Exhaustive whole-genome tandem repeats search.
BACKGROUND
Approximate tandem repeats (ATR) occur frequently in the genomes of organisms, and are a source of polymorphisms observed in individuals, and thus are of interest to those studying genetic disorders. Though extensive work has been done in order to identify ATRs, there are inherent limitations with the current approaches in terms of the number of pattern sizes that can be searched or the size of the input length.


RESULTS
This paper describes (1) a new algorithm which exhaustively finds all variable-length ATRs in a genomic sequence and (2) a precise description of, and an algorithm to significantly reduce, redundancy in the output. Our ATR definition is parameterized by a mismatch ratio p which allows for more mismatches in longer tandem repeats (and fewer in shorter). Furthermore, our algorithm is embarrassingly parallel and thus can attain near-linear speed-up on Beowulf clusters. We present results of our algorithm applied to sequences of widely differing lengths (from genes to chromosomes).


BACKGROUND
Source and binaries are available on request.
Krishnan
Arun
A
Bioinformatics Institute, 30 Biopolis Street, No. 07-01, Matrix, Singapore 138671, Singapore. arun@bii.a-star.edu.sg
Tang
Francis
F
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D020080:Tandem Repeat Sequences / Q000235:genetics*