BACKGROUND
with the discovery of mirnas the traditional view of rna as pure helper molecules in protein biogenesis has changed radically.
mirnas belong to a class of single-stranded, non-coding rna  with only 21– <dig> nt in sequence length.
they are directly involved in downregulation of gene expression at the post-transcriptional level, i.e., they act as negative regulators of translation, in multi-cellular animals and plants, and also appear in viruses .
according to the current understanding of mirna biogenesis, the primary mirna  transcript is cleaved into a 60– <dig> nt long precursor sequence by the drosha/pasha complex.
the pre-mirna is transported into the cytoplasm by exportin  <dig> and cleaved by dicer into the mature mirna.
in the risc  these molecules regulate expression of target genes by binding to complementary sites on the messenger rna .
this causes either cleavage and degradation of the mrna or just suppresses its translation into a protein.
the mirna precursor sequence folds into the typical hairpin stem-loop structure  which is considered to be the most important indicator in the maturation process.
rna folding is determined mainly by hydrogen bonds between complementary base pairs , and the wobble pair g-u.
basically, rnas form loops or bulges by unpaired bases and continuous segments of base pairings  as secondary structure components.
the structure of rna molecules is key to their type and function.
simpler computational approaches to discover mirna precursors in human or animals strongly rely on sequence homology to known mirnas  <cit>  or on sequence profiles  <cit> .
other algorithms have been based on characteristic secondary structure features and/or evolutionary conservation among different species  <cit> .
wang et al.
<cit>  align both the secondary structure and the sequence of known mirna precursors.
some methods consider the genomic context of mirna precursors by using conservation patterns of the flanking sequences  <cit>  or their appearance in clusters  <cit>  as additional search criteria.
berezikov et al.
<cit>  use phylogenetic shadowing to derive a general conservation profile over mirna precursor and flanking sequences.
this profile is used in combination with a structure filter to search for novel mirnas.
all these methods make use of comparative genomics information.
in contrast, ab initio prediction methods are able to predict mirnas in a single genome without using comparative sequence analysis or requiring sequence or structure conservation.
this enables the identification of completely new mirnas for which no close homologs are known.
it is estimated that the number of non-conserved mirnas may be relatively large  <cit> .
in  <cit>  a support vector machine  is trained on frequencies of predefined structure-sequence triplets.
the authors found a significantly higher specificity than when using counts of structure triplets only.
another feature-based svm approach  <cit>  uses nucleotide and base pair frequencies as input features in addition to lengths and distances of certain mirna structure elements.
nam et al.
<cit>  combine sequential and structural mirna characteristics into a hidden markov model  to identify distant homologs.
helvik et al.
<cit>  employ two svm classifiers trained on both sequence and structure features.
the first-level svm predicts drosha processing sites which are used by the second-level svm for an improved prediction of mirna genes.
here we introduce an ab initio method that relies only on characteristic patterns found or not found in the predicted secondary structure of mirna precursors , while ignoring the nucleotide sequence completely.
terminal loop and flanking sequences of the precursor occur to be more variable  than the stem sequences  <cit> , probably because of a minor importance during maturation.
the mature sequence in the stem, however, is rather short and relatively specific to the binding sites on the target mrna and, thus, to mirna function.
this leaves the question, to what extent characteristic sequence patterns may be shared by currently known and unknown mirnas.
we don't claim that sequence information can not be useful for de novo mirna finding, but demonstrate what is possible without.
we apply linear genetic programming   <cit>  to develop classifier programs.
each program incorporates and combines multiple regular expressions  that are matched against the input sequence.
here res represent powerful structure motifs which may reveal new knowledge about mirna precursors.
another advantage is that the method makes almost no assumptions about mirnas, i.e., it does not require previous knowledge about concrete structural features besides the training data.
in particular, the patterns searched for do not have to be predefined, but are adapted automatically .
because motif matching is position-independent, there is also no need to preselect candidate hairpins.
the overall method for finding mirna structures by scanning genome regions, named mirpred, may be summarized in five steps:
a fixed-length window is shifted in regular steps over the input sequence and its secondary structure sequence is predicted.
non-mirna structures are filtered out based on free energy and number of base pairings .
the core method applies several classifier programs to a windowed structure sequence and combines their predictions by voting with threshold.
double matches by overlapping sequence windows are detected and removed.
the predicted mirna candidates are filtered using a stricter threshold, e.g., on the number of successive matches around their genome location .
the general motivation to combine multiple predictions is to increase confidence.
here an ensemble of  <dig> classifiers was trained on known mirnas in the human genome.
this number was necessary to achieve a specificity of  <dig>  percent if all classifiers have to agree on a positive decision of the ensemble.
a low false positive rate is preferable to a low false negative rate, when scanning wider genome regions for new mirnas.
a higher proportion of candidate hairpins, instead, might come along with too many false positive predictions.
RESULTS
data preparation
machine learning methods derive classification models or rules from known positive and negative examples.
our predictors were trained and are applied on fixed-length example sequences .
the positive set is composed of all  <dig> human mirna hairpin sequences reported in mirbase   <cit> .
all mirnas in mirbase are either verified experimentally or by comparative analysis, i.e., have easily identifiable homologs in other closely-related species.
a  <dig> nt wide sequence window is centered and extracted around each known mirna hairpin in the human genome .
that is, smaller hairpins are extended, while longer hairpins are cut equally at both ends.
note that many stem-loop sequences reported in mirbase are longer than the actual precursor  and contain flanking material from the primary transcript.
the reverse complementary sequence is used if a mirna is located on the antisense strand.
for the negative examples, we first select  <dig>  random locations in the human genome.
at each position we shift a  <dig> nt wide window  <dig> times in sense direction – using a constant step size of  <dig> nt – and extract the subsequence of each window.
the resulting  <dig>  fixed-length and partly overlapping sequences simulate the input situation for the predictors when applied for scanning genome regions.
a higher number of negative samples is needed because of the higher diversity of non-mirna structures.
moreover, it is relatively unlikely to include a significant proportion of real mirnas in this way, also because of their assumed low frequency in the genome.
the rna secondary structure  of all extracted nucleotide sequences is predicted using rnafold  at default temperature 37°c and with default settings.
figure  <dig> gives an example of  <dig> successive sequence windows during scanning and their corresponding stem-loop structures which are strings of base pairings ") and non-paring bases .
it is seen that some substructures are more stable, i.e., independent of the window position, than others.
prefiltering of stem-loop structures
both data sets are prefiltered to rule out structures which are quite likely non-mirnas.
a candidate structure must meet three relatively weak conditions:  minimum  <dig> base pairings in the stem arm of the hairpin structure including the wobble pair g-u;  maximum - <dig> kcal/mol free energy.
these thresholds derive from the lowest number of base pairing and the highest free energy found among known human pre-mirnas.
both conditions must be met by the structure of the central  <dig> nt sequence in the scanning window .
this is approximately the size and location of the mirna precursor, ignoring the  <dig> nt extensions from the primary sequence.
in doing so, only  <dig>  of the positive examples  but  <dig>   negative examples are excluded.
note that prefiltering is not essential for the application of our motif-based gp classifiers.
actually, we found that it affects the final set of predicted candidates only slightly.
that is, the classifiers have learned to reject the prefiltered structures even though they have not been exposed to such during training.
nevertheless, prefiltering is important for a reduction and better selection of the training examples.
different arguments may be found for using a scanning window of  <dig> nt:  the ~ <dig> nt long pre-mirna sequence may not always be perfectly aligned in the window center.
short single-stranded extensions from the primary transcript flanking both ends of the precursor are argued to carry relevant structural information for drosha processing  <cit> .
the secondary structure of a  <dig> nt region following the mature duplex has been shown to be conserved  <cit> .
larger windows may include too much of the pri-mirna structure.
folding of mirna precursors appears to be less sensitive to a larger window size than non-mirna structures.
classification of stem-loop structures
the motif-based genetic programs  act as predictors that return a binary decision about whether an input sequence/structure contains a potential pre-mirna or not.
predictions from multiple classifiers  are combined by voting with threshold, i.e., the minimum number of individual decisions required for an overall positive decision.
higher thresholds yield fewer structures predicted as mirnas, but with a higher confidence.
the roc curve in figure  <dig> shows the performance of the ensemble classifier for different voting thresholds.
values are reported for an independent negative test set of  <dig>  windowed sequences  and for all positive examples .
majority voting  shows rather balanced prediction accuracies on the negative  and positive  examples.
such a configuration is appropriate if one wants to decide on certain candidate sequences as, e.g., suggested by other methods.
when searching wider genome regions for new mirnas, however, a higher specificity is desirable to keep the hit rate and number of potentially false positives low.
voting with maximum threshold  requires that all individual classifiers must vote "yes" and achieves a specificity of above  <dig>  percent.
this results in  <dig>  positive predictions out of  <dig>  negative structures, excluding  multiple matches of directly successive windows.
the small increase in specificity is paid by a more significant drop in sensitivity to around  <dig> percent here.
a certain amount of missed true positives is acceptable, if new mirnas are predicted with a higher confidence instead.
the performance of the individual classifiers  is at around  <dig>  percent specificity and  <dig> percent sensitivity.
however, this also means an almost  <dig> times higher rate of  positive predictions.
cross-validation test
in a separate experiment five-fold cross-validation was applied to verify the performance of the classifier programs.
because gp is a probabilistic method,  <dig> independent gp runs were performed for each of the  <dig> positive training sets and the best program on each set was selected.
the negative training sets were selected as described in methods.
on average, sensitivity remains at  <dig> percent over all human mirnas and drops down to  <dig> percent on the respective set of mirnas left out for testing.
specificity remains at an average of  <dig>  percent over the  <dig>  negative test examples.
both values – specificity and sensitivity – compare well to what has been previously reported for other comparable ab initio methods, including both pioneering approaches  <cit>  and second generation predictors  <cit> .
two very recent articles, officially published after the submission of our paper, report high performance values for feature-based classifiers.
kwang loong and mishra  <cit>  achieve around  <dig> percent specificity at  <dig>  percent sensitivity on human mirnas.
their method applies a svm with gaussian radial basis function  kernels and an improved extraction of structural and sequential features.
jiang et al.
<cit>  report even  <dig> percent sensitivity with about the same specificity , found, however, by resampling over a training set with relatively few positive and negative examples .
these values reduce to  <dig> sensitivity and  <dig> percent specificity when testing the method on an independent set of positive and negative examples.
direct comparisons with performance values from the literature must be taken carefully, of course, due to different information, data sets, and prefilters used.
also note that we favor a specificity-sensitivity tradeoff towards higher specificity in this paper.
mirnas of the same family are given names with the same  number but different types of suffixes that relate to the similarity of the mature sequence  <cit> .
numeric suffixes  indicate that the mature sequences are identical.
lettered suffixes  indicate that there are few mutations in the mature part.
to exclude the influence of same-family members on the cross-validation results, we  remove all human mirnas from each left-out test set, which have a member of the same family in the respective training set, and  keep only one member of each family in a test set.
this reduces the average test set size to  <dig> .
the average sensitivity is affected only slightly and is still around  <dig> percent .
performance on other mirna data sets
to validate our ensemble classifier on different sets of positive examples, we extracted fixed-length windows centered around known mirna sequences in mouse and rat, as described above for human.
there are  <dig>  mouse  mirna hairpins reported in mirbase  <dig>  – with known genome location and without double sequences.
we exclude  <dig>  which have an identical precursor in human.
these have been found by matching the central  <dig> nt – the approximate precursor sequence – against the full human windows.
our method correctly predicts  <dig>  percent of all mirnas in mouse  with the highest confidence, i.e.,  <dig> percent agreement between all classifiers.
if minimum  <dig> percent agreement is required for a positive decision the classification rate increases to  <dig>  percent.
only  <dig>  mouse  mirnas have no member of the same family in human, due to the high sequence conservation of  mirnas.
<dig>  percent of these are found with maximum voting threshold and  <dig>  percent with majority voting.
this also demonstrates that our classifiers while trained on human data are able to generalize to mirnas of other species.
in addition, we test the performance of our combined classifier on  <dig> new human mirna sequences in mirbase  <dig>  of which  <dig> are founding members of new mirna families.
from the first set,  <dig> percent are found with maximum confidence and  <dig> percent with confidence ≥ <dig> percent.
for the second set, these numbers drop to  <dig> and  <dig>  respectively.
comparing the new structure sequences by their string edit distance  <cit>  reveals that some are quite different to any previously known human precursor structure or belong to previously rather underrepresented structure classes  with, e.g., larger asymmetric bulges in the stem arm.
microrna identification during genome scanning
most mirna genes are located in dna regions which previously have been considered as non-coding regions, including intergenic regions and introns.
especially intronic mirnas seem to be much more frequent than previously thought  <cit> .
many mirnas appear in clusters on the genome, either in introns of a host gene or in polycistronic transcripts  <cit> .
such clusters are likely transcribed together and usually control mrnas of related functions.
therefore, genomic regions around known mirna locations are particularly promising for finding new mirnas  <cit> .
as a more realistic test scenario, we scan regions on chromosome  <dig> which has the highest number of validated mirnas among all human chromosomes.
the  <dig> mirnas are grouped into  <dig> clusters with a minimum distance of  <dig> kilobases.
the  <dig> nt wide scanning window is moved in  <dig> nt steps, starting  <dig> kb upstream of each cluster and ending  <dig> kb downstream.
the prefilter already identifies  <dig>   from the total  <dig>  structure sequences as negatives.
the combined classifier finds  <dig> positive predictions  which is about twice as many as for random locations used above, indicating a higher number of true positive mirnas.
after removing double matches by overlapping windows these reduce to  <dig>  of which  <dig> are rediscovered known mirnas .
the remaining  <dig> were not filtered out beforehand and all lie on the sense strand .
this leaves  <dig> candidates as potentially new mirnas.
we can use the results for the random locations – which are more likely true negatives – to estimate the number of real mirnas out of all positive matches here.
of the  <dig> hits approximately  <dig> ×  <dig>  808/ <dig>   <dig> =  <dig> are likely false positives, while the remaining  <dig> -  <dig> =  <dig> are potentially real.
excluding the found known mirnas leaves around  <dig> to be true positives.
because it would be counterintuitive to scan regions around known mirnas without using their information for finding new ones, mirnas on chromosome  <dig> are part of the training set here.
for comparison reasons, we trained another ensemble classifier without using these  <dig> mirnas.
its sensitivity is only a little lower on chromosome  <dig>  and slightly better on all human mirnas.
one has to note here that neither the composition nor the size of the ensembles are particularly optimized.
postfiltering and analysis of mirna candidates
additional criteria may be applied on the positive predictions to obtain less mirna candidates, that are more likely true.
we focus on structural aspects again, including the free energy of matching structures and the number of directly successive matches of the scanning window.
mirna structures are known to have lower free energy, i.e., to be more stable, than other non-coding or random structures  <cit> .
figure  <dig> compares different frequency distributions over free energies.
the distribution of all  <dig> predicted mirnas on chromosome  <dig> nicely fits the distribution of all  <dig> known human mirnas.
both distributions are shifted by around - <dig> kcal/mol towards lower free energies, compared to the distribution of all  <dig>  structures tested.
so at least according to their free energy, most candidate structures seem to be real mirnas, including especially those with free energy lower than - <dig>  all energies relate to the folding of only the central  <dig> nt in each sequence windows.
this is also why the free energy of  <dig> human mirnas falls below - <dig> kcal/mol.
the number of directly successive sequence windows is measured in two different ways.
figure  <dig> shows the frequency distribution over the number of successive matches by the sequence window, separately for the  <dig> unknown hits and the  <dig> known hits.
only full matches are counted, meaning that the corresponding structure must be predicted positively by all  <dig> classifiers.
known  mirna locations match more frequently during scanning than unknown locations .
more than  <dig> percent of the unknown candidates match only once, while this is true for only around  <dig> percent of the known candidates.
on the other hand, around  <dig> percent known ones, but only  <dig> percent unknown ones match three times or more.
this shows that mirna structures are more independent from their position in the scanning window than other structures and is another indicator for their above-average stability, besides a lower free energy.
here we only note that we found similar distributions of successive matches  over the  <dig> mirnas redetected by the ensemble not trained on mirnas from chromosome  <dig> and  when scanning over the  <dig> new mirnas in mirbase  <dig>  .
that is, clearly more mirnas are predicted with at least three matches than with only one match.
a more detailed picture is given in figure  <dig> where the distributions also include partial matches by any number of classifiers.
depending on the proportion of positive predictions, full matches count  <dig> and partial matches <  <dig>  these values are summed up from three window shifts before to three window shifts after a full match or a series of full matches.
according to this distribution,  <dig> percent of the unknown predictions fall below  <dig> counts, but less than  <dig> percent of the known ones do.
how similar are the different measures of structural stability?
figure  <dig> reveals a weak, but pronounced correlation between higher number of successive matches and lower free energy of the first matching window.
this implies that the measures still capture sufficiently different aspects and are not interchangeable.
also note that the free energy alone is not an absolutely reliable indicator of structural stability.
one may derive different thresholds from these distributions to further select the  <dig> unknown predicted structures.
for instance, a higher maximum free energy threshold of - <dig> would leave only  <dig> candidates.
when applying an additional minimum threshold of  <dig> on the number of matches  the number of candidates reduces to  <dig>  this is about the number of true positives estimated in the previous section.
also note that both thresholds are still passed by the vast majority  of known predicted mirnas on chromosome  <dig>
transcription
a necessary precondition for a mirna candidate to be true is that its genomic location is transcribed.
a large number of transcripts is known not to be translated into proteins, but not all of these are necessarily functional.
non-coding rnas not only occur between coding genes, but often overlap with coding regions on the same or the opposite strand  <cit> .
alignment of nucleotide sequences to an est library offers one way to identify coding and non-coding genes.
expressed sequence tags  are relatively short  and inaccurate  subsequences of transcribed and spliced cdna, synthesized from mature mrna.
more than  <dig> million human ests are now available in the genbank dbest database   <cit> .
this library favors the sampling and, thus, the detection of rare and lowly expressed transcripts.
we use blast  <cit>  with standard settings to search for the  <dig> predicted mirna sequences of  <dig> nt in the dbest database.
about  <dig> percent  match human ests with at least  <dig> percent sequence identity over a minimum alignment length of  <dig> nt.
this compares to around  <dig> percent of all known human mirnas , a value similar enough to provide additional confidence in the correctness of our predictions.
to find out how many candidate sequences lie in introns, we first align all sequence regions that have been scanned on human chromosome  <dig>  to the est library.
if an est alignment is split up into several discontiguous segments, we extract the whole sequence between the two outermost alignments, provided that these are longer than  <dig> nt.
then the intermediate regions are most likely introns which have been spliced out.
a mirna candidate is identified as being intronic, if it aligns to an extended est, but not to the original  est.
in total we found  <dig> percent  of the candidates to match est-defined introns and more than  <dig> percent  / 117) to be transcribed.
by comparison, only  <dig> out of the  <dig> known mirnas on chromosome  <dig> match ests while  <dig> match introns.
knowledge extraction
unlike black-box classifiers, like svms, our gp solutions may be better interpreted and analyzed in terms of the prediction model and the rules learned.
in particular, the contained regular expressions provide an insight into what sets mirnas apart from other structures.
a simple way of interpretation is to extract all structure motifs used in programs and match these separately against all positive and all negative examples.
general rules about how mirna structures should look like or not may be derived from highly distinctive expressions which match either significantly more mirna or non-mirna structures.
in doing so, one has to keep in mind that the expressions were embedded in a more complex classifier structure and used in combination with other res for the final decision making.
for instance, motifs with a positive matching rate above  <dig> percent also match at least  <dig> percent of the negative examples.
a single motif  is not enough to capture all information held in a mirna precursor and matches the structure sequence only in parts .
the terminal loop region  is matched clearly less frequently than the stem regions.
in fact, only few expressions match over the full hairpin loop and even fewer contain subexpressions which determine loop sizes precisely.
the matching frequency is even lower for the flanking sequences .
apparently, these regions are at least less important for finding characteristic structure motifs.
this result is in line with the most distinctive features of mirna precursors and predicted non-mirna structures derived from secondary structure clustering in  <cit> , which are size and number of bulges rather than the terminal loop size.
one explanation may be found in the conservation profile over mirna precursor sequences which is saddle-like  <cit>  and resembles the distribution graph in figure  <dig>  the higher variation in loop and flanking sequences also applies, to a certain extent, to the precursor structure  <cit> .
thermodynamic stability profiling reveals that the structure is apparently less robust in these regions  <cit> .
another reason may be that the secondary structure is predicted less accurately for the terminal loop than for the stem  <cit> .
at least the range of predicted loop lengths may be too wide and variable to be used for a reliable identification of mirnas.
CONCLUSIONS
we introduced a new ab initio method for mirna discovery in human that is purely based on finding distinctive motifs in predicted rna secondary structure.
in doing so, we favored a specificity-sensitivity tradeoff that is shifted towards higher specificity.
combining the predictions from multiple classifiers by voting with maximum threshold  has turned out to be a simple but effective means to increase confidence in and reduce the number of positive predictions and potentially false positives.
<dig>  percent specificity requires an ensemble of  <dig> classifiers here.
sensitivity is still maintained at a level sufficient for genome scanning applications.
another means to increase confidence is to postfilter the predicted mirna candidates by imposing additional criteria.
the robustness of the secondary structure against the position of the scanning window has been proposed as a structural criterion for mirna identification.
the sliding sequence window is more frequently identified as a match over a mirna location than over a non-mirna location.
finally, we collected different statistical and empirical evidence to validate the correctness of our predictions.
all  <dig> mirna candidates structures match the free energy distribution of known mirna precursors that is significantly shifted towards lower free energies, compared to the distribution of non-mirna structures.
approximately one third was estimated to be true positives, i.e., real mirnas or other small rnas of similar structure.
by aligning the candidate sequences to a human est database, we found that above  <dig> percent are most likely transcribed and that around  <dig> percent are located in introns.
the performance of our motif-based gp approach has been found at least competitive to presently existing methods for ab initio mirna identification.
more general advantages over svm-based methods include:
less assumptions are made about how a pre-mirna structure has to look like.
the patterns  used for classification are not predefined, but are automatically derived from positive and negative examples during training .
svms, instead, requires certain "rules" to be set up which determine how a structure sequence is transformed into a feature vector.
a preselection of candidate hairpins is not required since regular expressions are relatively independent from the absolute position of matching substructures.
svm classification, instead, requires hairpin-like structures to measure certain quality features.
because gp is a probabilistic method, a gain in performance is possible by combining multiple classifiers even if these have been trained on the same data.
deterministic svms only produce a single solution in this case.
our motif-based programs give a more direct and unbiased insight into what rules have been learned.
mostly the stem region of hairpin structures is used for mirna prediction, in contrast to loop region and flanking sequences.
a more detailed analysis of programs and structure motifs is a subject of our ongoing research.
as indicated above, ab initio mirna finding, by definition, does not apply homology search or conservation.
for instance, we did not prefilter the input sequences by scanning only regions conserved between human and, e.g., mouse or rat.
only  <dig>  of the potential mirna sequences found in human are highly conserved in mouse , i.e., with above  <dig> percent sequence identity over an alignment of at least  <dig> nt.
in general, it may be doubted whether one computational method alone is sufficient to estimate reliably how many mirnas actually exist in the human genome.
<dig>  percent specificity is, of course, not the end of the story.
the number of predictions produced is still large when scanning the complete genome and it may be questioned if these can be all real mirnas.
to find the true positives may still require additional support by other computational and/or experimental approaches, testing other criteria than the precursor structure.
nevertheless, identification methods like the one presented here serve as an important step toward filtering potential pre-mirna candidates.

 with the discovery of mirnas the traditional view of rna as pure helper molecules in protein biogenesis has changed radically. mirnas belong to a class of single-stranded, non-coding rna with only 21– nt in sequence length. they are directly involved in downregulation of gene expression at the post-transcriptional level, i.e., they act as negative regulators of translation, in multi-cellular animals and plants, and also appear in viruses. according to the current understanding of mirna biogenesis, the primary mirna transcript is cleaved into a 60– nt long precursor sequence by the drosha/pasha complex. the pre-mirna is transported into the cytoplasm by exportin and cleaved by dicer into the mature mirna. in the risc these molecules regulate expression of target genes by binding to complementary sites on the messenger rna. this causes either cleavage and degradation of the mrna or just suppresses its translation into a protein. the mirna precursor sequence folds into the typical hairpin stem-loop structure which is considered to be the most important indicator in the maturation process. rna folding is determined mainly by hydrogen bonds between complementary base pairs, and the wobble pair g-u. basically, rnas form loops or bulges by unpaired bases and continuous segments of base pairings as secondary structure components. the structure of rna molecules is key to their type and function. simpler computational approaches to discover mirna precursors in human or animals strongly rely on sequence homology to known mirnas or on sequence profiles. other algorithms have been based on characteristic secondary structure features and/or evolutionary conservation among different species. wang et al. align both the secondary structure and the sequence of known mirna precursors. some methods consider the genomic context of mirna precursors by using conservation patterns of the flanking sequences or their appearance in clusters as additional search criteria. berezikov et al. use phylogenetic shadowing to derive a general conservation profile over mirna precursor and flanking sequences. this profile is used in combination with a structure filter to search for novel mirnas. all these methods make use of comparative genomics information. in contrast, ab initio prediction methods are able to predict mirnas in a single genome without using comparative sequence analysis or requiring sequence or structure conservation. this enables the identification of completely new mirnas for which no close homologs are known. it is estimated that the number of non-conserved mirnas may be relatively large. in a support vector machine is trained on frequencies of predefined structure-sequence triplets. the authors found a significantly higher specificity than when using counts of structure triplets only. another feature-based svm approach uses nucleotide and base pair frequencies as input features in addition to lengths and distances of certain mirna structure elements. nam et al. combine sequential and structural mirna characteristics into a hidden markov model to identify distant homologs. helvik et al. employ two svm classifiers trained on both sequence and structure features. the first-level svm predicts drosha processing sites which are used by the second-level svm for an improved prediction of mirna genes. here we introduce an ab initio method that relies only on characteristic patterns found or not found in the predicted secondary structure of mirna precursors, while ignoring the nucleotide sequence completely. terminal loop and flanking sequences of the precursor occur to be more variable than the stem sequences, probably because of a minor importance during maturation. the mature sequence in the stem, however, is rather short and relatively specific to the binding sites on the target mrna and, thus, to mirna function. this leaves the question, to what extent characteristic sequence patterns may be shared by currently known and unknown mirnas. we don't claim that sequence information can not be useful for de novo mirna finding, but demonstrate what is possible without. we apply linear genetic programming to develop classifier programs. each program incorporates and combines multiple regular expressions that are matched against the input sequence. here res represent powerful structure motifs which may reveal new knowledge about mirna precursors. another advantage is that the method makes almost no assumptions about mirnas, i.e., it does not require previous knowledge about concrete structural features besides the training data. in particular, the patterns searched for do not have to be predefined, but are adapted automatically. because motif matching is position-independent, there is also no need to preselect candidate hairpins. the overall method for finding mirna structures by scanning genome regions, named mirpred, may be summarized in five steps: a fixed-length window is shifted in regular steps over the input sequence and its secondary structure sequence is predicted. non-mirna structures are filtered out based on free energy and number of base pairings. the core method applies several classifier programs to a windowed structure sequence and combines their predictions by voting with threshold. double matches by overlapping sequence windows are detected and removed. the predicted mirna candidates are filtered using a stricter threshold, e.g., on the number of successive matches around their genome location. the general motivation to combine multiple predictions is to increase confidence. here an ensemble of classifiers was trained on known mirnas in the human genome. this number was necessary to achieve a specificity of percent if all classifiers have to agree on a positive decision of the ensemble. a low false positive rate is preferable to a low false negative rate, when scanning wider genome regions for new mirnas. a higher proportion of candidate hairpins, instead, might come along with too many false positive predictions.  data preparation machine learning methods derive classification models or rules from known positive and negative examples. our predictors were trained and are applied on fixed-length example sequences. the positive set is composed of all human mirna hairpin sequences reported in mirbase. all mirnas in mirbase are either verified experimentally or by comparative analysis, i.e., have easily identifiable homologs in other closely-related species. a nt wide sequence window is centered and extracted around each known mirna hairpin in the human genome. that is, smaller hairpins are extended, while longer hairpins are cut equally at both ends. note that many stem-loop sequences reported in mirbase are longer than the actual precursor and contain flanking material from the primary transcript. the reverse complementary sequence is used if a mirna is located on the antisense strand. for the negative examples, we first select random locations in the human genome. at each position we shift a nt wide window times in sense direction – using a constant step size of nt – and extract the subsequence of each window. the resulting fixed-length and partly overlapping sequences simulate the input situation for the predictors when applied for scanning genome regions. a higher number of negative samples is needed because of the higher diversity of non-mirna structures. moreover, it is relatively unlikely to include a significant proportion of real mirnas in this way, also because of their assumed low frequency in the genome. the rna secondary structure of all extracted nucleotide sequences is predicted using rnafold at default temperature 37°c and with default settings. figure gives an example of successive sequence windows during scanning and their corresponding stem-loop structures which are strings of base pairings ") and non-paring bases. it is seen that some substructures are more stable, i.e., independent of the window position, than others. prefiltering of stem-loop structures both data sets are prefiltered to rule out structures which are quite likely non-mirnas. a candidate structure must meet three relatively weak conditions: minimum base pairings in the stem arm of the hairpin structure including the wobble pair g-u; maximum - kcal/mol free energy. these thresholds derive from the lowest number of base pairing and the highest free energy found among known human pre-mirnas. both conditions must be met by the structure of the central nt sequence in the scanning window. this is approximately the size and location of the mirna precursor, ignoring the nt extensions from the primary sequence. in doing so, only of the positive examples but negative examples are excluded. note that prefiltering is not essential for the application of our motif-based gp classifiers. actually, we found that it affects the final set of predicted candidates only slightly. that is, the classifiers have learned to reject the prefiltered structures even though they have not been exposed to such during training. nevertheless, prefiltering is important for a reduction and better selection of the training examples. different arguments may be found for using a scanning window of nt: the ~ nt long pre-mirna sequence may not always be perfectly aligned in the window center. short single-stranded extensions from the primary transcript flanking both ends of the precursor are argued to carry relevant structural information for drosha processing. the secondary structure of a nt region following the mature duplex has been shown to be conserved. larger windows may include too much of the pri-mirna structure. folding of mirna precursors appears to be less sensitive to a larger window size than non-mirna structures. classification of stem-loop structures the motif-based genetic programs act as predictors that return a binary decision about whether an input sequence/structure contains a potential pre-mirna or not. predictions from multiple classifiers are combined by voting with threshold, i.e., the minimum number of individual decisions required for an overall positive decision. higher thresholds yield fewer structures predicted as mirnas, but with a higher confidence. the roc curve in figure shows the performance of the ensemble classifier for different voting thresholds. values are reported for an independent negative test set of windowed sequences and for all positive examples. majority voting shows rather balanced prediction accuracies on the negative and positive examples. such a configuration is appropriate if one wants to decide on certain candidate sequences as, e.g., suggested by other methods. when searching wider genome regions for new mirnas, however, a higher specificity is desirable to keep the hit rate and number of potentially false positives low. voting with maximum threshold requires that all individual classifiers must vote "yes" and achieves a specificity of above percent. this results in positive predictions out of negative structures, excluding multiple matches of directly successive windows. the small increase in specificity is paid by a more significant drop in sensitivity to around percent here. a certain amount of missed true positives is acceptable, if new mirnas are predicted with a higher confidence instead. the performance of the individual classifiers is at around percent specificity and percent sensitivity. however, this also means an almost times higher rate of positive predictions. cross-validation test in a separate experiment five-fold cross-validation was applied to verify the performance of the classifier programs. because gp is a probabilistic method, independent gp runs were performed for each of the positive training sets and the best program on each set was selected. the negative training sets were selected as described in methods. on average, sensitivity remains at percent over all human mirnas and drops down to percent on the respective set of mirnas left out for testing. specificity remains at an average of percent over the negative test examples. both values – specificity and sensitivity – compare well to what has been previously reported for other comparable ab initio methods, including both pioneering approaches and second generation predictors. two very recent articles, officially published after the submission of our paper, report high performance values for feature-based classifiers. kwang loong and mishra achieve around percent specificity at percent sensitivity on human mirnas. their method applies a svm with gaussian radial basis function kernels and an improved extraction of structural and sequential features. jiang et al. report even percent sensitivity with about the same specificity, found, however, by resampling over a training set with relatively few positive and negative examples. these values reduce to sensitivity and percent specificity when testing the method on an independent set of positive and negative examples. direct comparisons with performance values from the literature must be taken carefully, of course, due to different information, data sets, and prefilters used. also note that we favor a specificity-sensitivity tradeoff towards higher specificity in this paper. mirnas of the same family are given names with the same number but different types of suffixes that relate to the similarity of the mature sequence. numeric suffixes indicate that the mature sequences are identical. lettered suffixes indicate that there are few mutations in the mature part. to exclude the influence of same-family members on the cross-validation results, we remove all human mirnas from each left-out test set, which have a member of the same family in the respective training set, and keep only one member of each family in a test set. this reduces the average test set size to. the average sensitivity is affected only slightly and is still around percent. performance on other mirna data sets to validate our ensemble classifier on different sets of positive examples, we extracted fixed-length windows centered around known mirna sequences in mouse and rat, as described above for human. there are mouse mirna hairpins reported in mirbase – with known genome location and without double sequences. we exclude which have an identical precursor in human. these have been found by matching the central nt – the approximate precursor sequence – against the full human windows. our method correctly predicts percent of all mirnas in mouse with the highest confidence, i.e., percent agreement between all classifiers. if minimum percent agreement is required for a positive decision the classification rate increases to percent. only mouse mirnas have no member of the same family in human, due to the high sequence conservation of mirnas. percent of these are found with maximum voting threshold and percent with majority voting. this also demonstrates that our classifiers while trained on human data are able to generalize to mirnas of other species. in addition, we test the performance of our combined classifier on new human mirna sequences in mirbase of which are founding members of new mirna families. from the first set, percent are found with maximum confidence and percent with confidence ≥ percent. for the second set, these numbers drop to and respectively. comparing the new structure sequences by their string edit distance reveals that some are quite different to any previously known human precursor structure or belong to previously rather underrepresented structure classes with, e.g., larger asymmetric bulges in the stem arm. microrna identification during genome scanning most mirna genes are located in dna regions which previously have been considered as non-coding regions, including intergenic regions and introns. especially intronic mirnas seem to be much more frequent than previously thought. many mirnas appear in clusters on the genome, either in introns of a host gene or in polycistronic transcripts. such clusters are likely transcribed together and usually control mrnas of related functions. therefore, genomic regions around known mirna locations are particularly promising for finding new mirnas. as a more realistic test scenario, we scan regions on chromosome which has the highest number of validated mirnas among all human chromosomes. the mirnas are grouped into clusters with a minimum distance of kilobases. the nt wide scanning window is moved in nt steps, starting kb upstream of each cluster and ending kb downstream. the prefilter already identifies from the total structure sequences as negatives. the combined classifier finds positive predictions which is about twice as many as for random locations used above, indicating a higher number of true positive mirnas. after removing double matches by overlapping windows these reduce to of which are rediscovered known mirnas. the remaining were not filtered out beforehand and all lie on the sense strand. this leaves candidates as potentially new mirnas. we can use the results for the random locations – which are more likely true negatives – to estimate the number of real mirnas out of all positive matches here. of the hits approximately × 808/ = are likely false positives, while the remaining - = are potentially real. excluding the found known mirnas leaves around to be true positives. because it would be counterintuitive to scan regions around known mirnas without using their information for finding new ones, mirnas on chromosome are part of the training set here. for comparison reasons, we trained another ensemble classifier without using these mirnas. its sensitivity is only a little lower on chromosome and slightly better on all human mirnas. one has to note here that neither the composition nor the size of the ensembles are particularly optimized. postfiltering and analysis of mirna candidates additional criteria may be applied on the positive predictions to obtain less mirna candidates, that are more likely true. we focus on structural aspects again, including the free energy of matching structures and the number of directly successive matches of the scanning window. mirna structures are known to have lower free energy, i.e., to be more stable, than other non-coding or random structures. figure compares different frequency distributions over free energies. the distribution of all predicted mirnas on chromosome nicely fits the distribution of all known human mirnas. both distributions are shifted by around - kcal/mol towards lower free energies, compared to the distribution of all structures tested. so at least according to their free energy, most candidate structures seem to be real mirnas, including especially those with free energy lower than - all energies relate to the folding of only the central nt in each sequence windows. this is also why the free energy of human mirnas falls below - kcal/mol. the number of directly successive sequence windows is measured in two different ways. figure shows the frequency distribution over the number of successive matches by the sequence window, separately for the unknown hits and the known hits. only full matches are counted, meaning that the corresponding structure must be predicted positively by all classifiers. known mirna locations match more frequently during scanning than unknown locations. more than percent of the unknown candidates match only once, while this is true for only around percent of the known candidates. on the other hand, around percent known ones, but only percent unknown ones match three times or more. this shows that mirna structures are more independent from their position in the scanning window than other structures and is another indicator for their above-average stability, besides a lower free energy. here we only note that we found similar distributions of successive matches over the mirnas redetected by the ensemble not trained on mirnas from chromosome and when scanning over the new mirnas in mirbase. that is, clearly more mirnas are predicted with at least three matches than with only one match. a more detailed picture is given in figure where the distributions also include partial matches by any number of classifiers. depending on the proportion of positive predictions, full matches count and partial matches < these values are summed up from three window shifts before to three window shifts after a full match or a series of full matches. according to this distribution, percent of the unknown predictions fall below counts, but less than percent of the known ones do. how similar are the different measures of structural stability? figure reveals a weak, but pronounced correlation between higher number of successive matches and lower free energy of the first matching window. this implies that the measures still capture sufficiently different aspects and are not interchangeable. also note that the free energy alone is not an absolutely reliable indicator of structural stability. one may derive different thresholds from these distributions to further select the unknown predicted structures. for instance, a higher maximum free energy threshold of - would leave only candidates. when applying an additional minimum threshold of on the number of matches the number of candidates reduces to this is about the number of true positives estimated in the previous section. also note that both thresholds are still passed by the vast majority of known predicted mirnas on chromosome transcription a necessary precondition for a mirna candidate to be true is that its genomic location is transcribed. a large number of transcripts is known not to be translated into proteins, but not all of these are necessarily functional. non-coding rnas not only occur between coding genes, but often overlap with coding regions on the same or the opposite strand. alignment of nucleotide sequences to an est library offers one way to identify coding and non-coding genes. expressed sequence tags are relatively short and inaccurate subsequences of transcribed and spliced cdna, synthesized from mature mrna. more than million human ests are now available in the genbank dbest database. this library favors the sampling and, thus, the detection of rare and lowly expressed transcripts. we use blast with standard settings to search for the predicted mirna sequences of nt in the dbest database. about percent match human ests with at least percent sequence identity over a minimum alignment length of nt. this compares to around percent of all known human mirnas, a value similar enough to provide additional confidence in the correctness of our predictions. to find out how many candidate sequences lie in introns, we first align all sequence regions that have been scanned on human chromosome to the est library. if an est alignment is split up into several discontiguous segments, we extract the whole sequence between the two outermost alignments, provided that these are longer than nt. then the intermediate regions are most likely introns which have been spliced out. a mirna candidate is identified as being intronic, if it aligns to an extended est, but not to the original est. in total we found percent of the candidates to match est-defined introns and more than percent / 117) to be transcribed. by comparison, only out of the known mirnas on chromosome match ests while match introns. knowledge extraction unlike black-box classifiers, like svms, our gp solutions may be better interpreted and analyzed in terms of the prediction model and the rules learned. in particular, the contained regular expressions provide an insight into what sets mirnas apart from other structures. a simple way of interpretation is to extract all structure motifs used in programs and match these separately against all positive and all negative examples. general rules about how mirna structures should look like or not may be derived from highly distinctive expressions which match either significantly more mirna or non-mirna structures. in doing so, one has to keep in mind that the expressions were embedded in a more complex classifier structure and used in combination with other res for the final decision making. for instance, motifs with a positive matching rate above percent also match at least percent of the negative examples. a single motif is not enough to capture all information held in a mirna precursor and matches the structure sequence only in parts. the terminal loop region is matched clearly less frequently than the stem regions. in fact, only few expressions match over the full hairpin loop and even fewer contain subexpressions which determine loop sizes precisely. the matching frequency is even lower for the flanking sequences. apparently, these regions are at least less important for finding characteristic structure motifs. this result is in line with the most distinctive features of mirna precursors and predicted non-mirna structures derived from secondary structure clustering in, which are size and number of bulges rather than the terminal loop size. one explanation may be found in the conservation profile over mirna precursor sequences which is saddle-like and resembles the distribution graph in figure the higher variation in loop and flanking sequences also applies, to a certain extent, to the precursor structure. thermodynamic stability profiling reveals that the structure is apparently less robust in these regions. another reason may be that the secondary structure is predicted less accurately for the terminal loop than for the stem. at least the range of predicted loop lengths may be too wide and variable to be used for a reliable identification of mirnas.  we introduced a new ab initio method for mirna discovery in human that is purely based on finding distinctive motifs in predicted rna secondary structure. in doing so, we favored a specificity-sensitivity tradeoff that is shifted towards higher specificity. combining the predictions from multiple classifiers by voting with maximum threshold has turned out to be a simple but effective means to increase confidence in and reduce the number of positive predictions and potentially false positives. percent specificity requires an ensemble of classifiers here. sensitivity is still maintained at a level sufficient for genome scanning applications. another means to increase confidence is to postfilter the predicted mirna candidates by imposing additional criteria. the robustness of the secondary structure against the position of the scanning window has been proposed as a structural criterion for mirna identification. the sliding sequence window is more frequently identified as a match over a mirna location than over a non-mirna location. finally, we collected different statistical and empirical evidence to validate the correctness of our predictions. all mirna candidates structures match the free energy distribution of known mirna precursors that is significantly shifted towards lower free energies, compared to the distribution of non-mirna structures. approximately one third was estimated to be true positives, i.e., real mirnas or other small rnas of similar structure. by aligning the candidate sequences to a human est database, we found that above percent are most likely transcribed and that around percent are located in introns. the performance of our motif-based gp approach has been found at least competitive to presently existing methods for ab initio mirna identification. more general advantages over svm-based methods include: less assumptions are made about how a pre-mirna structure has to look like. the patterns used for classification are not predefined, but are automatically derived from positive and negative examples during training. svms, instead, requires certain "rules" to be set up which determine how a structure sequence is transformed into a feature vector. a preselection of candidate hairpins is not required since regular expressions are relatively independent from the absolute position of matching substructures. svm classification, instead, requires hairpin-like structures to measure certain quality features. because gp is a probabilistic method, a gain in performance is possible by combining multiple classifiers even if these have been trained on the same data. deterministic svms only produce a single solution in this case. our motif-based programs give a more direct and unbiased insight into what rules have been learned. mostly the stem region of hairpin structures is used for mirna prediction, in contrast to loop region and flanking sequences. a more detailed analysis of programs and structure motifs is a subject of our ongoing research. as indicated above, ab initio mirna finding, by definition, does not apply homology search or conservation. for instance, we did not prefilter the input sequences by scanning only regions conserved between human and, e.g., mouse or rat. only of the potential mirna sequences found in human are highly conserved in mouse, i.e., with above percent sequence identity over an alignment of at least nt. in general, it may be doubted whether one computational method alone is sufficient to estimate reliably how many mirnas actually exist in the human genome. percent specificity is, of course, not the end of the story. the number of predictions produced is still large when scanning the complete genome and it may be questioned if these can be all real mirnas. to find the true positives may still require additional support by other computational and/or experimental approaches, testing other criteria than the precursor structure. nevertheless, identification methods like the one presented here serve as an important step toward filtering potential pre-mirna candidates. 
both their small size and sequence specificity make the detection of completely new mirnas a challenging task. new mirnas have been predicted close to known mirnas on human chromosome all candidate structures match the free energy distribution of mirna precursors which is significantly shifted towards lower free energies. an ensemble of motif-based classifiers achieves percent specificity with sensitivity remaining on an acceptable high level when requiring all classifiers to agree on a positive decision. mirpred is a novel method for ab initio prediction of mirnas by genome scanning that only relies on secondary structure to distinguish mirna precursors from other similar-sized segments of the human genome. among other things, we propose a new criterion to select mirna candidates with a higher stability of folding that is based on the number of matching windows around their genome location. we employed a human est library and found that around percent of the candidate sequences are likely to be transcribed, with around percent located in introns. this cannot be based on sequence information alone, but requires structure information about the mirna precursor. in doing so, it requires less previous knowledge about mirna precursor structures while programs and motifs allow a more straightforward interpretation and extraction of the acquired knowledge. various statistical and empirical evidence is collected to validate the correctness of and increase confidence in the predicted structures. micrornas are short, non-coding rna molecules that are directly involved in post-transcriptional regulation of gene expression. a low false positive rate is considered more important than a low false negative rate, when searching larger genome regions for unknown mirnas. unlike comparative genomics approaches, ab initio approaches are able to discover species-specific mirnas without known sequence homology. we apply a machine learning technique, called linear genetic programming, to develop special classifier programs which include multiple regular expressions matched against the secondary structure sequence. the classifiers are trained on fixed-length sequences as these occur when shifting a window in regular steps over a genome region.
 micrornas are short, non-coding rna molecules that are directly involved in post-transcriptional regulation of gene expression. the mature mirna sequence binds to more or less specific target sites on the mrna. both their small size and sequence specificity make the detection of completely new mirnas a challenging task. this cannot be based on sequence information alone, but requires structure information about the mirna precursor. unlike comparative genomics approaches, ab initio approaches are able to discover species-specific mirnas without known sequence homology.  mirpred is a novel method for ab initio prediction of mirnas by genome scanning that only relies on secondary structure to distinguish mirna precursors from other similar-sized segments of the human genome. we apply a machine learning technique, called linear genetic programming, to develop special classifier programs which include multiple regular expressions matched against the secondary structure sequence. special attention is paid to scanning issues. the classifiers are trained on fixed-length sequences as these occur when shifting a window in regular steps over a genome region. various statistical and empirical evidence is collected to validate the correctness of and increase confidence in the predicted structures. among other things, we propose a new criterion to select mirna candidates with a higher stability of folding that is based on the number of matching windows around their genome location. an ensemble of motif-based classifiers achieves percent specificity with sensitivity remaining on an acceptable high level when requiring all classifiers to agree on a positive decision. a low false positive rate is considered more important than a low false negative rate, when searching larger genome regions for unknown mirnas. new mirnas have been predicted close to known mirnas on human chromosome all candidate structures match the free energy distribution of mirna precursors which is significantly shifted towards lower free energies. we employed a human est library and found that around percent of the candidate sequences are likely to be transcribed, with around percent located in introns.  our motif finding method is at least competitive to state-of-the-art feature-based methods for ab initio mirna discovery. in doing so, it requires less previous knowledge about mirna precursor structures while programs and motifs allow a more straightforward interpretation and extraction of the acquired knowledge. 