methods for detecting non - coding rnas ( ncrnas ) in genomic sequence data have been a topic of intense research .
while techniques for detecting protein - coding genes can rely on universal characteristics such as start and stop codons , triplet amino acid codes , or ribosome binding sites , there are no corresponding characteristics known in ncrnas . early approaches to ncrna detection were designed for specific types of rnas , in particular trnas ( 1 ) . other approaches to ncrna searching were designed for detecting arbitrary ncrna classes , typically based on the conserved sequences or secondary structure elements .
the rnamotif ( 2 ) tool allows to describe a search pattern consisting of conserved stems and helices , while the erpin tool ( 3 ) allows to annotate an alignment with secondary structure information , which is then used as a search pattern . the infernal tool ( 4 ) also derives its query from a multiple alignment .
in contrast to erpin , however , the alignment is translated into a stochastic context - free grammar , which is then used for the ( quite time - demanding ) task of scanning genomic sequences . in general , the computational complexity of searching rnas increases with the complexity of the search pattern , limiting the use of such methods for genome - wide surveys . in this paper , we present fragrep , an efficient tool that is optimized for this kind of sequence - based searches . the approach implemented in the fragrep tool
is based on an elementary way of describing search patterns , allowing a highly efficient and hence genome - wide application .
this approach is particularly fruitful for the classes of ncrnas that contain stem or loop regions with well - conserved sequence patterns , such as y rnas and vault rnas 5 .
, 7 . , which , however , are interrupted by non - conserved sequences of highly variable lengths .
compared to rnamotif , we provide a statistically well - motivated ranking scheme , which relieves the user from defining an individual scoring scheme as in rnamotif .
the problem of efficiently searching a large sequence database for interrupted sequence patterns is also relevant in the context of other ncdna motifs , for example cis - regulatory modules ( 8) . in this context , the approach investigated in fragrep is complementary to the motif discovery procedures such as biooptimizer ( 9 ) or bipad ( 10 ) : once a suitable motif has been discovered , fragrep can be applied to scan genome databases for such patterns ( or constellations of patterns ) . in some cases ,
the fragmented patterns are informative enough to be clearly distinguished between true and false positives . in many other cases , however , fragrep can at least act as an efficient filtering technique .
the fragrep tool can be downloaded from the url http://www.bioinf.uni - leipzig.de / software / fragrep/.
suppose that the ncrna of interest contains k conserved sequence fragments , denoted by c1 ,  , ck , which occur in a given order in a set of known examples .
in practice , the fragment ci is obtained as the consensus sequence of conserved blocks in a multiple alignment . scanning a genome t for these blocks ,
we expect to find a non - conserved sequence segment xi between any two fragments ci and ci+1 .
, xk1 so that the string c1x1c2x2  xk1ck is contained as a substring in t. additionally , fragrep can take into account two further aspects : gap length bounds : for each xi , the user can specify the upper and lower bounds of the length , denoted by ui and i , respectively ; only the matches satisfying i |xi| ui will be taken into account by fragrep .
mismatches : the fragment ci does not need to match the corresponding sequence part of t exactly ; the user can specify the number of mismatches ( mi ) . denoting ci as the modified fragment of ci by at most mi arbitrary mismatches
we also refer to the string c1x1c2x2  xk1ck satisfying all these constraints as a matching subsequence of t. similar features
are incorporated in other tools such as rnabob ( ftp://ftp.genetics.wustl.edu/pub/eddy/software/rnabob-2.1.tar.z ) , which is based on a nondeterministic finite state machine with node rewriting rules instead of the dynamic programming approach used by fragrep .
the algorithm underlying fragrep essentially works in two steps:1.for each i  [ 1 : k ] , compute a list of all occurrences of ci in t.2.apply a dynamic programming algorithm to the lists computed in the first step in order to find all matching subsequences in t. for each i  [ 1 : k ] , compute a list of all occurrences of ci in t. apply a dynamic programming algorithm to the lists computed in the first step in order to find all matching subsequences in t. performing step 1 is straight - forward . as a result , we obtain an ordered list of indices yi=yi,1,yi,2,  ,yi , li , with yi , j denoting the position of the j occurrence of ci in t , and li denoting the number of occurrences of ci in t. using y1 ,  , yk , we now set up a graph g = ( v , e ) with the vertex v = { ( i , j ) | i  [ 1 : k ] , j  [ 1 : li ] } and an edge between ( i , j ) and ( i+1 , j ) , whenever the corresponding occurrences of ci and ci+1 satisfy the upper and lower bounds for the gap in between .
obviously , any path of length k  1 in g corresponds to a valid occurrence of c1 ,  ,
ck in t. for each ( i , j ) , i  [ 1 : k ] and j  [ 1 : li ] , we now computemi , j:={1iftcontains the modelc1,1,u1,  ,ci,i , uiwithcioccurring at positionyi , j0otherwise .
apparently , we have a valid occurrence of c1 ,  , ck in t whenever we have mk , j = 1 for some k  [ 1 : lk ] .
furthermore , we have m1,j = 1 for all j  [ 1 : l1 ] ( since every occurrence of c1 is a valid occurrence up to the first fragment ) .
now , using the graph g , we can compute all mi , j for i > 1 asmi , j={0ifmi1,j=0for all((i1,j),(i , j))e1otherwise . starting with i = 1 , the mi ,
now , each non - zero entry in the k row of m indicates at least one valid match .
defining l : = maxi 
 li , altogether k  l matrix entries are computed , so that the overall time complexity for computing m is o(kl ) ; enumerating all  matching subsequences of t can be done in o(kl +  ) time .
the match number  is proportional to the tolerance allowed by the gap length bounds , that is , uii . while in principle  is bounded by o(l ) ( since each occurrence of c1 might yield one matching subsequence for each occurrence of ck ) , one is naturally interested in queries that produce few significant rather than an abundance of insignificant matches .
hence , for all practical purposes , o(kl ) should be seen as the dominating term in the running time .
note that the above procedure can be easily adapted to start dynamic programming with the most informative sequence ca rather than c1 by starting in the a row of m. this increases the search efficiency and in practice leads to a significant speedup , in particular when short or ambiguous fragments are part of the pattern .
the c++ implementation of fragrep has been optimized in this and several other algorithmic details to improve the runtime .
this limitation could be relaxed by employing a different pattern matching algorithm that allows gaps at a prescribed gap function .
the use of the exact smith - waterman local sequence alignment algorithm for this purpose is possible but computationally quite expensive . in our applications ,
gaps were restricted to specific positions . in this case , it is more efficient to break the search pattern into smaller units linked by short intervals of variable lengths . since the identification of these breaks is self - evident in the applications under our consideration , one obtains significantly more specific query patterns than for gapped alignment matches .
a major issue in evaluating the quality of the matches produced by the above procedure is to assess how surprising a given match is , that is , how likely it is to be observed in a random sequence . to this end
, fragrep provides p- and e - value - like ranking schemes that are computed from a dinucleotide - based markov model . in order to adapt the markov models to the occurrences of a fragmented rather than a contiguous sequence pattern , we let ej denote the event of c1 , 
, cj being observed at least once in a sequence of length n in the given order and satisfying the distance constraints given by the respective upper and lower bounds ui and i for each ci ( formally dealing with a probability space over all sequences of length n ) .
furthermore , let q(j , l ) denote the event of observing cj at least once in a sequence of length l. our main interest obviously is to determine the probability p(ek ) .
denote mt as the first order markov model resulting from the dinucleotide frequency distribution in t , we may compute pt(c1 ) : = p(c1|mt ) as the probability of the fragment c1 being produced by mt . in order to obtain p(e1 ) , we assume that the probability of c1 being produced at a position x in a sequence of length n is independent of the probability of c1 being produced at any other position y in t  note that this assumption holds for the fragments that do not contain any substring of length 2 more than twice , and , for all practical purposes , is a sufficiently good approximation for the fragments that are short and contain only few repetitive substrings . now , under this assumption of independence , we obtain(1)p(e1)=q(1,n)=pt(c1)0v <
n|c1|(1pt(c1))v the probabilities q(j , l ) can be computed analogously for arbitrary j and l. it is now easy to see that for j  { 2 , 
, k } , we have(2)p(ej)=p(ej1)q(j , ujj)(since , in a sense , cj needs to be generated by mt in a sequence of length uj  j + |cj| ) so that we finally obtain(3)p(ek)=p(e1)2jkq(j , ujj ) as described above , p(ek ) is the probability of observing at least one exact match of the given fragmented pattern in a sequence of length n. this value can be easily adapted to the scenario involving occurrences with a certain number of mismatches by modifying the probabilities pt(cj ) accordingly .
since different matches obtained by fragrep generally have different mismatches in different positions , we can also compute the analogous probabilities for the individual matches detected by fragrep .
finally , w(ek ) : = log ( p(ek ) ) provides a convenient and statistically well - motivated ranking scheme for the matches .
we used fragrep to studying the evolution of a class of ncrnas in the slime mold dictyostelium discoideum that was discovered in an experimental survey by aspegren et al . ( 11 ) .
we searched the genomic sequence ( 12 ) for the type - i ncrnas using the following simple pattern : table00gttgrccttacagcaa20120gtcaactg2 the first two columns contain the minimal and maximal distance between the pattern fragment ( always 0 for the first fragment , of course ) , the last column is the maximal number of mismatches that is tolerated in each fragment .
( 11 ) ranges between 58 and 88 nucleotides , so that 120 is a reasonable choice for the gap length s upper bound .
we recovered 45 candidates , of which 34 were sufficiently similar to the experimentally determined sequences to be alignable .
a neighborjoining tree summarizing both known sequences and the novel candidates detected by fragrep is displayed in figure 1 .
we find that the class - i ncrnas are located in small clusters in all six chromosomes .
interestingly , there are two subclasses , denoted by a and b , that alternate in the larger clusters , even though their directions on the chromosomes do not seem to follow a simple rule . in order to evaluate the performance of the algorithm underlying fragrep
, we used the query derived from the vault rna a- , b1- , and b2-box consensus structures in kickhoefer et al .
scanning all chromosomes of the human genome took less than 10  minutes on a standard desktop computer with a 2  ghz processor and 1  gb main memory .
further results from scanning the human as well as the mouse , rat , and dog genomes are listed in table 1.table00trgcnnagygg10100ggttcgantcc10100ggttcgantcc1 in order to obtain an estimation of the influence of high gap - length tolerance on the running time , we modified the above query to allow for gap lengths up to 20,000 , resulting in an increase of the running time by less than five folds .
note that this increase in fault tolerance also increased the number of matching subsequences to the order of hundreds of thousands , so that the significance of such highly fault tolerant queries is already limited from a practical point of view . in spite of this undue fault tolerance ,
the application of standard multiple alignment tools such as clustalw or dialign to a relatively small set of representatives of an ncrna class can be used to determine conserved sequence patterns , which can be turned into fragrep queries in a straight - forward manner .
the fragrep tool can then be employed to find additional members of the ncrna family in related genomes .
this approach yields significant matches where other sequence search tools such as blast fail to report useful results , while the structure based approaches such as infernal ( 4 ) are too costly .
naturally , fragrep is not limited to ncrna detection ; the search for specific constellations of transcription factor binding sites is another potential application .
furthermore , the approach could be easily adapted to searching peptide motifs in protein databases .
 many classes of non - coding rnas ( ncrnas ; including y rnas , vault rnas , rnase p rnas , and mrp rnas , as well as a novel class recently discovered in dictyostelium discoideum ) can be characterized by a pattern of short but well - conserved sequence elements that are separated by poorly conserved regions of sometimes highly variable lengths . 
 local alignment algorithms such as blast are therefore ill - suited for the discovery of new homologs of such ncrnas in genomic sequences . 
 the fragrep tool instead implements an efficient algorithm for detecting the pattern fragments that occur in a given order . for each pattern fragment 
 , the mismatch tolerance and bounds on the length of the intervening sequences can be specified separately . 
 furthermore , matches can be ranked by a statistically well - motivated scoring scheme . 
Introduction
Algorithm
Results and Discussion