micrornas   ( mirnas ) are genome - encoded single - stranded rna molecules of ~22  nt in length , which play a significant role in regulation of gene expression in eukaryotes .
many details on biogenesis and interactions of mirnas are known ( see recent reviews , e.g. , [ 1 , 2 ] ) .
briefly , mirnas can be encoded by mirna genes , but also be generated from different rna transcripts ( e.g. , from introns of protein - coding genes ) .
plant and animal mirnas differ to some extent with respect to biogenesis and structural characteristics but also in their mode of action . in plants ,
most if not all mirnas are transcribed from genes by rna - dependent rna polymerase ii ( polii ) into primary transcripts called pri - mirna ; these transcripts fold into ( possibly imperfect ) stem - loop structures . from the pri - mirna dicer - like ( dcl )
enzymes process the stem - loop structure ( pre - mirna ) , which is usually longer ( ~130  nt ; see below ) than nonplant pre - mirna ( ~86  nt ) , and finally a mirna / mirna * duplex . in the cytoplasm
, the mirna is incorporated into the rna - induced silencing complex ( risc ) , and base - pairing of the mirna with complementary messenger rna ( mrna ) regions leads to mrna degradation or to inhibition of mrna translation .
most plant mirnas base - pair with their respective target mrnas in the coding region with perfect or near - perfect complementarity leading to cleavage ( and degradation ) of the mrnas ; animal mirnas usually base - pair with 3 untranslated regions through imperfect complementarity leading to translation repression .
finding of mirna genes either needs costly experimental approaches  for example , genetics , which led to the detection of the first animal mirnas [ 3 , 4 ] , cloning and sequencing of cdna , or deep sequencing  or computational prediction methods , which facilitate subsequent experimental verification or falsification .
the different properties of mirnas in plants and animals gave rise to different computational approaches ( for reviews see [ 57 ] ) .
most of these tools , however , rely on the following features : the mirna resides in a stem - loop structure , which possess a high thermodynamic stability and does not contain large internal loops or asymmetric bulges at least in the region of the mature mirna . in addition , many tools take into account a phylogenetic conservation of the pre - mirna structure and mirna sequence , which limits the chance to detect non - conserved , evolutionary new mirna genes .
for example , dezulian et al .   identify plant mirna homologs in a set of sequences , given a query mirna , by a sequence similarity search step and a set of structural filters ; pfeffer et al .  
identify dna - viral pre - mirnas , which show neither detectable conservation to other viral pre - mirnas nor to host pre - mirnas , by a search for stable stem - loops and scoring of these according to free energy of folding , base composition , and number of base pairs ; wang et al .   as well as
jones - rhoades and bartel   search for putative mirna / mirna * complexes in the intergenic regions of   arabidopsis thaliana and filter these according to gc content , mismatches in the stem , conservation in the rice genome , and the characteristic stem - loop structure . to our knowledge ,
the only tools for de novo prediction of pre - mirnas in plants are   hhmmir   and   triplet - svm .  
hhmmir calculates first the mfe structure of sequence regions ( using   rnafold in a scanning window approach with window length of less than 500  nt ) , extracts stem - loops that possess at least 10 base pairs , a minimum length of 50  nt , a loop of less than 20  nt and no multiloop(s ) , and finally classifies via a hierarchical hidden markov model ( hhmm ) .
( 96 sequences taken from   mirbase   5 ) and 0.973 for   a. thaliana ( 75 sequences ) .  
triplet - svm calculates by   rnafold the mfe structure of sequences , rejects those with junction(s ) , too few base pairs , and a high free energy ( i.e. , low structural stability ) , parses the remaining structures in  triplets  ( type of nucleotide plus paired or unpaired state of the nucleotide and its two neighbors ) , and finally classifies these features with a support vector machine ( svm ) .
the sensitivity of   triplet - svm is published to be 0.948 for   oryza sativa and 0.92 for   a. thaliana using the same sequences from   mirbase   5 as in the test with   hhmmir . in the following ,
we describe our tool , called   novomir , to detect pre - mirna and mirna / mirna * sequences in a plant genome . for this purpose  
novomir uses a series of filter steps , similar to those mentioned above , followed by a statistical model to discriminate a pre - mirna from all other rnas and by another statistical model to locate the mirna / mirna * complex in a putative pre - mirna .
thresholds and statistical values are learned from sets of true positive sequences ( plant pre - mirnas taken from   mirbase ; ) and true non - mirna sequences ( trnas , 5 s rrna , 5.8 s rrna , mrnas , etc . ) . for detection
,   novomir relies neither on comparative genomics nor on prior knowledge of a mirna target ; thus   novomir allows for searches in single plant genomes as well as in viral or viroid genomes .
sequences of plant pre - mirnas were obtained from different versions of   mirbase [ 15 , 16 ] : version 10.0 contains 1,247 sequences ; the recent version 14 contains 2,030 sequences .
the mean and median length of plant sequences are about ( 150  73 )  nt and 130  nt , respectively ( see figure s1 in supplementary material available online at doi:10.4061/2010/495904 ) ; the shortest pre - mirna is 54  nt in length ( mirbase i d : gma - mir2107 ) and the longest is 932  nt ( cre - mir916 ) .
the mean and median length of nonplant sequences are about ( 88  14 )  nt and 86  nt , respectively ; the shortest pre - mirna is 44  nt in length ( hsa - mir-1973 ) and the longest is 215  nt ( dme - mir-997 ) .
that is , most plant pre - mirnas are longer than animal pre - mirnas and their size range is more diverse .
the sequences of pre - mirnas and mature mirnas are slightly enriched in u   and u plus g , respectively ( see figure s2 ) .
the four nucleotides are not equally distributed at each position along the mirna sequences ( see figure s3 ) :   for example , a u is the preferred 5 nucleotide ( f1,u = 0.65 ) , a g on position 8 ( f8,g = 0.44 ) , and a c on position 19 ( f19,c = 0.52 ) .
the minimum free energy g37c of the secondary structures of pre - mirnas , as calculated by   rnafold   using default parameters , is in a wide range due to the different lengths l and g+c contents fgc of the sequences ( see figure s4 ) ;
normalization of g37c to length and fgc   results in g37c / l = ( 0.45  0.12 ) kcal / mol / nt and g37c / l / fgc = ( 1.02  0.26 ) kcal / mol / nt ; the latter value is significantly lower than that of other rna according to zhang et al . .
we used the 184 pre - mirnas and mature mirnas of   a. thaliana as listed in   mirbase version 10 as the true - positive data set for establishing all thresholds and parameters of   novomir .
sequences containing nucleotides other than a , c , g , u(t ) were discarded . for evaluation of sensitivity we used in addition the plant pre - mirnas and mature mirnas from   mirbase version 14 ( 190 from   a. thaliana and 1,853 from other plants ) .
the sensitivity of   novomir was nearly identical for both data sets ( and also with sequences from version 14  minus those from version 10 ; see supplemental table s1 ) ; thus we refrained from training with different data sets .
as the true - negative data set , we assembled rna sets from the following sources :   710 mrna sequences randomly selected from   a. thaliana   631 trna sequences from   a. thaliana   63 5.8 s rrna sequences from   rfam version 7.0    602 5 s rrna sequences from   rfam version 7.0   one randomly selected rna sequence from each of the 455 noncoding rna families from   rfam version 7.0 ( except mirna families ) ; 2,760 shuffled pre - mirna sequences ( each of the 184   a. thaliana sequences from   mirbase   10 was shuffled 5 times using shuffle   preserving ( a ) the mononucleotide content , ( b ) mono- and dinucleotide content , and ( c ) mononucleotide content in a window of 20  nt , resp . )   repetitive genomic elements from   a. thaliana from the repeatmasker library   ( in total 134,000  nt ) 8,000 pseudohairpin sequences from   homo sapiens    10,000 pseudohairpin sequences from   a. thaliana ; these were selected using   rnalfold from the tair cdna library   to have a minimum stem - loop length of 50  nt in a base pair span of 400  nt 10  5,000   sequences of a length between 80 and 800  nts randomly selected from the five chromosomes of   a. thaliana .  

it relies on   rnashapes [ 24 , 25 ] and   rnalfold   ( which is part of the vienna rna package ) for secondary structure calculations .  
rnalfold finds subsequences of a long rna sequence that fold into locally stable ( i.e. , thermodynamically favorable ) rna secondary structures ; the computational effort is (nl ) with length n of the long rna sequence and maximal base - pair separation l of the subsequences . for an rna sequence ,  
rnashapes computes shapes , which are classes of similar secondary structures , and a representative structure  shrep  of minimal free energy within each shape .
in the following , we describe the workflow of   novomir ( see supplemental figure s5 ) .
a typical plant pre - mirna consists of a relatively short sequence ( with median length ~130  nt and mean length ~150  73  nt ) that is able to fold into a stable stem - loop structure .
thus , we search in the genomic sequence for subsequences with locally stable secondary structure(s ) via rnalfold . in case the genomic sequence is longer than 1000  nt , we subdivide it into 1000  nt fragments overlapping by 400  nt .
this limit excludes only a few exceptionally long pre - mirnas ; that is , only 8 of 1356 plant pre - mirna sequences in   mirbase   10 and 14 of 2030 in   mirbase   14 , respectively , are dismissed due to this restriction for the sake of a fast first step . from the output of   rnalfold ,
the five subsequences with best locally stable structures are treated further as individual sequences .  
the original sequence ( with length 1000  nt ) or a subsequence ( with length 400  nt ) selected by   rnalfold is discarded if the sequence has a base composition not typical for pre - mirnas ; that is , the sequence is only retained if the fraction of each nucleotide is above 0.1 .
this filter rejects 9 and 21 plant pre - mirna sequences from   mirbase   10 and 14 , respectively . 

rnashapes is used to predict the thermodynamically optimal secondary structure ( minimum free energy ( mfe ) structure with gmfe ) and the optimal secondary structure of up to three shapes with energies less favorable than that of the mfe shape class by 0.1  kcal / mol .
the shapes have to differ in their nesting pattern for all loop types but positions of unpaired regions are not of relevance ( rnashapes 's option   t 3 ) .
in general , it is assumed that the mfe structure of pre - mirnas is the conformation adequate for further processing by dicer . in our case , however , we do not know the true 5 and 3 ends ; thus , the unrelated termini of the respective sequence , which do not belong to the true pre - mirna , might cause the pre - mirna structure to be thermodynamically suboptimal .
moreover , the restriction by   rnashapes to the shrep prediction avoids prediction ( and further processing ) of the immense number of suboptimal structures .
any sequence that is not able to fold into a structure ( as predicted in step ( 3 ) ) with g37c / l / fgc  0.75  kcal / mol / nt is rejected .
next , each retained secondary structure is reformatted from the bracket - dot notation used by   rnashapes into an alignment - like format   ( for an example see figure 1 ) , which eases handling during the following steps : at each multiloop , the structure is divided into the respective stem - loop structures , which are separately processed further ; 5 and 3 dangling ends are removed ; a hairpin loop is removed ; and asymmetric loops are made symmetric by introduction of gap symbols . afterwards
each ( sub)structure consists of the following states : base pairs ( match states m symbolized by   + + ) , loop
( mismatched states n ,   -- ) , and insertion ( i ) and deletion ( d ) states ( -| and   |- , resp . ) .
a stem - loop shorter than 30 states in the alignment - like format is deleted . for efficiency of this filter ,
next , a window of length 25 states is moved ( in steps of ( 1 ) state ) along the structure in the alignment - like format , and the fraction of base - paired states is determined for each window .
a stem - loop is deleted unless at least a mean fraction of 0.65 base - paired states is present in five different windows , which might overlap . for efficiency of this filter see figure 2(b ) .
a stem - loop is deleted if it does not contain a helix with at least 8 consecutive base pairs . for efficiency of this filter
a stem - loop is deleted if the ratio of its sequence length ( as predicted by   rnalfold ) and the length of the stem - loop in the alignment - like format is above 6 ; that is , the structure contains too many junctions and/or large , unstructured hairpin loops . for efficiency of this filter
if a sequence ( and structure ) remains after the filter steps ,   novomir decides on its possibility to be a pre - mirna using a paired hidden - markov model identical to that described by nam et al . .
briefly , the joint probability p(x ,  ) of an observed sequence x and a state sequence  is 
								 ( 1)p(x, )  =  t01i=1lei(xi)ti,i+1 , 
							 with transition probabilities tkl = p(i = l | i1 = k ) between the four states k , l  { m ,
n , i , d } , emission probabilities ek(b ) = p(xi = b | i = k ) of the different nucleotide and gap pairs b , window size l = 21 , and the probability of starting in state k defined as t01 .
in contrast to nam et al . , we use four hidden states ( is_mirna , is_mirnais_not_mirna , is_not_mirnais_mirna , is_not_mirna ; see figure s6 ) . for the decision that the sequence is a pre - mirna or not , the values for the j  is_mirna , is_not_mirna } states are normalized and summed up 
								 ( 2 )  pj=i  =  1lei , j(xi , j)ti , j,i+1,jj=14ei , j(xi , j)ti , j,i+1,j . 
							
the squared ratio 
								 ( 3)r1  =  ( pis_mirnapis_not_mirna)2 , 
							 as well as the mean of the nine highest values of the difference 
								 ( 4)r2  =  max  k = ll+20pis_mirnapis_not_mirna , 
							 are compared to thresholds for the pre - mirna decision . in case of a positive decision in the previous step ,
the values that lead to the six highest values of r2 are predicted as positions of probable mirna / mirna * duplices ( see figure 1(c ) ) .
our programnovomir uses a set of heuristic filters and a statistical model    to discriminate a mirna precursor from all other rnas ( see figure s5 ) .  
the data for this model are collected based on a set of true positive sequences ( mirna precursors from   a. thaliana as in   mirbase   10 ) and a set of true non - mirna sequences ( for details , see section 2.3 ) .   all thresholds for the filter steps and the probabilities for the hidden - markov model were selected on the basis of  receiver operating characteristic  ( roc ) curves like those shown in figure 2 . for these ,
the set of true positive   a. thaliana pre - mirna sequences was taken from   mirbase version 10 .
sensitivity values for the enlarged set of pre - mirnas from   mirbase version 14 ( 190   a. thaliana and 1,840 sequences from other plants ) are compared to those obtained from   mirbase version 10 ( 184   a. thaliana and 1,063 sequences from other plants ) in table 1 .
the sensitivity values of   novomir for   a. thaliana pre - mirna sequences of both   mirbase versions are very close to each other ( 0.837 and 0.832 , resp . ) .
the values for all plant pre - mirna sequences are slightly lower ( 0.791 and 0.792 , resp . ) , but show no clear trend that sequences of   mirbase   14 ( not present in   mirbase   10 ) are different from those of   mirbase   10 or that sequences from a certain taxonomic group might be different from those of others ( see supplemental table s1 ) .
the sensitivity of   novomir in predicting the position of the mirna / mirna * complex is also high ( 0.73 for   a. thaliana and 0.82 for all plants ; see table 1 ) . for this , a position is counted as correctly predicted if it matches exactly the annotated mature mirna or overlaps by five or fewer nucleotides .
we tested   hhmmir   and   triplet - svm   for sensitivity with the sequences from   mirbase   10 and 14 ( see table 1 ) .
the filtering steps of both tools reject already many sequences ( hhmmir more than 80% and   triplet - svm more than 22% ) .
for the sequences remaining after the filtering steps , the sensitivity of the hhmm and svm is at maximum 0.79 and 0.60 , respectively , which is also lower than that of   novomir with a sensitivity of at least 0.80 ( using all filter steps ) .
these data sets should not contain any true ( pre-)mirna . for example , we used well - annotated rnas ( mrna , noncoding rna ) and sets of  pseudohairpins  from   h. sapiens and   a. thaliana .
similarly , the chance is negligible that the data set of 10  5,000 sequences randomly selected from the   a. thaliana genome contains a true mirna .
the most difficult data set consisted of   a. thaliana mrnas ; with these   novomir reached a specificity of 0.975 ( see table 2 ) . with
we wanted to test the program with a more realistic scenario , given the satisfying sensitivity and specificity values of   novomir with our test data ( see tables 1 and 2 ) .
we selected all intergenic and intronic regions of the   a. thaliana genome from  the arabidopsis information resource 
( tair ) , removed all pre - mirna sequences , and searched within the remaining sequences for potential pre - mirnas via novomir .  
novomir classified 828 sequences from the 30,413 intergenic sequences and 649 sequences from the 148,558 intronic sequences , respectively , as potential pre - mirnas . despite this
pleasingly low numbers of hits , however , an interpretation of this outcome is not easy . to get an impression on the hits
, we searched with these potential pre - mirna sequences with   blast for any annotation and for the mirna - typical expression pattern in the  arabidopsis small rna project database  ( asrp ) [ 28 , 29 ] ; such a typical expression pattern of a pre - mirna includes sequences for the mirna as well as for the mirna * ( for an example see supplemental figure s7 ) . to our surprise
, we detected that some of the predicted candidates are already described as true pre - mirnas .
an example of such a sequence , predicted by   novomir as a potential pre - mirna , is located on   a. thaliana chromosome 3 in the region between genes at3g09280 and at3g09290 .
its secondary structure and its support by expressed small rnas are shown in figure 3 and figure s8 , respectively .
it is already known as pre - mir2111a [ 30 , 31 ] , but not present in   mirbase   14 .
the sequences of the mature mir2111a and of mir2111a * predicted by   novomir also coincide with the sequences given in .   in the following , we mention shortly three further candidate hits , for which we found some support by small - rna expression in the asrp but no explicit annotation .
one   novomir hit is located on chromosome 4 between at4g22760 and at4g22770 close to the 3 terminus of the latter , but on the opposite strand ; for further details , see figure 3 and figure s9 .
the next hit ( see figure 3 and figure s10 ) is located in between at5g52689 and at5g52690 .
the last mentioned hit is located in an intron of at1g01650 , which encodes for an aspartic - type endopeptidase / peptidase ; the structure of this sequence is shown in figure 3 and the expression pattern of the genomic region in figure s11 .
it is known that many mirnas are induced by biotic and abiotic stress [ 3638 ] .
thus , a lack of small rnas might either point to a false - positive prediction or to a stress condition not analyzed for expression of small rnas .
further candidate hits are located in regions showing expression patterns similar to those of repetitive elements .
a recently published review   discussed the possibility that some mirnas could be evolved from repetitive genomic elements and/or duplication of genomic regions .
viroids are plant - infectious , noncoding , unencapsidated , circular rnas that are transcribed in a rolling - circle mechanism either in nuclei ( pospiviroidae ) or in chloroplasts ( avsunviroidae ) of infected plants .
viroids cause the production of viroid - specific small rnas ( vsrna ) similar in size to small interfering ( sirna ) and mirnas , but they do escape the cytoplasmic silencing mechanism . a positive ( or negative )   novomir prediction of viroids as potential pre - mirnas would point to the genesis of vsrnas . for further details , see recent reviews [ 4043 ] .  
potato spindle tuber viroid ( pstvd ) is the type strain of   pospiviroidae . because of its high self - complementarity the circular pstvd rna folds into a rod - like secondary structure of high thermodynamic stability ( see figure 4 ) .
this structure can be divided into five structural domains on the basis of homology between different pospiviroids .
most sequence variants or strains of pstvd differ by mutations in the pathogenicity - modulating ( p ) domain and/or variable ( v ) domain .
only a few nucleotide changes in the p domain are sufficient to exhibit remarkably different symptoms in infected tomato plants   solanum lycopersicon cv rutgers .
if this p domain would be the source of mirna - like vsrnas , these could interfere somehow with the host 's metabolism leading to symptom production .
for an rna with pstvd sequence from positions 263359/196 , which is one of the structural elements present during processing of   ( + ) -strand replication intermediates to circles ,   novomir predicted mirna / mirna * complexes in the p domain of pstvd ; for an rna from positions 103255 , which is also a structural elements during processing ,   novomir predicted a further mirna / mirna * complex in the tr domain , but only after lowering the normalized energy threshold from the default value tg / l / fgc = 0.75 to 0.69 .
novomir predicted identical positions for complexes in a full - length , linear pstvd ( 1359 ) .
especially the prediction of vsrnas derived from the p domain supports an involvement of vsrnas in symptom production via vsrna - induced ( mis)regulation of plant - endogenous rnas like mrnas coding for transcription factors .
this hypothesis is supported by deep - sequencing of pstvd - derived vsrnas in pstvd - infected tomato plants ( diermann , matouek , teune , riesner and steger , submitted ) and sequencing of vsrnas produced   in vitro by dcl processing of pstvd   which showed clusters of vsrnas derived from the p domain .
in contrast , [ 45 , 46 ] found only vsrnas in pstvd - infected tomato plants that clustered in regions outside of the p domain .
this discrepancy is unresolved but might be based for example on different purification procedures of the vsrnas .
plant pre - mirnas are more heterogeneous in size and structure than animal pre - mirnas but still show sufficient characteristic features  such as relative thermodynamic stability of their structure , length of helices , and number and size of loops  to be differentiated from other rnas .
based on several of these features , we developed a series of filter steps and a statistical model that together are able to detect pre - mirnas with a sensitivity of about 0.8 and a specificity of about 0.99 .
thus , the program , which we call   novomir , is well suited to search on a genomic scale for new pre - mirnas that are not necessarily evolutionarily conserved . as an example , we searched with   novomir for pre - mirnas in nontranslated regions of the   a. thaliana genome and detected among the high - scoring sequences experimentally verified pre - mirnas , which were not annotated in the recent version of   mirbase
. additionally ,   novomir recognizes viroids as pre - mirnas , which supports the hypothesis that viroid - specific small rnas are generated in a mirna - like pathway .
 micrornas ( mirna ) are small regulatory , noncoding rna molecules that are transcribed 
 as primary mirnas ( pri - mirna ) from eukaryotic genomes . 
 at least in plants , their 
 regulatory activity is mediated through base - pairing with protein - coding messenger rnas 
 ( mrna ) followed by mrna degradation or translation repression . 
 
 we describe novomir , a program for the identification of mirna genes in plant 
 genomes . 
 it uses a series of filter steps and a statistical model to discriminate a pre - mirna 
 from other rnas and does rely neither on prior knowledge of a mirna target nor on 
 comparative genomics . 
 the sensitivity and specificity of novomir for detection of premirnas 
 from arabidopsis thaliana is ~0.83 and ~0.99 , respectively . 
 plant pre - mirnas 
 are more heterogeneous with respect to size and structure than animal pre - mirnas . despite 
 these difficulties , novomir is well suited to perform searches for pre - mirnas on a 
 genomic scale . 
 novomir is written in perl and relies on two additional , free programs for prediction 
 of rna secondary structure ( rnalfold , rnashapes ) . 