BACKGROUND
micrornas  are ~21-nucleotide  short, single stranded rna molecules involved in post-transcriptional regulation of gene expression  <cit> .
they are present in higher eukaryotes and some viral genomes  <cit> .
because the mirna and small-interfering rna  pathways partly overlap, current understanding of mirna biogenesis has gained from advances made in the field of rna interference.
mature, functional mirnas develop from degenerate palindromic repeats with a characteristic hairpin-like secondary structure  <cit> .
initially, experimental identification of mirnas was achieved through direct cloning and sequencing of small rnas  <cit> .
however, such relatively low-throughput screenings were biased towards abundantly or ubiquitously expressed mirnas  <cit>  and missed many mirnas with restricted temporal or tissue-specific expression patterns  <cit> .
recently, strategies using pcr  <cit> , microarrays  <cit>  or ultra high-throughput sequencing  <cit>  have expanded the list of known mirnas.
many of these show tissue-specific expression  <cit>  or appear to be species-specific  <cit> .
in both arabidopsis thaliana  <cit>  and caenorhabditis elegans  <cit> , for example, high-throughput sequencing of small rnas shows moderate overlap in detected mirnas between experiments in each species, indicating that also in well studied genomes many new mirnas remain to be discovered.
in addition, the observation that many mirna loci exhibit compelling hairpin structures on both sense and antisense strands led to the discovery of anti-sense mirna transcription  <cit> .
antisense mirna transcription and processing yield distinct mature mirnas.
this contributes to the functional diversification of mirna genes for a considerable fraction of the known mirna loci  <cit> .
various methods for the in silico prediction of mirnas have been developed to aid in experimental studies of mirna discovery  <cit> .
these methods generally consider the hairpin-like secondary structure of the mirna precursor, the mirna hairpin, as the most important characteristic of a mirna gene.
they use rna secondary structure prediction  algorithms, such as rnafold  <cit>  or mfold  <cit> , to predict the secondary structure and thermodynamic stability of the rna hairpin structures.
current bioinformatics approaches for the prediction of mirnas  <cit>  generally include three steps:  genome-wide prediction of hairpin structures;  filtering or scoring of those hairpins on the basis of their similarity in physical and sequence features to known mirna hairpins and  experimental validation of putative candidates.
a common approach for the first step is to search for hairpin structures using a sliding window and perform rssp on each window  <cit> .
an improvement in overall calculation time over this approach is to first identify degenerate palindromic sequences and to analyse only these further with rssp  <cit> .
unfortunately, these approaches detect vast numbers of hairpin structures in complete eukaryotic genomes.
depending on the method used, 1e <dig> to 4e <dig> hairpins per mb of genomic sequence are found, resulting in about 1e <dig> hairpins identified in the human genome  <cit> .
the challenge is, therefore, to devise an appropriate filtering method to separate the chaff from the wheat.
different criteria for filtering candidate mirna sequences have been proposed, generally with the aim to reduce the search space and/or to increase the specificity of prediction  <cit> .
evolutionary conservation is considered an important feature of the hairpin sequence  <cit>  and analysis thereof is often used to identify and focus comparisons on the conserved non-coding sequence space in different genomes  <cit> .
an evolutionary approach known as phylogenetic shadowing has been used for combined selection and filtering of mirna candidates  <cit> .
this study revealed a characteristic camel-shaped conservation pattern of putatively orthologous mirnas that was useful as a criterion for finding conserved mirna candidates in primate genomes.
other filtering criteria include intragenomic matching of candidate mirnas and their potential targets  <cit> , evidence for expression, thresholds on structural properties of hairpins, e.g.
minimal folding energy , absence of repetitive or low-complexity sequences, occurrence in introns or intergenic regions  <cit> , or proximity to known mirna loci  <cit> .
stringent filtering is performed to attain high specificity, that is, to minimize the number of false positive predictions of mirna genes  <cit> .
obviously, maximizing specificity increases the number of false negative predictions, that is, a decreased sensitivity  <cit> .
this implies that with stringent filtering, relevant mirnas will be missed.
the success of any filtering procedure depends however on the validity of the underlying assumptions.
for example, filtering on evolutionary conservation will miss species-specific or fast evolving mirnas  <cit>  and low-complexity filtering is likely to miss mirnas originating from transposable elements  <cit> .
several recent methods employ machine learning techniques such as a support vector machine   <cit>  for classification.
such svms evaluate differences in hairpin properties between true-positive and true-negative examples of mirnas for a given taxon to generate a prediction classifier.
svms have been successfully used for mirna gene prediction  <cit>  and for the prediction of 5' drosha processing sites in mirna hairpins  <cit> .
although the svm approach is claimed to outperform earlier methods  <cit> , svm-based classifications combine many features in a single kernel function and therefore do not provide direct insight into the biological significance of these features.
such insight can only be obtained through expert analyses and dedicated feature selection procedures  <cit> .
moreover, the set of true-negatives which is required for training an svm is often very difficult to define.
here, we present an innovative strategy for mirna prediction that focuses on attaining optimal sensitivity.
we define and combine  <dig> different filtering criteria and, using a set of genomic hairpins identified in the genome of caenorhabditis elegans, show that  <dig> of these characteristics capture the biological variation of mirna features present in sets of known mirna hairpins.
these  <dig> criteria are used to establish a combined likelihood score l that assesses the likelihood that a predicted hairpin structure in a genome contains a genuine mirna.
l is a continuous classifier that allows user-adjustable thresholds for sensitivity and specificity in ab initio mirna prediction and mirna analysis.
good performance of l for large sets of hairpins from the genomes of c. elegans and four viruses demonstrates the added value of the new analytical strategy for future mirna discovery and selection.
RESULTS
we have developed and evaluated a new computational strategy for the prediction of candidate mirnas in dna sequences.
the new approach focuses on high sensitivity in an initial hairpin detection step, followed by a flexible, user-adjustable procedure to balance sensitivity with specificity and selectivity.
for all hairpin sequences from an input sequence, a mirna likelihood score l is calculated, given an underlying scoring model based on descriptors of the physical and sequence characteristics of mirnas .
the performance of the strategy was assessed by retrieval of known mirnas from hairpin structures identified in the genome of c. elegans.
appropriate scoring models were derived for various taxonomic sets of known mirnas.
a detailed explanation of all  <dig> descriptors is given in the additional information .
a boundary; indication of extreme tail of descriptor distribution that was transformed into s <  <dig> fraction.
symbols denote: ↓ lower tail; ↑ upper tail, and; ↓↑ both tails.
b type; descriptor based on structural , sequence  or both structural and sequence  properties of the hairpin.
c discriminative power; expressed at 95% sensitivity, measured on the taxonomic set metazoa  and genomic hairpins in c. elegans .
* discriminative power of descriptor 'z' was measured on  <dig>  identified hairpins in four viruses.
d k; highest cohen's kappa coefficient  <cit>  with another descriptor, measured on the taxonomic set metazoa with s <  <dig> cut-off of 95%.
descriptor data fit
most of the descriptors used for mirna characteristics have been proposed in previous studies  <cit> , but a few are, to the best of our knowledge, for the first time defined in this study, for example 'gasurpluscu' .
in all cases except one, the empirical data showed a good fit to a skew-normal  probability distribution  <cit>  according to a chi-square goodness-of-fit test .
as example, the frequency distribution, fitted sn distribution and the transformed likelihood distribution function  are shown for the descriptors mfe and gc content in figure  <dig>  the only exception to an sn probability distribution fit was found for the descriptor 'p', which is the p-value of the mfe of randomized sequence  <cit> .
this fitted best to an exponential distribution corrected for zero values.
results of the data fit for all descriptors from the taxonomic set metazoa are listed in additional file  <dig>
likelihood score s for mirna hairpin descriptors
the cdf of the fitted distribution was transformed into an ldf with outcome s. the range of s  has an s <  <dig> and an s =  <dig> fraction which are separated by the cut-off value derived from the 95% confidence interval of the descriptor's cdf.
the s <  <dig> fraction contains mirnas hairpins with descriptor values in the tail of the distribution.
these have a low probability of occurring in true mirna hairpins.
the s =  <dig> fraction contains mirna hairpins with values in the remainder of the distribution and corresponds to likely properties of mirna hairpins.
descriptors were treated differently with respect to the transformation of the tails of the cdf .
for example, for the descriptor "minimal folding energy"  of a mirna, there is in principle no need to impose a lower bound, even though the fitted distribution  indicates that very low mfe values occur rarely in known mirnas.
the ldf of the descriptor mfe assigns a score s =  <dig> for all values below - <dig>  kcal/mol.
higher mfes are penalized proportional to the ldf and therefore assigned a score s <  <dig>  mfe is an example of a descriptor where the s <  <dig> fraction represents the upper 5% tail of the confidence interval.
for other descriptors, the s <  <dig> fraction is represented by the lower 5% tail of the distribution  or by both the lower 5% and the upper 5% tail .
table  <dig> and additional file  <dig> list the unlikely tails for each descriptor.
correlation of descriptors
the  <dig> descriptors here defined were either based on the sequence of the hairpin, the structure of the hairpin or on a combination of both .
correlations among these were obvious, for instance, between stem length or gc-content on the one hand and the mfe of a hairpin on the other hand.
correlated descriptors will overemphasize the importance of a more general feature of a mirna hairpin and affect the usefulness of l. to assess the correlation among descriptors in their s <  <dig> fractions, we calculated cohen's kappa coefficient κ  <cit>  for all  <dig> possible pairs of descriptors, using the mirna hairpins of the taxonomic set metazoa .
for each descriptor the most strongly correlated descriptor, as determined by the highest observed κ is listed in table  <dig>  and additional file  <dig>  the highest κ was found between descriptors 'gcratio' and 'gsurplusc' , followed by 'd' and 'q'  and the pair 'p' and 'z' .
discriminative power of descriptors
a discriminative descriptor contributes to the separation of true mirna hairpins from non-mirna hairpins.
the discriminative power of a descriptor was defined as the ratio of percentages of mirna hairpins and genomic hairpins that comply with a threshold set to the descriptor's limiting value between s =  <dig> and s <  <dig> of the ldf .
a discriminative power smaller than  <dig>  implies that relatively more mirna hairpins are rejected than genomic hairpins.
higher values are obtained for descriptor values that are typically encountered in mirna hairpins, but that are less common in collections of genomic, predominantly non-mirna hairpins.
the most discriminative descriptor was mfeahl  and least discriminative were polyc, polycstem, polygstem  .
figure  <dig> illustrates the discriminative power of descriptor mfeahl and reveals a substantial difference between the sn-fitted cdfs of mirna hairpins and randomly selected genomic hairpins.
only 7% of genomic hairpins complied with the criterion of an mfeahl of  <dig> , representing 95% of the cdf of metazoan mirna hairpins.
the opposite was true for the least discriminative descriptors: for example for polyc, 99% of the genomic hairpins versus 96% of the metazoan mirna hairpins had a longest polyc stretch smaller than five .
delimiting a subset of most informative descriptors
the correlation and discriminative power of descriptors were used to select a non-redundant subset of most informative descriptors.
descriptors that either correlated with a more selective descriptor, using a threshold for correlation of κ> <dig> , or that had a discriminative power smaller than  <dig>  were omitted.
this resulted in a subset of  <dig> descriptors, seven of which were sequence related, nine structure related, and two descriptors with mixed properties .
remarkably, the descriptors 'gc-content' and the mfe randomization descriptors 'p'  <cit>  and 'z'  <cit> , which are often used in mirna prediction studies, were not included in the subset .
the latter two ranked among the most selective descriptors, but were excluded because of their strong correlation with the most selective descriptor mfeahl index, in which the mfe is adjusted for hairpin length and gc-content .
assessment of scoring model performance
the  <dig> most selective descriptors  were used to define and analyze different scoring models.
the cdf of the fitted distribution of all  <dig> descriptors was transformed into an ldf with outcome s and the l score for a given mirna sequence was calculated as the product of all s values.
scoring model performance, defined as the power to distinguish  mirna hairpins from other  genomic hairpins, was compared for different models that were built using varying settings for five parameters .
scoring model performance was measured as auc performance and, where appropriate, with selectivity measured at two values of sensitivity , using genomic hairpins in c. elegans and the collection of mirnas hairpins in the taxonomic set metazoa.
size of taxonomic set
as expected, scoring models based on small taxonomic sets had a less accurate data fit, as shown by increasing chi-square statistics for decreasing set size .
gain in goodness-of-fit and auc performance saturated with increasing set size.
the data presented in figure  <dig> indicate that a minimal set size of a thousand mirna hairpins is required for an accurate data fit  <  <dig> ).
performance in terms of selectivity appeared to increase beyond this set size, suggesting that prediction performance can be further improved by using larger taxonomic sets.
composition of taxonomic set
performance was found to depend on the evolutionary distance between the species contained in a scoring model's taxonomic set and the species for which  hairpins are scored by that scoring model.
when five taxonomic sets were constructed that comprised equally sized sets of mirna hairpins from taxa with a decreasing evolutionary distance and diversity relative to human , these showed increasing auc performance on the mirna hairpins from human.
the opposite trend, i.e.
a decrease in auc performance of the same five scoring models, was observed for mirna hairpins from nematoda and metazoa.
seemingly small differences in auc values translate to substantial differences in genome-wide counts of positive hairpins.
when choosing an arbitrary mirna detection sensitivity of 75%, the difference between an auc of  <dig>   and  <dig>   results in  <dig>  or  <dig> % fewer remaining genomic hairpins .
the results confirm that a scoring model based on a set that is taxonomically closest to the organism for which the mirna hairpins are scored, performs best.
however, it is noteworthy that taxonomic sets that do not contain human mirna hairpins  can yield scoring models with a good performance for identifying human mirnas.
composition of descriptor subset
selection of informative descriptors was found to be a crucial step in the development of scoring models, and three factors that affected scoring model performance were therefore analyzed in detail, i.e.
the number of descriptors selected , discriminative power of descriptors  and correlation between descriptors.
correlation of structural properties that describe rna molecules is well-known  <cit> .
in a mirna prediction method such correlations can strongly influence the prediction accuracy and should therefore be dealt with cautiously.
figure  <dig> illustrates the effect of highly correlated descriptors on scoring model performance, using the strongly correlated descriptors 'd' and 'q'  and a third descriptor 'scs-di' that has a weak correlation with both 'd' and 'q' .
scoring models containing pairs of uncorrelated descriptors had a higher selectivity value than the individual descriptors.
in contrast, the scoring model based on the strongly correlated descriptors 'd' and 'q' gave a lower discriminative power than one based on the most discriminative, individual descriptor 'q' .
although this decrease  seems small, the combined effect over all correlated descriptors will have a considerable effect in terms of the absolute number of genomic hairpins that are penalized.
it illustrates the necessity of selecting a descriptor subset with as little pair-wise correlation as possible in the development of appropriate scoring models.
parameterization of the ldf
the effect of parameterization on performance was assessed by lowering the default cut-off value  to 90% and 80% before use in calculation of the transformed likelihood distribution score s. the parameterization caused the number of mirna hairpins included in the s <  <dig> fractions to double  or quadruplicate  and increased the penalization of hairpins relative to the default cut-off value.
figure  <dig> shows that increased auc performance and selectivity values were obtained by lowering the cut-off value compared to the reference model, with selectivity indexed for the reference model.
the increase is explained by the fact that most descriptors gain in discriminative power at a decrease in sensitivity .
weighting of descriptors
the effect of weighting individual descriptors was studied by assigning weights to each of the  <dig> previously selected descriptors.
weights were equal to the square root of a descriptor's discriminative power as measured at a sensitivity of 95% and ranged from  <dig>  for gasurpluscu to  <dig>  for mfeahl .
figure  <dig> shows that a scoring model with weighted descriptors  had a significantly increased auc performance and selectivity index relative to their unweighted models .
obviously, when weighted on the basis of their discriminative power, descriptors with a high discriminative power contribute stronger to the overall l score than descriptors with low discriminative power.
as such, a better separation between mirna hairpins and random genomic hairpins is accomplished.
finally, combinations of weighting and varying the parameterization of descriptors were tested .
scoring model w90% had the highest auc performance on metazoan mirna hairpins of all tested models.
when weighting and parameterization were compared, weighting showed a stronger effect on selectivity measured at 95% sensitivity, whereas parameterization had a stronger effect on selectivity at 75% sensitivity.
this implies that both variables have a distinct effect on the shape of the roc curve.
building optimal scoring models
the data collected and analyses presented allowed the selection of optimal scoring models, with maximal discriminative power to distinguish true mirna hairpins from other genomic  hairpins for any given case.
in general, significant increases in selectivity were gained by descriptor weighting and parameterization.
in terms of choice for a specific scoring model, the taxonomic input set should be sufficiently large and taxonomically as close as possible to the organism of interest.
in total,  <dig> scoring models were built, based on  <dig> distinct taxonomic sets and the subset of  <dig> most informative descriptors, with the ldf parameterized at 90% of the cdf and using individual weighting of descriptors.
weighting and parameterization at 90% of the cdf resulted in the highest auc performance.
table  <dig> shows the performance gain of these optimal scoring models relative to their non-optimized counterparts.
figure  <dig> shows the roc curves for the final and initial scoring model metazoa.
the final scoring model metazoa was subjected to a 10-fold cross-validation for benchmarking and yielded an auc of  <dig> .
the arbitrary cut-off for l of  <dig> e- <dig> classifies  <dig> %  of mirna hairpins correctly as positive and  <dig> % of all genomic hairpins of c. elegans as negative.
the difference in performance with the non cross-validated auc performance  is due in part to the much smaller taxonomic input set used.
the latter was obtained by clustering all metazoan mirna hairpins on the basis of sequence similarity.
nearly identical hairpin sequences can have subtle variation in some descriptor values and thereby accurately represent the fact that mirnas occur in families.
therefore, and to maintain a classifier as selective as possible, we recommend to use the non-clustered variant of the scoring model.
a number of mirnas in taxonomic set
b -; no weighting , y; weighting individual descriptors by the square root of their discriminative power
c ldf parameterized at 95% or 90% of the cdf
d goodness-of-fit is evaluated by averaging chi-square test statistics of all  <dig> descriptors
e area under the curve of roc curves measured on the taxonomic sets of known mirna hairpins from nematodes , h. sapiens  and metazoa  versus  <dig>  randomly selected genomic hairpins from c. elegans.
f selectivity expressed at 95% and 75% sensitivity, with sensitivity measured on the taxonomic set of metazoa, specificity measured on set of  <dig> , <dig> c. elegans genomic hairpins.
g scorings models composed of the subset of  <dig> most informative descriptors
combined likelihood score l for mirna hairpin descriptors
the combined l score for a given mirna hairpin was calculated as the product of all s values of descriptors considered in a scoring model.
in figure  <dig>  the distribution of the resulting l scores for all mirna hairpins from the taxonomic set 'metazoa' is given for two different scoring models in a cumulative l-score plot.
for the scoring model metazoa , 31% of the known metazoan mirna hairpins had an l score of  <dig> .
this means that for  <dig>  mirna hairpins, the s score of the ldf of each of the  <dig> descriptors was  <dig> .
a cumulative l score plot can be used to select a desired level of sensitivity: an arbitrarily chosen sensitivity of 90% is reached at an l of  <dig>  for the optimized scoring model metazoa  and at an l of  <dig>  for the initial scoring model metazoa .
this hundred-fold difference is caused by adjusted parameterization and weighting of descriptors in the first model, resulting in a higher overall penalization.
this example illustrates that the l score is a relative measure that depends on the scoring model.
for all  <dig>  mirna hairpins used in this study, l scores were calculated for all  <dig> scoring models , which were all based on the subset of  <dig> descriptors.
figure  <dig> shows an example of a detailed descriptor report for cel-mir- <dig> for scoring model metazoa.
the report shows the individual descriptor values, positions of these values in the cdf of the descriptors and the transformed s scores.
the resulting l score equals  <dig>  due to the fact that three descriptors fall outside the 90% range of the cdf.
data for all  <dig>  combinations of mirnas  and scoring models  are available in the accompanying web document μrnall  <cit>
comparison of the l score approach to threshold filtering
comparison of our l score method to binary threshold filtering on mirna hairpin descriptors showed superior performance of the l classifier .
for sets of mirna and genomic hairpins that were filtered at the bordering value between the s =  <dig> and s <  <dig> fractions for all  <dig> descriptors, values for the performance parameters sensitivity, specificity and selectivity were obtained.
next, we kept either sensitivity or specificity constant, assessed at which l score this parameter was equalled and compared the other performance parameters.
in both cases, our scoring model approach outperformed threshold filtering.
when fixed at sensitivity, the scoring model approach achieved 17% better.
sensitivity was measured on all metazoan mirna hairpins  instead of on c. elegans mirna hairpins  because of the inaccuracy caused by the limited number of mirnas in the c. elegans set .
a sensitivity measured on the taxonomic set metazoa
b specificity measured on the set of  <dig> , <dig> genomic hairpins in c. elegans
c selectivity calculated with sensitivity on metazoan mirnas and specificity measured on c. elegans genomic hairpins
d minimal l score of the scoring model metazoa for which the performance of threshold filtering performance is equalled
predicting hairpins from a genomic sequence
we developed a procedure for predicting hairpin structures from genomic sequences using vmatch  <cit> .
the algorithm detects degenerate palindromic repeats and is therefore able to recover known mirna hairpins with very high sensitivity.
to benchmark the procedure, we predicted hairpin structures in the genomes c. elegans and four viruses: epstein-barr virus , mareks disease virus , human cytomegalovirus  and kaposi sarcoma-associated herpesvirus .
the number of recovered, known mirna hairpins, number of identified hairpins and percentage and absolute number of non-overlapping hairpins on unique loci are given for three different l score criteria for the scoring model metazoa, for both mirna and genomic hairpins .
a identified mirna hairpins/number of known mirna hairpins in genome in mirbase version  <dig>   <cit> .
b percentage of mirna or genomic hairpin loci that have at least a certain l-score for scoring model metazoa .
c mirna hcmv-mir-ul148d could not be mapped on the genomic sequence of hcmv .
d mirna kshv-mir-k12-10b could not be mapped on the genomic sequence of kshv .
in the four viral genomes,  <dig>  hairpins were identified, including all  <dig> known mirnas hairpins of these viruses.
in c. elegans,  <dig> , <dig> hairpins were predicted and only four out of  <dig> known mirnas hairpins were missed .
when benchmarking the performance of the hairpin identification with the mirbase entries  <cit>  of all metazoan mirna hairpins,  <dig>  out of  <dig>   mirna hairpins were recovered.
the hairpin prediction algorithm is independent of sequence context .
this benchmark is therefore an estimate of the algorithm's good performance on metazoan genomes.
similar performance has been reported for other edit-distance based hairpins detection methods  <cit> .
on a genome scale, all these methods yield around  <dig> – <dig>  hairpins per single stranded mb of sequence.
these hairpins are predominantly overlapping and nested.
analyses of mirna hairpin candidates in viral genomes
the data in table  <dig> show that only  <dig> – <dig> % of the indentified hairpin loci in four viral genomes have a high l score .
this corresponds to 69– <dig> loci per genome.
in addition, 83–100% of all known mirna hairpins comply with this threshold for l. out of  <dig>  hairpins predicted in the genome of ebv, only  <dig> hairpins, originating from  <dig> unique loci, had an l score of  <dig> .
ten of these were experimentally validated mirna loci  <cit>  .
further support for our mirna prediction and scoring method comes from recently discovered mirnas in the mdv genome  <cit>  that were not included in mirbase  <dig> .
all five novel mirnas  were present in the set of here predicted hairpins and three of these had l score of  <dig>  .
the  <dig> unique loci in mdv with an l score of  <dig>  collapsed into eight unique sequences due to a large inverted repeat.
out of these eight, all five loci that did not overlap with annotated exons corresponded to known mirna loci.
the two examples show that most hairpins in viral genomes with high l score are true mirna hairpins and that the absolute number of hairpin loci with high l scores is small.
this allowed us to manually examine the remaining, non-mirna loci with high l scores, using additional filtering criteria for genomic location such as proximity to known mirnas  <cit>  and intronic position  <cit> .
among the remaining loci in mdv with l ≥  <dig> , one appeared to be located in the transcribed strand of an intron and two others closely flanked  the mdv1-mir-m <dig> gene in the same orientation .
similarly, out of the remaining ten ebv loci with l =  <dig> , two candidate mirnas were located directly upstream and amidst a cluster of eleven known mirnas in an intronic region of the bart gene  <cit>  .
mining the c. elegans genome for putative mirna hairpins
using the scoring model metazoa, the genome of c. elegans was searched for potentially novel mirna hairpins.
for the set of  <dig> , <dig> genomic hairpins, a cut-off value l ≥  <dig>  resulted in a reduction of the number of candidate mirna loci to  <dig>  .
for l =  <dig>  only  <dig>  hairpins loci remained, but the sensitivity measured from retrieval of known mirna hairpins was only 34%.
nevertheless, this shows that filtering criteria in addition to the l score are required prior to experimental evaluation of candidate mirnas.
such criteria may include the use of annotation data or genomic context.
it has been suggested, for example, that metazoan mirnas do not overlap with exons  <cit> .
indeed, in the annotation used here , manual inspection of the genomic position of  <dig> known mirnas of c. elegans showed that only two hairpins  overlap with annotated exons .
another very selective criterion is similarity to a known  mature mirna.
we used this criterion such that similarity should be present in the stem of the hairpin and cover at least a  <dig> nt overlap with at most three mismatches.
this resulted in a reduction to only  <dig> hairpin loci .
another property of many mirnas is their clustered occurrence, with  <dig> from  <dig> mirnas in c. elegans separated by less than  <dig> kb  <cit> .
this criterion limited the number of hairpin loci to  <dig>  .
an example of a less selective criterion is removing all hairpins that fall in highly repetitive genomic areas.
a catalogue of repeat regions can be obtained by an algorithm as tandem repeats finder  <cit> .
additional selection can be accomplished with threshold filtering using the same  descriptors already used in our scoring model.
besides translating mirna hairpin properties into a statistic for relative rating, as done in calculating the l score, a descriptor can be used as a binary decision criterion: below the threshold, the hairpin is rejected as potential candidate; above it is included.
which descriptor to use for further filtering is in the hands of the individual researcher and may depend on the data studied.
in the following, we provide two examples of such filtering using seven individual descriptors: four based on structure  and three based on sequence complexity .
except for stem length, all individual thresholds fall within their s <  <dig> fractions and separately reject at most three c. elegans mirna hairpins.
this ensemble of thresholds excludes low-complexity sequences, captures palindromic repeats with limited degeneracy and should comprise the vast majority of mirnas.
in total, only six c. elegans mirna hairpins fail this filter and the same sensitivity  is achieved on all metazoan mirna hairpins.
only 30% of the set of genomic hairpins in c. elegans passes this filter, representing a selectivity of  <dig>  .
a rejected c. elegans mirna hairpins by this step alone
b remaining cumulative number of c. elegans mirna hairpins; remaining cumulative number of genomic hairpin loci
c similarity to a metazoan mature mirna of at least  <dig> nt length with at most three mismatches
d cel-mir- <dig> is fully located in the final exon of y105e8a.16; cel-mir- <dig> is largely located in the 3'utr of zk <dig> , but overlaps  <dig> nt with the final exon
e at most  <dig> nt overlap with a repeat identified by tandem repeats finder  <cit>
f similarity with mature mirna may have at most  <dig> nt overlap with hairpin loop coordinates and at least  <dig> nt of the stem must separate the similarity from the end of the hairpin.
criteria are set according to the biological model of mirna maturation from hairpins  <cit> .
in the following examples, filtering on l score was combined with filtering on either genomic context or on a similarity threshold to known metazoan mature mirnas .
goal of these filtering protocols was to achieve sets feasibly sized for manual inspection and/or laboratory evaluation.
the protocols comply with characteristics of mirnas mentioned above: occurrence in clusters and presence in families.
"clustered" and "similar" resulted in lists of  <dig> and  <dig> candidate mirna loci , respectively, that were manually inspected.
the most compelling cases among these are presented in figure  <dig> and figure  <dig>  figure  <dig> shows a cluster of hairpins of which several have l =  <dig>  starting  <dig> kb downstream of cel-mir- <dig>  figure  <dig> shows two conspicuous hairpins that share similarity with the two known mature mirnas cel-mir- <dig> and cel-mir- <dig> .
the multiple alignment of the four hairpin sequences revealed the characteristic camel-shaped conservation pattern that is often observed between related mirnas  <cit> : high or perfect conservation in the stem of the pre-mirna hairpins, low conservation in the hairpin loop and the up- and downstream stem sequences.
the 5' seed sequences of both mature mirnas  are exactly conserved in the novel hairpins, suggesting that hairpins  <dig> , <dig> and  <dig> , <dig> are likely members of the mirna families to which cel-mir- <dig> and cel-mir- <dig> belong  <cit> .
furthermore, candidate  <dig> , <dig> is located in the 12th intron of the gene f54f <dig> , for which the c. elegans unigene set   <cit>  provided evidence of transcription.
cel-mir- <dig> and cel-mir- <dig> were predicted by comparative computational approaches and confirmed by a pcr amplification protocol, but their precise mature mirna ends are unknown  <cit> .
recent high-throughput sequencing of mirnas from c. elegans  <cit>  could not confirm the existence of both mirnas.
the data presented for the filtering protocols "clustered" and "similar"  show that combined filtering on l score, genomic context and threshold filtering allows for compilation of a priority list of candidate mirnas that is amenable to manual inspection and experimental verification.
apart from filtering on genomic clustering or similarity to known mirnas, filtering on l score attains the largest data reduction.
this shows that the l score was important in compilation of the priority list and demonstrates the added value of our approach for in silico mirna prediction.
discussion
we here present a new computational strategy for the in silico prediction of mirna hairpins and show the applicability of the method for predicting new candidate mirna hairpins in four viral genomes and in the genome of c. elegans.
while using the latter as an example for model construction, the l score method as here optimized for c. elegans is well usable for other metazoan genomes.
however, further improvement of performance of the method on different taxonomic groups can be achieved by constructing dedicated scoring models .
our strategy aims at minimizing the number of false negative predictions , rather than at minimizing the number of false positive predictions , as proposed in previous studies.
focusing on sensitivity rather than specificity should help uncover new classes of mirna molecules in biological systems.
hairpins in genomic sequences are identified with the help of an adjusted suffix-tree based method.
when the performance of the hairpin prediction was benchmarked on sets of all known mirnas hairpins from viruses and metazoa, all  <dig> viral mirnas were recovered ,  <dig> of  <dig>  c. elegans mirnas were recovered and  <dig>  out of  <dig>   metazoan mirnas were shown to be recoverable when considered in their genomic context.
similar performance was reported for another edit distance-based hairpin identification method  <cit> .
four c. elegans mirnas  remained undetected due to the absence of a stringently base-pairing area in their stems.
they all had extremely poor l scores , ranking first, third, fourth and eight among the c. elegans mirna hairpins with lowest l scores.
none of the four was found in recent high-throughput sequencing datasets, which otherwise retrieved the vast majority of known c. elegans mirnas  <cit> .
this suggests that these four may not be genuine mirnas.
if so, the reported performance of our hairpin prediction method is underestimated.
the biological variation and evolutionary diversity of various properties of mirna hairpins were captured in a likelihood score l, based on statistics derived from accurately fitted  distributions of hairpin characteristics derived from known mirna hairpins.
in total  <dig> hairpin characteristics were defined and analyzed.
the l score is a measure for a single hairpin sequence: a descriptor that captures evolutionary conservation in another species is not included.
although conservation has proven to be an extremely selective mirna detection criterion  <cit> , it conflicts with the aim to maximize sensitivity, because of the existence of species-specific mirnas.
the strategy was evaluated on genomic hairpins and known mirnas from the c. elegans genome.
although details of analyses and results are likely to differ when applied to other genomes and other negative sets of genomic hairpins, major trends and results were shown to be similar .
based on analyses of correlation and discriminative power,  <dig> hairpin characteristics were identified as most selective.
comparison of the  <dig> descriptor scoring model with a binary threshold filtering protocol using the same  <dig> descriptors  shows that a 17% higher selectivity is achieved with the l score strategy.
binary decision thresholds on all or even a few descriptors can easily result in a major decrease of sensitivity.
in the strategy developed here, l <  <dig> represents individual sequences that have one or more descriptors with s <  <dig>  indicating that these descriptors have a relatively low probability of occurrence in mirna hairpins because they occur in the tail of their respective distribution.
when a descriptor value falls outside the observed range of biological variation, the continuous likelihood score l allows for the compensation of an unlikely score for a single descriptor by likely scores for other descriptors.
in such a case, the sequence is not a priori rejected as a mirna hairpin candidate.
the l score thus allows for more deviations from 'genuine' mirna characteristics than binary selection  on the basis of the same characteristics.
this is an important improvement over the use of pre-defined thresholds for filtering on single or multiple descriptors published previously  <cit> .
assigning scores to descriptors, as opposed to binary selection on pre-defined thresholds, has also been used in previous work.
for example, mirscan  <cit>  employs an heuristic score assignment to seven features and assigns weights based on the relative entropy between known mirna hairpins and genomic hairpins.
palgrade  <cit>  uses a statistical distribution by arbitrarily binning the ordered vector of descriptor values.
svm kernels achieve descriptor scoring and weighting as part of the svm  <cit> .
novel to the approach here developed is that the score assignment is based entirely on the statistical evaluation of the variation in physical and sequence properties observed in known mirnas and no binary selection prior to building a scoring model is used.
the l score is a relative measure of the likelihood that a given hairpin is a mirna hairpin candidate.
an important parameter contributing to useful l scores is the number of mirnas used to derive the discriminating statistics of the individual characteristics.
a minimum of about a thousand mirna hairpins is required, but results indicate that the larger the available data set, the better the scoring model captures the variation in mirna hairpin characteristics and performs.
in the context of machine learning, the input mirna set could be considered a training set, although in the l score derivation no formal 'training' is included.
it is noteworthy that the evolutionary distance between the species contained in the taxonomic set for a scoring model influences l considerably.
in general, the scoring model based on the set that is taxonomically closest to the organism being analyzed performs best.
this indicates that over a wide range of characteristics, mirna hairpins within  species are substantially more alike than mirna hairpin sequences between less-related species.
this should be taken into account when searching for similarity between mirna hairpins from distantly related species.
however, we observed that, for example, taxonomic sets that do not contain human mirna hairpins can yield scoring models that accurately identify human mirna hairpins.
in addition, descriptor weighting and parameterization appeared to considerably influence the performance of a scoring model.
the analyses presented allow the selection of optimal scoring models, with maximal discriminative power to distinguish true mirna hairpins from other genomic  hairpins for a selected set and a given data set.
however, each set of data, for example in case of a new genome sequence, will require its own analysis to build an optimal scoring model.
whereas the analyses started with  <dig> descriptors, based on extensive correlation and selectivity analyses, a subset model based on  <dig> descriptors was performing better than the model comprising all  <dig> descriptors.
in view of the importance of the taxonomic composition of the set used in the model, it should be pointed out, that this may reflect a taxonomic bias for metazoan sequences that may not be valid for other taxonomic groups, such as, for example plant mirna hairpins.
in the set of  <dig> most informative descriptors selected, it is remarkable that three descriptors that are generally considered important are not represented: gc content and the mfe randomization descriptors p and z. gc-content is widely used as a pre-filtering step of in silico mirna prediction methods  <cit> , but is not among the  <dig> descriptors used in the final scoring models.
the gc-content showed the highest variability in the  mean over different taxonomic sets , reflecting the apparently large variation in gc-content found among mirna hairpins from different species.
any scoring model that includes the fitted distribution of gc-content would disqualify hairpin structures in species containing mirnas with relatively high or low gc-content.
also the descriptors p and z, based on mfe randomization shown to be significantly lower for mirnas hairpins than for randomized sequences  <cit> , were not among the <dig> descriptors selected.
although p and z ranked among the most selective descriptors, they were excluded because of their strong correlation  with the most selective descriptor mfeahl index, in which the mfe is adjusted for hairpin length and gc-content.
svms have similar aims as the l-score strategy and perform well in mirna classification  <cit> .
in assessing and comparing the performance of different methods, however, several caveats should be considered.
first, methods that use evolutionary conservation perform well on conserved mirnas  <cit>  but fail to detect species-specific or fast evolving mirnas  <cit> .
the importance of the latter should not be underestimated.
second, the particular data set on which the performance is achieved is important to the evaluation and comparison of the results from different methods.
unfortunately, there is no benchmark set of both positive and negative examples of mirna hairpins available.
many methods are tailored on a specific organism and are likely to perform best in that exact context.
assembling a set of true negative sequences is particularly challenging: hairpins in non-coding rnas, e.g.
the set of trnas as used in  <cit> , are likely to possess different and more diverse hairpin features than mirna hairpins, whereas a set of genomic hairpins might contain bona fide mirna hairpins.
svms explicitly require negative examples for training and testing, whereas the l scoring method uses such a set only for benchmarking purposes.
third, data on prediction performance are not reported consistently in literature.
our method enables reporting of auc performance as well as sensitivity and specificity values over the entire range of the roc curve.
comparison with binary classifiers from other methods therefore requires transformation of the continuous outcome to a binary outcome by choosing an arbitrary threshold for l and using the associated sensitivity and specificity values as measure of the performance.
with these caveats in mind, we compared the performance of our method to three leading svm-based methods mipred  <cit> , rnamicro  <cit>  and mirna svm  <cit>  note that rnamicro is based on multiple sequence alignments.
using different positive and negative datasets, these methods report the following values of sensitivity and specificity; 1) mipred:  <dig> % and  <dig> %, using  <dig> human mirnas as positive and  <dig> human genomic hairpins as negative set; 2) mipred:  <dig> % and  <dig> %, using  <dig>  metazoan, non-human mirnas as positive and  <dig>  human genomic hairpins as negative set; 3) rnamicro: 90% and 99%, using  <dig> metazoan mirna hairpin alignments as positive and  <dig> shuffled mirna hairpin and trna alignments as negative set, and; 4) mirna svm: 90% and 95%, using  <dig> human mirnas as positive and  <dig>  random human genomic hairpins as negative set.
these performances compare well to the values of  <dig> % and  <dig> % obtained in the  <dig> fold-cross validated performance of our l score model, using  <dig> metazoan mirna hairpins as positive and  <dig>  randomly selected genomic hairpins from c. elegans as negative set.
the performance of the l scoring model is most similar to that of mipred, which does not include sequence conservation as a parameter.
an analysis of the performance of our model on sets of genomic hairpins other than those derived for the c. elegans genome is provided as additional file .
a major challenge of any svm is understanding its behavior in, for example, a biological context.
while svms are known to produce classifiers that perform well in case of unseen data  <cit> , svms are essentially black-box classifiers.
this makes it difficult to judge the relative importance of individual descriptors or to translate results in biologically relevant understanding.
as all parameters are embedded in the kernel function of the svm, svm classifiers are also difficult to adjust, although they do not require the pre-selection of parameters required for the l score strategy here presented.
classifier selection based on the detailed descriptor analysis presented here may improve future svm approaches.
a key advantage of the l score strategy over svms is that the contribution of individual descriptors to a scoring model can be analyzed in a straightforward way by adding or removing a descriptor or changing the parameterization or weight of descriptors.
this way the scoring model becomes better tailored to the biologist's needs in a particular research environment.
CONCLUSIONS
at the laboratory bench, the criterion that is of most interest is simply how many putative hairpins should be evaluated by experimentation.
with current developments in microarray analysis and high-throughput sequencing, the numbers of potential candidates that can be screened with relative ease will increase dramatically.
still large numbers of new mirnas may be identified.
yet, for the time being, the individual laboratory would like to see as little putative candidates as possible with as high a success rate as feasible.
the highest l score is  <dig>  implying that the given hairpin scores are maximal for all descriptors in the model.
in the  <dig> mb large genome of c. elegans, still  <dig>  hairpin loci remain that cannot be ranked further on the basis of l. it implies that relatively large numbers of genomic hairpins  comply with all mirna hairpin descriptors, whereas it is unlikely that they all generate mature mirnas, given the relative small number of  <dig> currently known c. elegans mirnas.
it is likely that this situation will occur in most genomic contexts.
if so, several strategies are open.
the model parameters could be adjusted, so that the individual descriptor is less likely to get the maximal score.
this way, the l score approach will convert to more traditional threshold filtering.
given that the analysis requires high sensitivity, it would however be more advantageous to incorporate more biological expert knowledge in the selection process, such as the presence of the hairpin in an intron, sequence similarity to known mirnas, etc.
when following this strategy, one has to be aware that the number of novel mirnas that could be discovered is constrained by the filtering on genomic context.
for example, in the set of  <dig> mirnas in c. elegans ,  <dig> occur in singletons when clustered on distance,  <dig> have no other family representative and  <dig> are not located in an intron  <cit> .
these numbers can thus be considered as indicative for the fraction of true mirnas that will remain concealed when filtering on genomic context.
with the filtering protocols  we show that a combination of filtering on l score, genomic context and threshold filtering allows for compilation of a priority list of manageable size for manual inspection and further experimentation.
in addition to good performance in comparison with other leading  methods and a user-defined selectivity, an additional advantage of the l score approach over threshold filtering and support vector machine classifiers is that the prior analysis of taxonomically defined sets and fitted distributions, correlations, and discriminative power of descriptors gives detailed insight in the behavior of a scoring model and can accommodate expert knowledge.
it should therefore appeal to the experimental biologist, despite the fairly time-consuming construction of a suitable scoring model.
the scoring model proposed here is independent of the hairpin prediction step and can therefore be coupled to any in silico or experimental mirna prediction method.
it can facilitate the analysis of large sets of putative mirna hairpin loci obtained in deep-sequencing efforts of small rnas  <cit> .
the l score approach can be used to rank and select interesting mirna hairpin candidates for downstream experimental analysis in search for novel mirnas.
moreover, our in-depth analyses of known mirna hairpins from mirbase  <cit> , our detailed descriptor analyses  and the l score approach here presented are likely to increase the reliability and evidence of mirbase entries and will help to further increase the biological relevance of the mirbase repository.

 micrornas are ~21-nucleotide short, single stranded rna molecules involved in post-transcriptional regulation of gene expression. they are present in higher eukaryotes and some viral genomes. because the mirna and small-interfering rna pathways partly overlap, current understanding of mirna biogenesis has gained from advances made in the field of rna interference. mature, functional mirnas develop from degenerate palindromic repeats with a characteristic hairpin-like secondary structure. initially, experimental identification of mirnas was achieved through direct cloning and sequencing of small rnas. however, such relatively low-throughput screenings were biased towards abundantly or ubiquitously expressed mirnas and missed many mirnas with restricted temporal or tissue-specific expression patterns. recently, strategies using pcr, microarrays or ultra high-throughput sequencing have expanded the list of known mirnas. many of these show tissue-specific expression or appear to be species-specific. in both arabidopsis thaliana and caenorhabditis elegans, for example, high-throughput sequencing of small rnas shows moderate overlap in detected mirnas between experiments in each species, indicating that also in well studied genomes many new mirnas remain to be discovered. in addition, the observation that many mirna loci exhibit compelling hairpin structures on both sense and antisense strands led to the discovery of anti-sense mirna transcription. antisense mirna transcription and processing yield distinct mature mirnas. this contributes to the functional diversification of mirna genes for a considerable fraction of the known mirna loci. various methods for the in silico prediction of mirnas have been developed to aid in experimental studies of mirna discovery. these methods generally consider the hairpin-like secondary structure of the mirna precursor, the mirna hairpin, as the most important characteristic of a mirna gene. they use rna secondary structure prediction algorithms, such as rnafold or mfold, to predict the secondary structure and thermodynamic stability of the rna hairpin structures. current bioinformatics approaches for the prediction of mirnas generally include three steps: genome-wide prediction of hairpin structures; filtering or scoring of those hairpins on the basis of their similarity in physical and sequence features to known mirna hairpins and experimental validation of putative candidates. a common approach for the first step is to search for hairpin structures using a sliding window and perform rssp on each window. an improvement in overall calculation time over this approach is to first identify degenerate palindromic sequences and to analyse only these further with rssp. unfortunately, these approaches detect vast numbers of hairpin structures in complete eukaryotic genomes. depending on the method used, 1e to 4e hairpins per mb of genomic sequence are found, resulting in about 1e hairpins identified in the human genome. the challenge is, therefore, to devise an appropriate filtering method to separate the chaff from the wheat. different criteria for filtering candidate mirna sequences have been proposed, generally with the aim to reduce the search space and/or to increase the specificity of prediction. evolutionary conservation is considered an important feature of the hairpin sequence and analysis thereof is often used to identify and focus comparisons on the conserved non-coding sequence space in different genomes. an evolutionary approach known as phylogenetic shadowing has been used for combined selection and filtering of mirna candidates. this study revealed a characteristic camel-shaped conservation pattern of putatively orthologous mirnas that was useful as a criterion for finding conserved mirna candidates in primate genomes. other filtering criteria include intragenomic matching of candidate mirnas and their potential targets, evidence for expression, thresholds on structural properties of hairpins, e.g. minimal folding energy, absence of repetitive or low-complexity sequences, occurrence in introns or intergenic regions, or proximity to known mirna loci. stringent filtering is performed to attain high specificity, that is, to minimize the number of false positive predictions of mirna genes. obviously, maximizing specificity increases the number of false negative predictions, that is, a decreased sensitivity. this implies that with stringent filtering, relevant mirnas will be missed. the success of any filtering procedure depends however on the validity of the underlying assumptions. for example, filtering on evolutionary conservation will miss species-specific or fast evolving mirnas and low-complexity filtering is likely to miss mirnas originating from transposable elements. several recent methods employ machine learning techniques such as a support vector machine for classification. such svms evaluate differences in hairpin properties between true-positive and true-negative examples of mirnas for a given taxon to generate a prediction classifier. svms have been successfully used for mirna gene prediction and for the prediction of 5' drosha processing sites in mirna hairpins. although the svm approach is claimed to outperform earlier methods, svm-based classifications combine many features in a single kernel function and therefore do not provide direct insight into the biological significance of these features. such insight can only be obtained through expert analyses and dedicated feature selection procedures. moreover, the set of true-negatives which is required for training an svm is often very difficult to define. here, we present an innovative strategy for mirna prediction that focuses on attaining optimal sensitivity. we define and combine different filtering criteria and, using a set of genomic hairpins identified in the genome of caenorhabditis elegans, show that of these characteristics capture the biological variation of mirna features present in sets of known mirna hairpins. these criteria are used to establish a combined likelihood score l that assesses the likelihood that a predicted hairpin structure in a genome contains a genuine mirna. l is a continuous classifier that allows user-adjustable thresholds for sensitivity and specificity in ab initio mirna prediction and mirna analysis. good performance of l for large sets of hairpins from the genomes of c. elegans and four viruses demonstrates the added value of the new analytical strategy for future mirna discovery and selection.  we have developed and evaluated a new computational strategy for the prediction of candidate mirnas in dna sequences. the new approach focuses on high sensitivity in an initial hairpin detection step, followed by a flexible, user-adjustable procedure to balance sensitivity with specificity and selectivity. for all hairpin sequences from an input sequence, a mirna likelihood score l is calculated, given an underlying scoring model based on descriptors of the physical and sequence characteristics of mirnas. the performance of the strategy was assessed by retrieval of known mirnas from hairpin structures identified in the genome of c. elegans. appropriate scoring models were derived for various taxonomic sets of known mirnas. a detailed explanation of all descriptors is given in the additional information. a boundary; indication of extreme tail of descriptor distribution that was transformed into s < fraction. symbols denote: ↓ lower tail; ↑ upper tail, and; ↓↑ both tails. b type; descriptor based on structural, sequence or both structural and sequence properties of the hairpin. c discriminative power; expressed at 95% sensitivity, measured on the taxonomic set metazoa and genomic hairpins in c. elegans. * discriminative power of descriptor'z' was measured on identified hairpins in four viruses. d k; highest cohen's kappa coefficient with another descriptor, measured on the taxonomic set metazoa with s < cut-off of 95%. descriptor data fit most of the descriptors used for mirna characteristics have been proposed in previous studies, but a few are, to the best of our knowledge, for the first time defined in this study, for example'gasurpluscu'. in all cases except one, the empirical data showed a good fit to a skew-normal probability distribution according to a chi-square goodness-of-fit test. as example, the frequency distribution, fitted sn distribution and the transformed likelihood distribution function are shown for the descriptors mfe and gc content in figure the only exception to an sn probability distribution fit was found for the descriptor'p', which is the p-value of the mfe of randomized sequence. this fitted best to an exponential distribution corrected for zero values. results of the data fit for all descriptors from the taxonomic set metazoa are listed in additional file likelihood score s for mirna hairpin descriptors the cdf of the fitted distribution was transformed into an ldf with outcome s. the range of s has an s < and an s = fraction which are separated by the cut-off value derived from the 95% confidence interval of the descriptor's cdf. the s < fraction contains mirnas hairpins with descriptor values in the tail of the distribution. these have a low probability of occurring in true mirna hairpins. the s = fraction contains mirna hairpins with values in the remainder of the distribution and corresponds to likely properties of mirna hairpins. descriptors were treated differently with respect to the transformation of the tails of the cdf. for example, for the descriptor "minimal folding energy" of a mirna, there is in principle no need to impose a lower bound, even though the fitted distribution indicates that very low mfe values occur rarely in known mirnas. the ldf of the descriptor mfe assigns a score s = for all values below - kcal/mol. higher mfes are penalized proportional to the ldf and therefore assigned a score s < mfe is an example of a descriptor where the s < fraction represents the upper 5% tail of the confidence interval. for other descriptors, the s < fraction is represented by the lower 5% tail of the distribution or by both the lower 5% and the upper 5% tail. table and additional file list the unlikely tails for each descriptor. correlation of descriptors the descriptors here defined were either based on the sequence of the hairpin, the structure of the hairpin or on a combination of both. correlations among these were obvious, for instance, between stem length or gc-content on the one hand and the mfe of a hairpin on the other hand. correlated descriptors will overemphasize the importance of a more general feature of a mirna hairpin and affect the usefulness of l. to assess the correlation among descriptors in their s < fractions, we calculated cohen's kappa coefficient κ for all possible pairs of descriptors, using the mirna hairpins of the taxonomic set metazoa. for each descriptor the most strongly correlated descriptor, as determined by the highest observed κ is listed in table and additional file the highest κ was found between descriptors'gcratio' and'gsurplusc', followed by'd' and'q' and the pair'p' and'z'. discriminative power of descriptors a discriminative descriptor contributes to the separation of true mirna hairpins from non-mirna hairpins. the discriminative power of a descriptor was defined as the ratio of percentages of mirna hairpins and genomic hairpins that comply with a threshold set to the descriptor's limiting value between s = and s < of the ldf. a discriminative power smaller than implies that relatively more mirna hairpins are rejected than genomic hairpins. higher values are obtained for descriptor values that are typically encountered in mirna hairpins, but that are less common in collections of genomic, predominantly non-mirna hairpins. the most discriminative descriptor was mfeahl and least discriminative were polyc, polycstem, polygstem. figure illustrates the discriminative power of descriptor mfeahl and reveals a substantial difference between the sn-fitted cdfs of mirna hairpins and randomly selected genomic hairpins. only 7% of genomic hairpins complied with the criterion of an mfeahl of, representing 95% of the cdf of metazoan mirna hairpins. the opposite was true for the least discriminative descriptors: for example for polyc, 99% of the genomic hairpins versus 96% of the metazoan mirna hairpins had a longest polyc stretch smaller than five. delimiting a subset of most informative descriptors the correlation and discriminative power of descriptors were used to select a non-redundant subset of most informative descriptors. descriptors that either correlated with a more selective descriptor, using a threshold for correlation of κ>, or that had a discriminative power smaller than were omitted. this resulted in a subset of descriptors, seven of which were sequence related, nine structure related, and two descriptors with mixed properties. remarkably, the descriptors'gc-content' and the mfe randomization descriptors'p' and'z', which are often used in mirna prediction studies, were not included in the subset. the latter two ranked among the most selective descriptors, but were excluded because of their strong correlation with the most selective descriptor mfeahl index, in which the mfe is adjusted for hairpin length and gc-content. assessment of scoring model performance the most selective descriptors were used to define and analyze different scoring models. the cdf of the fitted distribution of all descriptors was transformed into an ldf with outcome s and the l score for a given mirna sequence was calculated as the product of all s values. scoring model performance, defined as the power to distinguish mirna hairpins from other genomic hairpins, was compared for different models that were built using varying settings for five parameters. scoring model performance was measured as auc performance and, where appropriate, with selectivity measured at two values of sensitivity, using genomic hairpins in c. elegans and the collection of mirnas hairpins in the taxonomic set metazoa. size of taxonomic set as expected, scoring models based on small taxonomic sets had a less accurate data fit, as shown by increasing chi-square statistics for decreasing set size. gain in goodness-of-fit and auc performance saturated with increasing set size. the data presented in figure indicate that a minimal set size of a thousand mirna hairpins is required for an accurate data fit < ). performance in terms of selectivity appeared to increase beyond this set size, suggesting that prediction performance can be further improved by using larger taxonomic sets. composition of taxonomic set performance was found to depend on the evolutionary distance between the species contained in a scoring model's taxonomic set and the species for which hairpins are scored by that scoring model. when five taxonomic sets were constructed that comprised equally sized sets of mirna hairpins from taxa with a decreasing evolutionary distance and diversity relative to human, these showed increasing auc performance on the mirna hairpins from human. the opposite trend, i.e. a decrease in auc performance of the same five scoring models, was observed for mirna hairpins from nematoda and metazoa. seemingly small differences in auc values translate to substantial differences in genome-wide counts of positive hairpins. when choosing an arbitrary mirna detection sensitivity of 75%, the difference between an auc of and results in or % fewer remaining genomic hairpins. the results confirm that a scoring model based on a set that is taxonomically closest to the organism for which the mirna hairpins are scored, performs best. however, it is noteworthy that taxonomic sets that do not contain human mirna hairpins can yield scoring models with a good performance for identifying human mirnas. composition of descriptor subset selection of informative descriptors was found to be a crucial step in the development of scoring models, and three factors that affected scoring model performance were therefore analyzed in detail, i.e. the number of descriptors selected, discriminative power of descriptors and correlation between descriptors. correlation of structural properties that describe rna molecules is well-known. in a mirna prediction method such correlations can strongly influence the prediction accuracy and should therefore be dealt with cautiously. figure illustrates the effect of highly correlated descriptors on scoring model performance, using the strongly correlated descriptors'd' and'q' and a third descriptor'scs-di' that has a weak correlation with both'd' and'q'. scoring models containing pairs of uncorrelated descriptors had a higher selectivity value than the individual descriptors. in contrast, the scoring model based on the strongly correlated descriptors'd' and'q' gave a lower discriminative power than one based on the most discriminative, individual descriptor'q'. although this decrease seems small, the combined effect over all correlated descriptors will have a considerable effect in terms of the absolute number of genomic hairpins that are penalized. it illustrates the necessity of selecting a descriptor subset with as little pair-wise correlation as possible in the development of appropriate scoring models. parameterization of the ldf the effect of parameterization on performance was assessed by lowering the default cut-off value to 90% and 80% before use in calculation of the transformed likelihood distribution score s. the parameterization caused the number of mirna hairpins included in the s < fractions to double or quadruplicate and increased the penalization of hairpins relative to the default cut-off value. figure shows that increased auc performance and selectivity values were obtained by lowering the cut-off value compared to the reference model, with selectivity indexed for the reference model. the increase is explained by the fact that most descriptors gain in discriminative power at a decrease in sensitivity. weighting of descriptors the effect of weighting individual descriptors was studied by assigning weights to each of the previously selected descriptors. weights were equal to the square root of a descriptor's discriminative power as measured at a sensitivity of 95% and ranged from for gasurpluscu to for mfeahl. figure shows that a scoring model with weighted descriptors had a significantly increased auc performance and selectivity index relative to their unweighted models. obviously, when weighted on the basis of their discriminative power, descriptors with a high discriminative power contribute stronger to the overall l score than descriptors with low discriminative power. as such, a better separation between mirna hairpins and random genomic hairpins is accomplished. finally, combinations of weighting and varying the parameterization of descriptors were tested. scoring model w90% had the highest auc performance on metazoan mirna hairpins of all tested models. when weighting and parameterization were compared, weighting showed a stronger effect on selectivity measured at 95% sensitivity, whereas parameterization had a stronger effect on selectivity at 75% sensitivity. this implies that both variables have a distinct effect on the shape of the roc curve. building optimal scoring models the data collected and analyses presented allowed the selection of optimal scoring models, with maximal discriminative power to distinguish true mirna hairpins from other genomic hairpins for any given case. in general, significant increases in selectivity were gained by descriptor weighting and parameterization. in terms of choice for a specific scoring model, the taxonomic input set should be sufficiently large and taxonomically as close as possible to the organism of interest. in total, scoring models were built, based on distinct taxonomic sets and the subset of most informative descriptors, with the ldf parameterized at 90% of the cdf and using individual weighting of descriptors. weighting and parameterization at 90% of the cdf resulted in the highest auc performance. table shows the performance gain of these optimal scoring models relative to their non-optimized counterparts. figure shows the roc curves for the final and initial scoring model metazoa. the final scoring model metazoa was subjected to a 10-fold cross-validation for benchmarking and yielded an auc of. the arbitrary cut-off for l of e- classifies % of mirna hairpins correctly as positive and % of all genomic hairpins of c. elegans as negative. the difference in performance with the non cross-validated auc performance is due in part to the much smaller taxonomic input set used. the latter was obtained by clustering all metazoan mirna hairpins on the basis of sequence similarity. nearly identical hairpin sequences can have subtle variation in some descriptor values and thereby accurately represent the fact that mirnas occur in families. therefore, and to maintain a classifier as selective as possible, we recommend to use the non-clustered variant of the scoring model. a number of mirnas in taxonomic set b -; no weighting, y; weighting individual descriptors by the square root of their discriminative power c ldf parameterized at 95% or 90% of the cdf d goodness-of-fit is evaluated by averaging chi-square test statistics of all descriptors e area under the curve of roc curves measured on the taxonomic sets of known mirna hairpins from nematodes, h. sapiens and metazoa versus randomly selected genomic hairpins from c. elegans. f selectivity expressed at 95% and 75% sensitivity, with sensitivity measured on the taxonomic set of metazoa, specificity measured on set of, c. elegans genomic hairpins. g scorings models composed of the subset of most informative descriptors combined likelihood score l for mirna hairpin descriptors the combined l score for a given mirna hairpin was calculated as the product of all s values of descriptors considered in a scoring model. in figure the distribution of the resulting l scores for all mirna hairpins from the taxonomic set'metazoa' is given for two different scoring models in a cumulative l-score plot. for the scoring model metazoa, 31% of the known metazoan mirna hairpins had an l score of. this means that for mirna hairpins, the s score of the ldf of each of the descriptors was. a cumulative l score plot can be used to select a desired level of sensitivity: an arbitrarily chosen sensitivity of 90% is reached at an l of for the optimized scoring model metazoa and at an l of for the initial scoring model metazoa. this hundred-fold difference is caused by adjusted parameterization and weighting of descriptors in the first model, resulting in a higher overall penalization. this example illustrates that the l score is a relative measure that depends on the scoring model. for all mirna hairpins used in this study, l scores were calculated for all scoring models, which were all based on the subset of descriptors. figure shows an example of a detailed descriptor report for cel-mir- for scoring model metazoa. the report shows the individual descriptor values, positions of these values in the cdf of the descriptors and the transformed s scores. the resulting l score equals due to the fact that three descriptors fall outside the 90% range of the cdf. data for all combinations of mirnas and scoring models are available in the accompanying web document μrnall comparison of the l score approach to threshold filtering comparison of our l score method to binary threshold filtering on mirna hairpin descriptors showed superior performance of the l classifier. for sets of mirna and genomic hairpins that were filtered at the bordering value between the s = and s < fractions for all descriptors, values for the performance parameters sensitivity, specificity and selectivity were obtained. next, we kept either sensitivity or specificity constant, assessed at which l score this parameter was equalled and compared the other performance parameters. in both cases, our scoring model approach outperformed threshold filtering. when fixed at sensitivity, the scoring model approach achieved 17% better. sensitivity was measured on all metazoan mirna hairpins instead of on c. elegans mirna hairpins because of the inaccuracy caused by the limited number of mirnas in the c. elegans set. a sensitivity measured on the taxonomic set metazoa b specificity measured on the set of, genomic hairpins in c. elegans c selectivity calculated with sensitivity on metazoan mirnas and specificity measured on c. elegans genomic hairpins d minimal l score of the scoring model metazoa for which the performance of threshold filtering performance is equalled predicting hairpins from a genomic sequence we developed a procedure for predicting hairpin structures from genomic sequences using vmatch. the algorithm detects degenerate palindromic repeats and is therefore able to recover known mirna hairpins with very high sensitivity. to benchmark the procedure, we predicted hairpin structures in the genomes c. elegans and four viruses: epstein-barr virus, mareks disease virus, human cytomegalovirus and kaposi sarcoma-associated herpesvirus. the number of recovered, known mirna hairpins, number of identified hairpins and percentage and absolute number of non-overlapping hairpins on unique loci are given for three different l score criteria for the scoring model metazoa, for both mirna and genomic hairpins. a identified mirna hairpins/number of known mirna hairpins in genome in mirbase version. b percentage of mirna or genomic hairpin loci that have at least a certain l-score for scoring model metazoa. c mirna hcmv-mir-ul148d could not be mapped on the genomic sequence of hcmv. d mirna kshv-mir-k12-10b could not be mapped on the genomic sequence of kshv. in the four viral genomes, hairpins were identified, including all known mirnas hairpins of these viruses. in c. elegans,, hairpins were predicted and only four out of known mirnas hairpins were missed. when benchmarking the performance of the hairpin identification with the mirbase entries of all metazoan mirna hairpins, out of mirna hairpins were recovered. the hairpin prediction algorithm is independent of sequence context. this benchmark is therefore an estimate of the algorithm's good performance on metazoan genomes. similar performance has been reported for other edit-distance based hairpins detection methods. on a genome scale, all these methods yield around – hairpins per single stranded mb of sequence. these hairpins are predominantly overlapping and nested. analyses of mirna hairpin candidates in viral genomes the data in table show that only – % of the indentified hairpin loci in four viral genomes have a high l score. this corresponds to 69– loci per genome. in addition, 83–100% of all known mirna hairpins comply with this threshold for l. out of hairpins predicted in the genome of ebv, only hairpins, originating from unique loci, had an l score of. ten of these were experimentally validated mirna loci. further support for our mirna prediction and scoring method comes from recently discovered mirnas in the mdv genome that were not included in mirbase. all five novel mirnas were present in the set of here predicted hairpins and three of these had l score of. the unique loci in mdv with an l score of collapsed into eight unique sequences due to a large inverted repeat. out of these eight, all five loci that did not overlap with annotated exons corresponded to known mirna loci. the two examples show that most hairpins in viral genomes with high l score are true mirna hairpins and that the absolute number of hairpin loci with high l scores is small. this allowed us to manually examine the remaining, non-mirna loci with high l scores, using additional filtering criteria for genomic location such as proximity to known mirnas and intronic position. among the remaining loci in mdv with l ≥, one appeared to be located in the transcribed strand of an intron and two others closely flanked the mdv1-mir-m gene in the same orientation. similarly, out of the remaining ten ebv loci with l =, two candidate mirnas were located directly upstream and amidst a cluster of eleven known mirnas in an intronic region of the bart gene. mining the c. elegans genome for putative mirna hairpins using the scoring model metazoa, the genome of c. elegans was searched for potentially novel mirna hairpins. for the set of, genomic hairpins, a cut-off value l ≥ resulted in a reduction of the number of candidate mirna loci to. for l = only hairpins loci remained, but the sensitivity measured from retrieval of known mirna hairpins was only 34%. nevertheless, this shows that filtering criteria in addition to the l score are required prior to experimental evaluation of candidate mirnas. such criteria may include the use of annotation data or genomic context. it has been suggested, for example, that metazoan mirnas do not overlap with exons. indeed, in the annotation used here, manual inspection of the genomic position of known mirnas of c. elegans showed that only two hairpins overlap with annotated exons. another very selective criterion is similarity to a known mature mirna. we used this criterion such that similarity should be present in the stem of the hairpin and cover at least a nt overlap with at most three mismatches. this resulted in a reduction to only hairpin loci. another property of many mirnas is their clustered occurrence, with from mirnas in c. elegans separated by less than kb. this criterion limited the number of hairpin loci to. an example of a less selective criterion is removing all hairpins that fall in highly repetitive genomic areas. a catalogue of repeat regions can be obtained by an algorithm as tandem repeats finder. additional selection can be accomplished with threshold filtering using the same descriptors already used in our scoring model. besides translating mirna hairpin properties into a statistic for relative rating, as done in calculating the l score, a descriptor can be used as a binary decision criterion: below the threshold, the hairpin is rejected as potential candidate; above it is included. which descriptor to use for further filtering is in the hands of the individual researcher and may depend on the data studied. in the following, we provide two examples of such filtering using seven individual descriptors: four based on structure and three based on sequence complexity. except for stem length, all individual thresholds fall within their s < fractions and separately reject at most three c. elegans mirna hairpins. this ensemble of thresholds excludes low-complexity sequences, captures palindromic repeats with limited degeneracy and should comprise the vast majority of mirnas. in total, only six c. elegans mirna hairpins fail this filter and the same sensitivity is achieved on all metazoan mirna hairpins. only 30% of the set of genomic hairpins in c. elegans passes this filter, representing a selectivity of. a rejected c. elegans mirna hairpins by this step alone b remaining cumulative number of c. elegans mirna hairpins; remaining cumulative number of genomic hairpin loci c similarity to a metazoan mature mirna of at least nt length with at most three mismatches d cel-mir- is fully located in the final exon of y105e8a.16; cel-mir- is largely located in the 3'utr of zk, but overlaps nt with the final exon e at most nt overlap with a repeat identified by tandem repeats finder f similarity with mature mirna may have at most nt overlap with hairpin loop coordinates and at least nt of the stem must separate the similarity from the end of the hairpin. criteria are set according to the biological model of mirna maturation from hairpins. in the following examples, filtering on l score was combined with filtering on either genomic context or on a similarity threshold to known metazoan mature mirnas. goal of these filtering protocols was to achieve sets feasibly sized for manual inspection and/or laboratory evaluation. the protocols comply with characteristics of mirnas mentioned above: occurrence in clusters and presence in families. "clustered" and "similar" resulted in lists of and candidate mirna loci, respectively, that were manually inspected. the most compelling cases among these are presented in figure and figure figure shows a cluster of hairpins of which several have l = starting kb downstream of cel-mir- figure shows two conspicuous hairpins that share similarity with the two known mature mirnas cel-mir- and cel-mir-. the multiple alignment of the four hairpin sequences revealed the characteristic camel-shaped conservation pattern that is often observed between related mirnas: high or perfect conservation in the stem of the pre-mirna hairpins, low conservation in the hairpin loop and the up- and downstream stem sequences. the 5' seed sequences of both mature mirnas are exactly conserved in the novel hairpins, suggesting that hairpins, and, are likely members of the mirna families to which cel-mir- and cel-mir- belong. furthermore, candidate, is located in the 12th intron of the gene f54f, for which the c. elegans unigene set provided evidence of transcription. cel-mir- and cel-mir- were predicted by comparative computational approaches and confirmed by a pcr amplification protocol, but their precise mature mirna ends are unknown. recent high-throughput sequencing of mirnas from c. elegans could not confirm the existence of both mirnas. the data presented for the filtering protocols "clustered" and "similar" show that combined filtering on l score, genomic context and threshold filtering allows for compilation of a priority list of candidate mirnas that is amenable to manual inspection and experimental verification. apart from filtering on genomic clustering or similarity to known mirnas, filtering on l score attains the largest data reduction. this shows that the l score was important in compilation of the priority list and demonstrates the added value of our approach for in silico mirna prediction. discussion we here present a new computational strategy for the in silico prediction of mirna hairpins and show the applicability of the method for predicting new candidate mirna hairpins in four viral genomes and in the genome of c. elegans. while using the latter as an example for model construction, the l score method as here optimized for c. elegans is well usable for other metazoan genomes. however, further improvement of performance of the method on different taxonomic groups can be achieved by constructing dedicated scoring models. our strategy aims at minimizing the number of false negative predictions, rather than at minimizing the number of false positive predictions, as proposed in previous studies. focusing on sensitivity rather than specificity should help uncover new classes of mirna molecules in biological systems. hairpins in genomic sequences are identified with the help of an adjusted suffix-tree based method. when the performance of the hairpin prediction was benchmarked on sets of all known mirnas hairpins from viruses and metazoa, all viral mirnas were recovered, of c. elegans mirnas were recovered and out of metazoan mirnas were shown to be recoverable when considered in their genomic context. similar performance was reported for another edit distance-based hairpin identification method. four c. elegans mirnas remained undetected due to the absence of a stringently base-pairing area in their stems. they all had extremely poor l scores, ranking first, third, fourth and eight among the c. elegans mirna hairpins with lowest l scores. none of the four was found in recent high-throughput sequencing datasets, which otherwise retrieved the vast majority of known c. elegans mirnas. this suggests that these four may not be genuine mirnas. if so, the reported performance of our hairpin prediction method is underestimated. the biological variation and evolutionary diversity of various properties of mirna hairpins were captured in a likelihood score l, based on statistics derived from accurately fitted distributions of hairpin characteristics derived from known mirna hairpins. in total hairpin characteristics were defined and analyzed. the l score is a measure for a single hairpin sequence: a descriptor that captures evolutionary conservation in another species is not included. although conservation has proven to be an extremely selective mirna detection criterion, it conflicts with the aim to maximize sensitivity, because of the existence of species-specific mirnas. the strategy was evaluated on genomic hairpins and known mirnas from the c. elegans genome. although details of analyses and results are likely to differ when applied to other genomes and other negative sets of genomic hairpins, major trends and results were shown to be similar. based on analyses of correlation and discriminative power, hairpin characteristics were identified as most selective. comparison of the descriptor scoring model with a binary threshold filtering protocol using the same descriptors shows that a 17% higher selectivity is achieved with the l score strategy. binary decision thresholds on all or even a few descriptors can easily result in a major decrease of sensitivity. in the strategy developed here, l < represents individual sequences that have one or more descriptors with s < indicating that these descriptors have a relatively low probability of occurrence in mirna hairpins because they occur in the tail of their respective distribution. when a descriptor value falls outside the observed range of biological variation, the continuous likelihood score l allows for the compensation of an unlikely score for a single descriptor by likely scores for other descriptors. in such a case, the sequence is not a priori rejected as a mirna hairpin candidate. the l score thus allows for more deviations from'genuine' mirna characteristics than binary selection on the basis of the same characteristics. this is an important improvement over the use of pre-defined thresholds for filtering on single or multiple descriptors published previously. assigning scores to descriptors, as opposed to binary selection on pre-defined thresholds, has also been used in previous work. for example, mirscan employs an heuristic score assignment to seven features and assigns weights based on the relative entropy between known mirna hairpins and genomic hairpins. palgrade uses a statistical distribution by arbitrarily binning the ordered vector of descriptor values. svm kernels achieve descriptor scoring and weighting as part of the svm. novel to the approach here developed is that the score assignment is based entirely on the statistical evaluation of the variation in physical and sequence properties observed in known mirnas and no binary selection prior to building a scoring model is used. the l score is a relative measure of the likelihood that a given hairpin is a mirna hairpin candidate. an important parameter contributing to useful l scores is the number of mirnas used to derive the discriminating statistics of the individual characteristics. a minimum of about a thousand mirna hairpins is required, but results indicate that the larger the available data set, the better the scoring model captures the variation in mirna hairpin characteristics and performs. in the context of machine learning, the input mirna set could be considered a training set, although in the l score derivation no formal'training' is included. it is noteworthy that the evolutionary distance between the species contained in the taxonomic set for a scoring model influences l considerably. in general, the scoring model based on the set that is taxonomically closest to the organism being analyzed performs best. this indicates that over a wide range of characteristics, mirna hairpins within species are substantially more alike than mirna hairpin sequences between less-related species. this should be taken into account when searching for similarity between mirna hairpins from distantly related species. however, we observed that, for example, taxonomic sets that do not contain human mirna hairpins can yield scoring models that accurately identify human mirna hairpins. in addition, descriptor weighting and parameterization appeared to considerably influence the performance of a scoring model. the analyses presented allow the selection of optimal scoring models, with maximal discriminative power to distinguish true mirna hairpins from other genomic hairpins for a selected set and a given data set. however, each set of data, for example in case of a new genome sequence, will require its own analysis to build an optimal scoring model. whereas the analyses started with descriptors, based on extensive correlation and selectivity analyses, a subset model based on descriptors was performing better than the model comprising all descriptors. in view of the importance of the taxonomic composition of the set used in the model, it should be pointed out, that this may reflect a taxonomic bias for metazoan sequences that may not be valid for other taxonomic groups, such as, for example plant mirna hairpins. in the set of most informative descriptors selected, it is remarkable that three descriptors that are generally considered important are not represented: gc content and the mfe randomization descriptors p and z. gc-content is widely used as a pre-filtering step of in silico mirna prediction methods, but is not among the descriptors used in the final scoring models. the gc-content showed the highest variability in the mean over different taxonomic sets, reflecting the apparently large variation in gc-content found among mirna hairpins from different species. any scoring model that includes the fitted distribution of gc-content would disqualify hairpin structures in species containing mirnas with relatively high or low gc-content. also the descriptors p and z, based on mfe randomization shown to be significantly lower for mirnas hairpins than for randomized sequences, were not among the descriptors selected. although p and z ranked among the most selective descriptors, they were excluded because of their strong correlation with the most selective descriptor mfeahl index, in which the mfe is adjusted for hairpin length and gc-content. svms have similar aims as the l-score strategy and perform well in mirna classification. in assessing and comparing the performance of different methods, however, several caveats should be considered. first, methods that use evolutionary conservation perform well on conserved mirnas but fail to detect species-specific or fast evolving mirnas. the importance of the latter should not be underestimated. second, the particular data set on which the performance is achieved is important to the evaluation and comparison of the results from different methods. unfortunately, there is no benchmark set of both positive and negative examples of mirna hairpins available. many methods are tailored on a specific organism and are likely to perform best in that exact context. assembling a set of true negative sequences is particularly challenging: hairpins in non-coding rnas, e.g. the set of trnas as used in, are likely to possess different and more diverse hairpin features than mirna hairpins, whereas a set of genomic hairpins might contain bona fide mirna hairpins. svms explicitly require negative examples for training and testing, whereas the l scoring method uses such a set only for benchmarking purposes. third, data on prediction performance are not reported consistently in literature. our method enables reporting of auc performance as well as sensitivity and specificity values over the entire range of the roc curve. comparison with binary classifiers from other methods therefore requires transformation of the continuous outcome to a binary outcome by choosing an arbitrary threshold for l and using the associated sensitivity and specificity values as measure of the performance. with these caveats in mind, we compared the performance of our method to three leading svm-based methods mipred, rnamicro and mirna svm note that rnamicro is based on multiple sequence alignments. using different positive and negative datasets, these methods report the following values of sensitivity and specificity; 1) mipred: % and %, using human mirnas as positive and human genomic hairpins as negative set; 2) mipred: % and %, using metazoan, non-human mirnas as positive and human genomic hairpins as negative set; 3) rnamicro: 90% and 99%, using metazoan mirna hairpin alignments as positive and shuffled mirna hairpin and trna alignments as negative set, and; 4) mirna svm: 90% and 95%, using human mirnas as positive and random human genomic hairpins as negative set. these performances compare well to the values of % and % obtained in the fold-cross validated performance of our l score model, using metazoan mirna hairpins as positive and randomly selected genomic hairpins from c. elegans as negative set. the performance of the l scoring model is most similar to that of mipred, which does not include sequence conservation as a parameter. an analysis of the performance of our model on sets of genomic hairpins other than those derived for the c. elegans genome is provided as additional file. a major challenge of any svm is understanding its behavior in, for example, a biological context. while svms are known to produce classifiers that perform well in case of unseen data, svms are essentially black-box classifiers. this makes it difficult to judge the relative importance of individual descriptors or to translate results in biologically relevant understanding. as all parameters are embedded in the kernel function of the svm, svm classifiers are also difficult to adjust, although they do not require the pre-selection of parameters required for the l score strategy here presented. classifier selection based on the detailed descriptor analysis presented here may improve future svm approaches. a key advantage of the l score strategy over svms is that the contribution of individual descriptors to a scoring model can be analyzed in a straightforward way by adding or removing a descriptor or changing the parameterization or weight of descriptors. this way the scoring model becomes better tailored to the biologist's needs in a particular research environment.  at the laboratory bench, the criterion that is of most interest is simply how many putative hairpins should be evaluated by experimentation. with current developments in microarray analysis and high-throughput sequencing, the numbers of potential candidates that can be screened with relative ease will increase dramatically. still large numbers of new mirnas may be identified. yet, for the time being, the individual laboratory would like to see as little putative candidates as possible with as high a success rate as feasible. the highest l score is implying that the given hairpin scores are maximal for all descriptors in the model. in the mb large genome of c. elegans, still hairpin loci remain that cannot be ranked further on the basis of l. it implies that relatively large numbers of genomic hairpins comply with all mirna hairpin descriptors, whereas it is unlikely that they all generate mature mirnas, given the relative small number of currently known c. elegans mirnas. it is likely that this situation will occur in most genomic contexts. if so, several strategies are open. the model parameters could be adjusted, so that the individual descriptor is less likely to get the maximal score. this way, the l score approach will convert to more traditional threshold filtering. given that the analysis requires high sensitivity, it would however be more advantageous to incorporate more biological expert knowledge in the selection process, such as the presence of the hairpin in an intron, sequence similarity to known mirnas, etc. when following this strategy, one has to be aware that the number of novel mirnas that could be discovered is constrained by the filtering on genomic context. for example, in the set of mirnas in c. elegans, occur in singletons when clustered on distance, have no other family representative and are not located in an intron. these numbers can thus be considered as indicative for the fraction of true mirnas that will remain concealed when filtering on genomic context. with the filtering protocols we show that a combination of filtering on l score, genomic context and threshold filtering allows for compilation of a priority list of manageable size for manual inspection and further experimentation. in addition to good performance in comparison with other leading methods and a user-defined selectivity, an additional advantage of the l score approach over threshold filtering and support vector machine classifiers is that the prior analysis of taxonomically defined sets and fitted distributions, correlations, and discriminative power of descriptors gives detailed insight in the behavior of a scoring model and can accommodate expert knowledge. it should therefore appeal to the experimental biologist, despite the fairly time-consuming construction of a suitable scoring model. the scoring model proposed here is independent of the hairpin prediction step and can therefore be coupled to any in silico or experimental mirna prediction method. it can facilitate the analysis of large sets of putative mirna hairpin loci obtained in deep-sequencing efforts of small rnas. the l score approach can be used to rank and select interesting mirna hairpin candidates for downstream experimental analysis in search for novel mirnas. moreover, our in-depth analyses of known mirna hairpins from mirbase, our detailed descriptor analyses and the l score approach here presented are likely to increase the reliability and evidence of mirbase entries and will help to further increase the biological relevance of the mirbase repository. 
moreover, the in-depth analyses of mirna hairpins descriptors preceding and determining the l score outcome could be used as an extension to mirbase entries to help increase the reliability and biological relevance of the mirna registry. we show that the majority of previously identified mirna hairpins have high l scores, that the method outperforms mirna prediction by threshold filtering and that it is more transparent than svm classifiers. the l score is applicable as a prediction classifier with high sensitivity for novel mirna hairpins. we here propose a new strategy for mirna hairpin prediction in which the likelihood that a genomic hairpin is a true mirna hairpin is evaluated based on statistical distributions of observed biological variation of properties of known mirna hairpins. the l-score approach can be used to rank and select interesting mirna hairpin candidates for downstream experimental analysis when coupled to a genome-wide set of in silico-identified hairpins or to facilitate the analysis of large sets of putative mirna hairpin loci obtained in deep-sequencing efforts of small rnas. using a dataset of known mirna hairpins from the mirbase database and an exhaustive set of genomic hairpins identified in the genome of caenorhabditis elegans, a subset of most informative descriptors was selected after detailed analysis of correlation among and discriminative power of individual descriptors. these distributions are transformed into a single and continuous outcome classifier called the l score. the number of known mirna hairpins registered in the mirbase database is rapidly increasing, but recent reports suggest that many mirnas with restricted temporal or tissue-specific expression remain undiscovered. micrornas, short ~21-nucleotide rna molecules, play an important role in post-transcriptional regulation of gene expression.
 micrornas, short ~21-nucleotide rna molecules, play an important role in post-transcriptional regulation of gene expression. the number of known mirna hairpins registered in the mirbase database is rapidly increasing, but recent reports suggest that many mirnas with restricted temporal or tissue-specific expression remain undiscovered. various strategies for in silico mirna identification have been proposed to facilitate mirna discovery. notably support vector machine methods have recently gained popularity. however, a drawback of these methods is that they do not provide insight into the biological properties of mirna sequences.  we here propose a new strategy for mirna hairpin prediction in which the likelihood that a genomic hairpin is a true mirna hairpin is evaluated based on statistical distributions of observed biological variation of properties of known mirna hairpins. these distributions are transformed into a single and continuous outcome classifier called the l score. using a dataset of known mirna hairpins from the mirbase database and an exhaustive set of genomic hairpins identified in the genome of caenorhabditis elegans, a subset of most informative descriptors was selected after detailed analysis of correlation among and discriminative power of individual descriptors. we show that the majority of previously identified mirna hairpins have high l scores, that the method outperforms mirna prediction by threshold filtering and that it is more transparent than svm classifiers.  the l score is applicable as a prediction classifier with high sensitivity for novel mirna hairpins. the l-score approach can be used to rank and select interesting mirna hairpin candidates for downstream experimental analysis when coupled to a genome-wide set of in silico-identified hairpins or to facilitate the analysis of large sets of putative mirna hairpin loci obtained in deep-sequencing efforts of small rnas. moreover, the in-depth analyses of mirna hairpins descriptors preceding and determining the l score outcome could be used as an extension to mirbase entries to help increase the reliability and biological relevance of the mirna registry. 