title: An efficient algorithm for finding short approximate non-tandem repeats.
abstract: We study the problem of approximate non-tandem repeat extraction. Given a long subject string S of length N over a finite alphabet Sigma and a threshold D, we would like to find all short substrings of S of length P that repeat with at most D differences, i.e., insertions, deletions, and mismatches. We give a careful theoretical characterization of the set of seeds (i.e., some maximal exact repeats) required by the algorithm, and prove a sublinear bound on their expected numbers. Using this result, we present a sub-quadratic algorithm for finding all short (i.e., of length O(log N)) approximate repeats. The running time of our algorithm is O(DN(3pow(epsilon)-1)log N), where epsilon = D/P and pow(epsilon) is an increasing, concave function that is 0 when epsilon = 0 and about 0.9 for DNA and protein sequences.
authors.affiliation: Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, Tübingen, 72076, Germany. adebiyi@informatik.uni-tuebingen.de
authors.forename: E F
authors.initials: EF
authors.lastname: Adebiyi
authors.forename: T
authors.initials: T
authors.lastname: Jiang
authors.forename: M
authors.initials: M
authors.lastname: Kaufmann
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D030541:Databases, Genetic; D012091:Repetitive Sequences, Nucleic Acid