the presence of large numbers of repeats often confounds sequence assembly , especially if the repeats are long and highly conserved .
the presence of low copy - number repeats can also confound assembly , especially for whole - genome shotgun sequencing projects .
once a genome has been assembled , repeats take on a new and more important role involving their biological function
. certain classes of repeats , such as transposons , perform a function by allowing mobile elements to move around a genome .
other classes belong to less well - defined categories with respect to their role , though they may be even more ubiquitous .
repetitive sequences appear to dominate the centromeres of many eukaryotes , and telomeric and subtelomeric repeats extend for thousands or tens of thousands of nucleotides at the ends of chromosomes .
these repeats also appear elsewhere in the genome , for reasons as yet unknown . for these and other reasons , it is critical to both the assembly and analysis of genomic sequences to identify and characterize repetitive sequence elements .
there are numerous computational methods for detecting repeats , in one form or another , in genomic dna sequences .
these include algorithms that locate repeated substrings , including tandem repeats [ 3 , 4 , 5 , 6 ] , as well as programs for identifying known repeats , such as the widely - used repeatmasker .
repeatmasker uses a database of known repeat sequences and implements a string - matching algorithm to find copies of those repeats in a new sequence .
a more rapid implementation of the same approach is maskeraid , a wrapper for wu - blast [ 9 , 10 ] that uses the blast engine instead of the crossmatch algorithm .
most of these tools have some restriction on the maximum length of the input sequence , which limits their use to sequences considerably smaller than the size of a eukaryotic chromosome .
recently , however , new systems based on suffix trees , such as repeatmatch ( based on mummer ) and reputer [ 12 , 13 ] , have overcome this size limitation , at least for biologically realistic input sizes .
both repeatmatch and reputer are highly efficient computational tools that can find all exact repeats in sequences as long as complete eukaryotic chromosomes - 10100 megabases ( mb ) .
the output of these systems , however , while accurately representing the long list of positions of exact repeats , does not provide any overview or summary of the repetitive structure of the sequence .
the reputer system includes a visualization tool to generate repeat graphs , which are useful for identifying the positions of repeats , but this does not provide an overview of the exact and non - exact repeats in a genome .
an example sequence of 180 bp and graphical depiction of exact repeats , using minimal repeat length 6 bp .
both of the horizontal lines correspond to the example sequence , and diagonal lines connect the two occurrences of each repeat .
reputer includes a visualization tool to provide similar graphics . examining the output of reputer and repeatmatch for a complete bacterial genome
, it quickly becomes obvious that many exact repeats are non - exact copies of one another .
whether a genome is a few or hundreds of megabases in length , the task of recognizing and describing how repeats resemble one another at this scale is too complicated to accomplish manually .
here we describe a new system for the recognition of repeat classes in genome sequences .
in contrast to approaches that cluster together the results of blast searches ( for example , z.h .
bao and s. eddy , unpublished data ) our algorithm uses a comprehensive set of exact repeats as the basis for constructing repeat classes .
it relies on the efficient suffix tree data structure for identification of exact repeats , which permits rapid identification of repeat classes even in sequences containing tens of millions of nucleotides
. the algorithm does not make any prior assumptions about the number or structure of the classes . at its core
is a merging procedure that produces the actual members of each repeat class using merging criteria described below , and it also builds a repeat map of the genome sequence .
we have applied this system to several complete microbial genomes [ 15 , 16 , 17 , 18 , 19 , 20 , 21 ] , to the complete arabidopsis thaliana genome , and to a large collection of rice bacterial artificial chromosome ( bac ) end sequences [ 22 , 23 ] .
the output of the system gives a clear picture of all repeat classes identified in a genome or a sequence collection .
it provides straightforward access to the actual repeat sequences as a multi - fasta file , simple statistical analyses of the results , and a procedure for identifying each class 's most representative element .
we describe here the computational techniques used in the system and demonstrate its use on several different genome sequences .
we begin by defining an exact repeat as a subsequence that occurs in dna sequence at least twice . a maximal repeat ( figure 2a )
is a repeat that can not be extended in either direction without incurring a mismatch .
repeats may have a direction with respect to the underlying sequence ( forward , reverse ) and with respect to each other ( reverse complement ) . by allowing a set of editing operations - deletions , insertion and mismatches
the set of repeats chosen initially , from which the repeat classes will be constructed , is called the initial repeat set .
top , red , blue and yellow lines show the locations of the repeat sequences .
pairs a1 and a2 , b1 and b2 , and c1 and c2 are initial repeat pairs .
bottom , green bars labeled m1 , m2 , m3 and m4 indicate the location of merging repeats . in the initial repeat
set , different repeats may be very close together ( figure 2b ) and may even overlap ( figure 2c ) .
this intricate picture can be simplified by constructing a more general type of repeat : a ' merging repeat ' will be defined as a sequence that can be found in the whole genome sequence not less than twice , where occurrences of the merging repeat are permitted to be partial copies .
merging repeats , labeled m1-m4 in figure 2 , are created from initial repeat sequences that are close together or overlapping .
merging repeats maintain pointers to the initial repeats comprising them ; for example repeat m1 ( figure 2b ) has pointers to initial repeats a1 and b1 .
we shall also refer to these initial repeats as ' subrepeats ' of m1 using these properties , we can formulate a similarity condition between merging repeats .
two merging repeats m1 and m2 are similar if they have at least one common initial sequence , or there exists a sequence of merging repeats m1 , n1 , n2 , ... nk , m2 such that each pair of merging repeats in the sequence shares at least one common subrepeat .
the minimum number k of merging repeats needed to establish the similarity between m1 and m2 can be used as a similarity measure .
for example , the merging repeats m2 and m4 . in figure 2b are similar with similarity measure k = 2 based on the sequence m2 , m3 , m1 , m4 .
one goal of our clustering algorithm is to distribute merging repeats into classes according to this similarity condition so that two rules are satisfied : first , elements in the same class ( homogeneity elements ) are highly similar to each other ; and second , elements from different classes ( separation elements ) have no similarity to each other . the maximal similarity k defined on all merging repeats in a class can be used for assessing the overall similarity of the class members .
( in this paper the measure of similarity k is used only for the definition of merging repeats ) . in this study
the method does not require the use of exact initial repeats , but can be applied easily to an initial set containing approximate repeats [ 3 , 13 ] .
our algorithm is based on first identifying all exact repeats in the input sequence , and then defining repeat classes by merging and extending these short exact matches .
an exact repeat is represented by pair of coordinates ( a1 , a2 ) delimiting its location in the genome sequence , and by the repeat length l. we implemented an algorithm that uses either of two suffix tree methods , repeatmatch   or reputer   to determine all the exact repeats in a given sequence .
( for more on suffix trees see . ) the computational time and space requirements for both these systems are linear in the size of the input sequences , an essential requirement for any algorithm attempting to process whole eukaryotic genomes .
the input to the system can be either a single genome sequence or a set of sequences .
the clustering procedure consists of the following steps , which are described in more detail below .
the list of coordinates of all exact repeats as output by repeatmatch or reputer can be interpreted as a partition of the original genome sequence .
we used reputer in the example and in the subsequent repeat analyses of microbial genomes ; for the a. thaliana genome and and the rice bac end - sequence data we used repeatmatch . )
each partition point has a reference to the pair coordinates ( a1 , a2 ) and the repeat length l. each repeat corresponds to at least two partition points .
some repeats can be found in the sequence more than twice , and the corresponding partition points can appear with different coordinates and different lengths . to prepare the data for the merging procedure ,
we sort the list of partition points in increasing order , and in the case of duplicate first coordinates , in increasing order of second coordinates .
( the clustering algorithm is order - independent ; however , the linear nature of repeat data allows us to use this pre - processing step to simplify the clustering procedure without affecting the final clusters . ) in particular cases it is useful to filter the original repeat data to remove certain types of repeats ; for example , simple one - base ( homopolymeric ) or two - base repeats .
, this procedure works by repeatedly merging together two exact repeats that either overlap or that occur within a limited distance ( a gap ) of each other .
. whether the algorithm is merging repeats that overlap ( figure 2c ) , or merging repeats separated by a gap ( figure 2b ) , the new merging repeats will always have the property that significant subsequences of the repeat appear at least twice in the genome sequence . at the time of merging procedure ,
this map is based on a linked - list data structure , which allows for rapid and simple modifications to the dynamically changing repeat data .
every merging repeat in the map is linked by pointers to all the merging repeats with which it shares exact repeats .
each merging repeat will be assigned to a specific class if its list of references ( that is , the repeats that were combined into the merging repeat ) contains at least one repeat that already belongs to the class .
if a merging repeat has references that belong to multiple distinct classes , then those classes are combined into one .
if a merging repeat contains no references to an existing class , then the merging repeat forms a new class .
the initial classification is based on exact repeats . to merge together similar but non - exact repeats , we use wu - blast [ 9 , 10 ] to search all merging repeats against all others .
the resulting matches between the classes are used as input to an update procedure which redistributes all merging repeats into new classes .
it is possible to skip this step if the initial repeat set contains approximate rather than exact repeats . in this step ,
the output from reputer or repeatmatch is used to partition the original genome sequence . for each repeat
starting at coordinates a1 and a2 with length l , this list will include both ( a1 , a2 , l ) and ( a2 , a1 , l ) .
the list is then sorted by first and by second coordinates . to illustrate the method
the table on the left in figure 3 shows all seven pairs of repeats , while the right table shows the corresponding sorted partition points .
the table on the left shows repeat pairs that were found by reputer in the 180 bp example sequence shown in figure 1 using a minimum repeat length of 6 bp .
( f ) or reverse complement ( rc ) , first coordinates ( a1 , a2 ) and length ( la ) .
arrows show the correspondence between the repeat ( 67,153,6 ) and the two partition points ( 67,153,6 ) and ( 153,67,6 ) . using the list of partition points ,
given two partition points p1 = ( a1 , a2 , la ) and p2 = ( b1 , b2 , lb ) where a1 < b1 , we compute the distance between the non - overlapping repeats as d(p1 , p2 ) = max ( 0 , b1 - a1 - la + 1 ) .
next , given a maximum gap size g > 0 , the ' merging with gap ' protocol uses the rule that sequences corresponding to p1 and p2 are merged if the ' merging with overlap ' protocol only merges sequences that overlap one another ; that is they are at least partially identical .
we denote the overlap of two sequences as 0(p1 , p2 ) = max ( 0 , a1 + la - b1 + 1 ) for a1 < b1 then the criterion for ' merging with overlap ' is as follows : given a minimum overlap proportion op , where 0  op  1 , repeat points ( a1 , a2,la ) and ( b1 , b2 , lb ) are merged if at least one of the four repeats has overlap satisfying 0 ( p1 , p2 ) > op min ( la , lb ) . the parameter op is interpreted as a fraction of the shorter of the two repeats .
thus for op = 0.75 , we will merge two overlapped sequences if the length of their overlap is at least 75% of the length of the shorter sequence .
using either merging procedure , if two sequences are merged then the new sequence will be defined as a merging repeat with starting position m = a1 and with length lm = max ( a1 + la , b1 + lb ) - a1 .
the merging procedure is not permitted to merge pairs of partition points of the form ( b1 , b2 , lb ) and ( b2 , b1 , lb ) .
this condition avoids merging of tandem repeats and avoids repetitiveness within the merging repeats . on the left side of figure 4
the extent of each merging repeat is shown by dividing sets of repeats using horizontal lines .
horizontal lines divide sets of exact repeats that were merged into a single merging repeat .
the arrow shows the connection between a group of two short exact repeats and the corresponding 11 bp merging repeat starting at position 77 .
this procedure , by updating and creating new references , leads to the repeat map shown on the right of figure 4 .
each merging repeat maintains references to the other merging repeats with which it shares exact repeats ; each exact repeat is assigned to the first merging repeat in which it appears . in our example
, the merging repeat starting in coordinate 77 gets a reference to itself only , because its exact repeats have no previous references .
the next repeat , starting in position 116 , gets a reference to itself and to its mate the merging repeat 77 . a data structure stores with each merging
repeat its start coordinate , its length ( lm ) , the number of exact repeats it includes ( nm ) , and a list of references to itself and to other repeats ( r1 , r2 , r3 ) . given the repeat map
, we can begin to define classes by noting that if a merging repeat has at least one reference in common with another , then they belong to the same class .
, lm = ( 126,8 ) has two common references in two different classes , class 1 and class 5 .
these classes are then combined together into a new class 1 , which contains all references from both the original classes .
the gray rectangle in the repeat map table shows the merging repeat with its length , the number of exact repeats it includes , and references to the repeats it contains .
it contains references to class 1 ( 16 ) and class 5 ( 116 ) , marked by gray in the first classification table . on the next classification step ,
these two classes are merged and the rest of their references are added to the new class 1 .
arrows show the directions of class merging . for this step , the most time - consuming part of the algorithm , we use the underlying sequences of the merging repeats , and run a blast search of all sequences against all others .
classes are merged if any of their underlying sequences have a blast e - value less then a user - specified threshold when compared to any sequence in another class .
if a class appears in multiple similarity pairs , all these similar classes are merged with the original class .
for the example in figure 4 , blast searches do not reveal any new similarity pairs ; thus the classification from the figure is identical to the final classification ( table 1 ) .
table 2 summarizes the repeat analysis for the neisseria meningitidis genome   using two different clustering criteria .
it illustrates how increasing the exact repeat size in the initial step leads to fewer merging repeats and fewer classes .
it also shows how reducing the size of the gap and increasing the required overlap increases the number of repeat classes , as would be expected .
sensitivity of the clustering method to different merging parameters the length of the neisseria meningitidis genome is 2,272,351 bp . for a more comprehensive repeat analysis
, we chose seven different microbial genomes , using 25 base pairs ( bp ) as the minimal exact repeat length and allowing less than a 25 bp gap for the merging procedure .
it presents the number of merging repeats , the number of repeat classes , the longest single merging repeat , and the number of classes containing more than two members . as shown here , these latter classes comprise only 1025% of all repeat classes , indicating that most repeat types are simple duplications . among these duplication ,
the vast majority occur in tandem , although this is not shown in table 3 .
the picture given here shows how repeat analysis can quickly provide an overall picture of how repetitive a genome is ; in addition , the analysis extracts the repeats themselves for further analysis .
repeat structure of microbial genomes small microbial genomes have relatively few types of repeats , and relatively few copies of each type .
in contrast , our studies of longer eukaryotic genome sequences have uncovered tens of thousands of repeat classes and hundreds of thousands of merging repeats . in order to be able to process this data efficiently - in particular , in order to run the procedure where
all classes are compared against each other using blast - we developed a procedure to define the most representative element for each class , which we call its prototype . referring to the repeat map shown in figure 5
, we use the length of the merging repeat ( lm ) and the number of exact repeats ( nm ) to defined the desirable properties for the prototype .
thus , in the ' merging with gap ' procedure , the merging repeats with the longest lengths and with the greatest number of subrepeats should be the best candidates to represent the class . in this case
when we use the ' merging with overlap ' procedure , we also look for the greatest number of subrepeats , but the length of the most representative repeat should be closer to the shortest repeat in the class . in this case
the representative element will tend to match across most of its length to every member of the class . using these considerations
given the merging repeat length l ( lm ) and number of subrepeats n ( nm ) , the maximum and the minimum repeat lengths in the class ( lmax and lmin ) , and the maximum and the minimum number of subrepeats in the class ( nmax and nmin ) , we define the function f(l , n ) for each merging repeat of the class as for ' merging with gaps ' and for ' merging with overlaps ' .
this non - negative function is a summary of the variance in the length and number of subrepeats from the desirable values for the class prototype
. then we solve the optimization problem of minimizing function f(l , n ) : find ( l , n ) corresponding to an element in the single repeat class : min f(l , n ) . if we get several elements that minimize this function , we select the one with the maximal number of subrepeats .
thus in our example ( figures 1 , 3,4,5 ) the prototype for class 1 is the longest repeat starting in position 77 , with l = 11 and n = 2 .
likewise , the prototype for class 2 is the repeat starting at position 23 , and for class 3 it is the repeat starting at position 38 .
we used this procedure in our studies of the genome sequences of a. thaliana   and rice bac end sequences [ 22 , 23 ] .
the 125 mb a. thaliana genome consists of five chromosomes ranging from 18 mb to 30 mb in length .
we applied the suffix tree algorithm for finding exact repeats to each of these sequences separately , and than used our clustering method to determine the repetitive structure of each chromosome .
we found from 100,000 to 400,000 pairs of exact repeats in each chromosome using a minimum length of 25 bp ( after filtering out simple repeat sequences ) .
these repeats in total represent approximately 10% of the chromosome sequences . to group the repeats into classes
the gap merging strategy was used , with a maximum gap size of less than 25 bp .
the algorithm finds some 5,0007,000 repeat classes per chromosome , but only 20% of these contain more than two elements .
arabidopsis is known to contain extensive gene duplication and strong evidence of a whole - genome duplication ; thus it is not surprising to observe such a preponderance of repeats with just two members .
we defined the prototype element for each class using the optimization procedure described above , combined all the prototypes from five chromosomes in one database , and generated a final classification of the whole genome by clustering the blast search results of all prototypes against all .
table 4 contains a summary of the repeat structure for the entire a. thaliana genome .
summary of repeat analysis of arabidopsis genome and rice bac end sequences to find out more about the composition of the arabidopsis repeats , each sequence was searched against atrepbase   and the arabidopsis gene database   ( using a maximum blast e - value of 0.01 and at least 100% identity for arabidopsis genes and at least 95% identity to atrep - base sequences ) . of 105,434 repeat sequences that fall into 27,961 separate repeat classes
, 2,124 sequences matched an annotated repeat sequence in atrepbase , and 25,149 sequences matched a segment of an arabidopsis gene . comparing both sets of matches ,
only 417 of the repeat sequences were found to match both a gene segment and an annotated repeat sequence .
the large number of repeats that match gene segments reflects the prevalence of segmental chromosomal duplications and tandem gene duplications in arabidopsis . due to the greedy ' merging with gap '
method used to build the repeat classes , relatively few of the repeat classes contained an abundance of the repeat sequences ; the largest repeat class contained 30,975 sequences of which 6,505 matched gene segments and 1,723 matched annotated repeats . to further analyze the composition of the repeat classes , a prototype repeat sequence was chosen to represent each repeat class containing at least five members , and the top database matches
examined , approximately half ( 755 ) matched gene segments and 58 matched annotated repeats .
the genes matched by the prototype repeat sequences include known members of large arabidopsis gene families including a cytochrome p450 , a receptor kinase , a disease - resistance protein and several transposon open reading frames .
in addition , there were many matches to hypothetical proteins , the validity of which remains to be determined .
prototype repeat sequences ( arabidopsis thaliana genome ) that matched genes or annotated atrepbase repeats yuan et al .  
recently reported on the construction of a rice repeat database that was generated by searching all available rice sequences for minisatellite sequences , mobile elements , rdna , centromeric repeat sequences and telomeric repeat sequences .
we attempted to use the repeat finding system described here to enlarge this set , using as input the large collection of sequences from the clemson university rice bac end database . unlike either arabidopsis or the microbial genomes , where a single genome sequence or a few large chromosomes were being processed , in this case we had 101,562 bac end sequences with an average length of approximately 400700 bp .
we therefore developed a special pre - processing procedure which generates a single sequence ( approximately 42 mb long ) from all the bac ends .
this procedure permits the algorithm to work with hundreds of thousands of different sequences simultaneously .
the system found 5,208,206 exact repeat pairs with lengths from 25 bp to 728 bp , where the latter represents an entire bac end that was repeated exactly .
the maximum length of each repeat was bounded by the length of the bac end sequence in which it was found .
this length restriction was added to the merging procedure to avoid artificially long repeats that might mistakenly span more than one bac end sequence .
the pre - clustering procedure also includes filtering of the exact repeats data to remove simple - sequence repeats , which were determined to comprise over 40% of exact repeats .
this resulted in 48,768 repeat classes , of which only 8,118 include more than two elements .
a searchable rice repeat database , based on the prototypes of these classes , is available online at . to test this new repeat database , we compared it to the set of annotated repeats based on known , expertly curated repeats .
there were four general groups in this set : telomere / centromere repeats , transposon / transposon - like repeats , rdna , and all the rest .
we used blast to search annotated repeats against the rice repeat database , using an e - value cutoff of 10 .
classification of the blast hits shows that the annotated repeats from the four distinct groups always fall into separate classes in the rice repeat database ; in other words , the new database divides the previous repeat classes into a finer - grained set of repeats , but it does not merge any of the four known groups together . because of the use of the efficient suffix tree procedures , the system runs very fast , with the all - versus - all blast search consuming approximately 80% of the computation time .
the running time of the exact repeat finder is about 1015% of the total , with the other processes - merging , clustering and post - blast updating - using a relatively minor proportion of overall computation time .
the running time depends on both the sequence length and the number of repeats ; for example , small microbial genomes take just 315 minutes , whereas the highly repetitive rice repeat database took about two days to process .
the memory needed for computation is dominated by the requirements of the suffix tree used for the initial repeats computation [ 11 , 12 , 13 ] ; this can grow to many gigabytes for large eukaryotic chromosomes .
our algorithm is based on first identifying all exact repeats in the input sequence , and then defining repeat classes by merging and extending these short exact matches .
an exact repeat is represented by pair of coordinates ( a1 , a2 ) delimiting its location in the genome sequence , and by the repeat length l. we implemented an algorithm that uses either of two suffix tree methods , repeatmatch   or reputer   to determine all the exact repeats in a given sequence .
( for more on suffix trees see . ) the computational time and space requirements for both these systems are linear in the size of the input sequences , an essential requirement for any algorithm attempting to process whole eukaryotic genomes .
the input to the system can be either a single genome sequence or a set of sequences .
the clustering procedure consists of the following steps , which are described in more detail below .
the list of coordinates of all exact repeats as output by repeatmatch or reputer can be interpreted as a partition of the original genome sequence .
we used reputer in the example and in the subsequent repeat analyses of microbial genomes ; for the a. thaliana genome and and the rice bac end - sequence data we used repeatmatch . )
each partition point has a reference to the pair coordinates ( a1 , a2 ) and the repeat length l. each repeat corresponds to at least two partition points .
some repeats can be found in the sequence more than twice , and the corresponding partition points can appear with different coordinates and different lengths . to prepare the data for the merging procedure , we sort the list of partition points in increasing order , and in the case of duplicate first coordinates , in increasing order of second coordinates .
( the clustering algorithm is order - independent ; however , the linear nature of repeat data allows us to use this pre - processing step to simplify the clustering procedure without affecting the final clusters . ) in particular cases it is useful to filter the original repeat data to remove certain types of repeats ; for example , simple one - base ( homopolymeric ) or two - base repeats . step 2 : merging procedure . in outline
, this procedure works by repeatedly merging together two exact repeats that either overlap or that occur within a limited distance ( a gap ) of each other .
specific values for the overlap and gap distance can be specified for each genome sequence .
whether the algorithm is merging repeats that overlap ( figure 2c ) , or merging repeats separated by a gap ( figure 2b ) , the new merging repeats will always have the property that significant subsequences of the repeat appear at least twice in the genome sequence . at the time of merging procedure
this map is based on a linked - list data structure , which allows for rapid and simple modifications to the dynamically changing repeat data .
every merging repeat in the map is linked by pointers to all the merging repeats with which it shares exact repeats .
each merging repeat will be assigned to a specific class if its list of references ( that is , the repeats that were combined into the merging repeat ) contains at least one repeat that already belongs to the class .
if a merging repeat has references that belong to multiple distinct classes , then those classes are combined into one .
if a merging repeat contains no references to an existing class , then the merging repeat forms a new class .
the initial classification is based on exact repeats . to merge together similar but non - exact repeats
, we use wu - blast [ 9 , 10 ] to search all merging repeats against all others .
the resulting matches between the classes are used as input to an update procedure which redistributes all merging repeats into new classes .
it is possible to skip this step if the initial repeat set contains approximate rather than exact repeats .
in this step , the output from reputer or repeatmatch is used to partition the original genome sequence . for each repeat
starting at coordinates a1 and a2 with length l , this list will include both ( a1 , a2 , l ) and ( a2 , a1 , l ) .
the list is then sorted by first and by second coordinates . to illustrate the method
the table on the left in figure 3 shows all seven pairs of repeats , while the right table shows the corresponding sorted partition points .
the table on the left shows repeat pairs that were found by reputer in the 180 bp example sequence shown in figure 1 using a minimum repeat length of 6 bp .
repeats are represented by type : forward ( f ) or reverse complement ( rc ) , first coordinates ( a1 , a2 ) and length ( la ) .
arrows show the correspondence between the repeat ( 67,153,6 ) and the two partition points ( 67,153,6 ) and ( 153,67,6 ) .
using the list of partition points , we begin merging exact repeats using the following criteria . given two partition points p1 = ( a1 , a2 , la ) and p2 = ( b1 , b2 , lb ) where a1 < b1 , we compute the distance between the non - overlapping repeats as d(p1 , p2 ) = max ( 0 , b1 - a1 - la + 1 ) .
next , given a maximum gap size g > 0 , the ' merging with gap ' protocol uses the rule that sequences corresponding to p1 and p2 are merged if the ' merging with overlap ' protocol only merges sequences that overlap one another ; that is they are at least partially identical .
we denote the overlap of two sequences as 0(p1 , p2 ) = max ( 0 , a1 + la - b1 + 1 ) for a1 < b1 then the criterion for ' merging with overlap ' is as follows : given a minimum overlap proportion op , where 0  op  1 , repeat points ( a1 , a2,la ) and ( b1 , b2 , lb ) are merged if at least one of the four repeats has overlap satisfying 0 ( p1 , p2 ) > op min ( la , lb ) . the parameter op is interpreted as a fraction of the shorter of the two repeats .
thus for op = 0.75 , we will merge two overlapped sequences if the length of their overlap is at least 75% of the length of the shorter sequence . using either merging procedure ,
if two sequences are merged then the new sequence will be defined as a merging repeat with starting position m = a1 and with length lm = max ( a1 + la , b1 + lb ) - a1 .
the merging procedure is not permitted to merge pairs of partition points of the form ( b1 , b2 , lb ) and ( b2 , b1 , lb ) .
this condition avoids merging of tandem repeats and avoids repetitiveness within the merging repeats . on the left side of figure 4
the extent of each merging repeat is shown by dividing sets of repeats using horizontal lines . merging procedure .
horizontal lines divide sets of exact repeats that were merged into a single merging repeat .
the arrow shows the connection between a group of two short exact repeats and the corresponding 11 bp merging repeat starting at position 77 .
this procedure , by updating and creating new references , leads to the repeat map shown on the right of figure 4 .
each merging repeat maintains references to the other merging repeats with which it shares exact repeats ; each exact repeat is assigned to the first merging repeat in which it appears . in our example , the merging repeat starting in coordinate 77 gets a reference to itself only , because its exact repeats have no previous references .
the next repeat , starting in position 116 , gets a reference to itself and to its mate the merging repeat 77 .
a data structure stores with each merging repeat its start coordinate , its length ( lm ) , the number of exact repeats it includes ( nm ) , and a list of references to itself and to other repeats ( r1 , r2 , r3 ) .
given the repeat map , we can begin to define classes by noting that if a merging repeat has at least one reference in common with another , then they belong to the same class .
, lm = ( 126,8 ) has two common references in two different classes , class 1 and class 5 .
these classes are then combined together into a new class 1 , which contains all references from both the original classes .
the gray rectangle in the repeat map table shows the merging repeat with its length , the number of exact repeats it includes , and references to the repeats it contains .
it contains references to class 1 ( 16 ) and class 5 ( 116 ) , marked by gray in the first classification table . on the next classification step ,
these two classes are merged and the rest of their references are added to the new class 1 .
for this step , the most time - consuming part of the algorithm , we use the underlying sequences of the merging repeats , and run a blast search of all sequences against all others .
classes are merged if any of their underlying sequences have a blast e - value less then a user - specified threshold when compared to any sequence in another class .
if a class appears in multiple similarity pairs , all these similar classes are merged with the original class .
for the example in figure 4 , blast searches do not reveal any new similarity pairs ; thus the classification from the figure is identical to the final classification ( table 1 ) .
table 2 summarizes the repeat analysis for the neisseria meningitidis genome   using two different clustering criteria .
it illustrates how increasing the exact repeat size in the initial step leads to fewer merging repeats and fewer classes .
it also shows how reducing the size of the gap and increasing the required overlap increases the number of repeat classes , as would be expected .
sensitivity of the clustering method to different merging parameters the length of the neisseria meningitidis genome is 2,272,351 bp . for a more comprehensive repeat analysis
, we chose seven different microbial genomes , using 25 base pairs ( bp ) as the minimal exact repeat length and allowing less than a 25 bp gap for the merging procedure .
it presents the number of merging repeats , the number of repeat classes , the longest single merging repeat , and the number of classes containing more than two members . as shown here , these latter classes comprise only 1025% of all repeat classes , indicating that most repeat types are simple duplications . among these duplication ,
the vast majority occur in tandem , although this is not shown in table 3 .
the picture given here shows how repeat analysis can quickly provide an overall picture of how repetitive a genome is ; in addition , the analysis extracts the repeats themselves for further analysis .
small microbial genomes have relatively few types of repeats , and relatively few copies of each type . in contrast , our studies of longer eukaryotic genome sequences have uncovered tens of thousands of repeat classes and hundreds of thousands of merging repeats . in order to be able to process this data efficiently - in particular , in order to run the procedure where
all classes are compared against each other using blast - we developed a procedure to define the most representative element for each class , which we call its prototype . referring to the repeat map shown in figure 5 , we use the length of the merging repeat ( lm ) and the number of exact repeats ( nm ) to defined the desirable properties for the prototype .
thus , in the ' merging with gap ' procedure , the merging repeats with the longest lengths and with the greatest number of subrepeats should be the best candidates to represent the class . in this case
when we use the ' merging with overlap ' procedure , we also look for the greatest number of subrepeats , but the length of the most representative repeat should be closer to the shortest repeat in the class . in this case
the representative element will tend to match across most of its length to every member of the class . using these considerations
for each class , given the merging repeat length l ( lm ) and number of subrepeats n ( nm ) , the maximum and the minimum repeat lengths in the class ( lmax and lmin ) , and the maximum and the minimum number of subrepeats in the class ( nmax and nmin ) , we define the function f(l , n ) for each merging repeat of the class as for ' merging with gaps ' and for ' merging with overlaps ' .
this non - negative function is a summary of the variance in the length and number of subrepeats from the desirable values for the class prototype .
then we solve the optimization problem of minimizing function f(l , n ) : find ( l , n ) corresponding to an element in the single repeat class : min f(l , n ) . if we get several elements that minimize this function , we select the one with the maximal number of subrepeats . thus in our example ( figures 1
, 3,4,5 ) the prototype for class 1 is the longest repeat starting in position 77 , with l = 11 and n = 2 .
likewise , the prototype for class 2 is the repeat starting at position 23 , and for class 3 it is the repeat starting at position 38 .
we used this procedure in our studies of the genome sequences of a. thaliana   and rice bac end sequences [ 22 , 23 ] .
the 125 mb a. thaliana genome consists of five chromosomes ranging from 18 mb to 30 mb in length .
we applied the suffix tree algorithm for finding exact repeats to each of these sequences separately , and than used our clustering method to determine the repetitive structure of each chromosome .
we found from 100,000 to 400,000 pairs of exact repeats in each chromosome using a minimum length of 25 bp ( after filtering out simple repeat sequences ) .
these repeats in total represent approximately 10% of the chromosome sequences . to group the repeats into classes
the gap merging strategy was used , with a maximum gap size of less than 25 bp .
the algorithm finds some 5,0007,000 repeat classes per chromosome , but only 20% of these contain more than two elements .
arabidopsis is known to contain extensive gene duplication and strong evidence of a whole - genome duplication ; thus it is not surprising to observe such a preponderance of repeats with just two members .
we defined the prototype element for each class using the optimization procedure described above , combined all the prototypes from five chromosomes in one database , and generated a final classification of the whole genome by clustering the blast search results of all prototypes against all .
table 4 contains a summary of the repeat structure for the entire a. thaliana genome .
summary of repeat analysis of arabidopsis genome and rice bac end sequences to find out more about the composition of the arabidopsis repeats , each sequence was searched against atrepbase   and the arabidopsis gene database   ( using a maximum blast e - value of 0.01 and at least 100% identity for arabidopsis genes and at least 95% identity to atrep - base sequences ) . of 105,434 repeat sequences that fall into 27,961 separate repeat classes
, 2,124 sequences matched an annotated repeat sequence in atrepbase , and 25,149 sequences matched a segment of an arabidopsis gene . comparing both sets of matches ,
only 417 of the repeat sequences were found to match both a gene segment and an annotated repeat sequence .
the large number of repeats that match gene segments reflects the prevalence of segmental chromosomal duplications and tandem gene duplications in arabidopsis .
due to the greedy ' merging with gap ' method used to build the repeat classes , relatively few of the repeat classes contained an abundance of the repeat sequences ; the largest repeat class contained 30,975 sequences of which 6,505 matched gene segments and 1,723 matched annotated repeats . to further analyze the composition of the repeat classes , a prototype repeat sequence was chosen to represent each repeat class containing at least five members , and the top database matches
examined , approximately half ( 755 ) matched gene segments and 58 matched annotated repeats .
the genes matched by the prototype repeat sequences include known members of large arabidopsis gene families including a cytochrome p450 , a receptor kinase , a disease - resistance protein and several transposon open reading frames .
in addition , there were many matches to hypothetical proteins , the validity of which remains to be determined .
.   recently reported on the construction of a rice repeat database that was generated by searching all available rice sequences for minisatellite sequences , mobile elements , rdna , centromeric repeat sequences and telomeric repeat sequences .
we attempted to use the repeat finding system described here to enlarge this set , using as input the large collection of sequences from the clemson university rice bac end database . unlike either arabidopsis or the microbial genomes , where a single genome sequence or a few large chromosomes were being processed , in this case we had 101,562 bac end sequences with an average length of approximately 400700 bp .
we therefore developed a special pre - processing procedure which generates a single sequence ( approximately 42 mb long ) from all the bac ends .
this procedure permits the algorithm to work with hundreds of thousands of different sequences simultaneously .
the system found 5,208,206 exact repeat pairs with lengths from 25 bp to 728 bp , where the latter represents an entire bac end that was repeated exactly .
the maximum length of each repeat was bounded by the length of the bac end sequence in which it was found .
this length restriction was added to the merging procedure to avoid artificially long repeats that might mistakenly span more than one bac end sequence .
the pre - clustering procedure also includes filtering of the exact repeats data to remove simple - sequence repeats , which were determined to comprise over 40% of exact repeats .
this resulted in 48,768 repeat classes , of which only 8,118 include more than two elements .
a searchable rice repeat database , based on the prototypes of these classes , is available online at . to test this new repeat database , we compared it to the set of annotated repeats based on known , expertly curated repeats .
there were four general groups in this set : telomere / centromere repeats , transposon / transposon - like repeats , rdna , and all the rest .
we used blast to search annotated repeats against the rice repeat database , using an e - value cutoff of 10 .
classification of the blast hits shows that the annotated repeats from the four distinct groups always fall into separate classes in the rice repeat database ; in other words , the new database divides the previous repeat classes into a finer - grained set of repeats , but it does not merge any of the four known groups together .
because of the use of the efficient suffix tree procedures , the system runs very fast , with the all - versus - all blast search consuming approximately 80% of the computation time .
the running time of the exact repeat finder is about 1015% of the total , with the other processes - merging , clustering and post - blast updating - using a relatively minor proportion of overall computation time .
the running time depends on both the sequence length and the number of repeats ; for example , small microbial genomes take just 315 minutes , whereas the highly repetitive rice repeat database took about two days to process .
the memory needed for computation is dominated by the requirements of the suffix tree used for the initial repeats computation [ 11 , 12 , 13 ] ; this can grow to many gigabytes for large eukaryotic chromosomes .
we describe a new system for rapid identification of all repeats in genome sequences and assignment of these repeats to similarity classes . the system has been used to analyze the repeat structure of several complete microbial genomes , and the much larger genome of the model plant a. thaliana .
we also used it to create a new rice repeat database , based on an analysis of a large bac end sequence database .
this new computational tool should prove helpful in the analysis of repeat structure for both complete and partial genome sequences .
shumway for helpful comments , suggestions and discussion . this work was supported in part by nsf grants kdi-9980088 and iis-9902923 and by nih grant r01-lm06845 .
 backgrounda computational system for analysis of the repetitive structure of genomic sequences is described . 
 the method uses suffix trees to organize and search the input sequences ; this data structure has been used previously for efficient computation of exact and degenerate repeats.resultsthe resulting software tool collects all repeat classes and outputs summary statistics as well as a file containing multiple sequences ( multi fasta ) , that can be used as the target of searches . 
 its use is demonstrated here on several complete microbial genomes , the entire arabidopsis thaliana genome , and a large collection of rice bacterial artificial chromosome end sequences.conclusionswe propose a new clustering method for analysis of the repeat data captured in suffix trees . 
 this method has been incorporated into a system that can find repeats in individual genome sequences or sets of sequences , and that can organize those repeats into classes . 
 it quickly and accurately creates repeat databases from small and large genomes . 
 the associated software ( repeatfinder ) , should prove helpful in the analysis of repeat structure for both complete and partial genome sequences . 
Background
Results and discussion
Algorithm description
Step 1: Pre-processing
Step 2: Merging and repeat map generation
Step 3: Classification
Step 4: BLAST searches and further merging
Repeat analysis of microbial genomes
Defining the prototype for a repeat class
Repeat structure of the 
Rice repeat database
Performance
Conclusions
Acknowledgements