title: Space efficient computation of rare maximal exact matches between multiple sequences.
abstract: In this article, we propose a new method for computing rare maximal exact matches between multiple sequences. A rare match between k sequences S(1), ... , S(k) is a string that occurs at most t(i)-times in the sequence S(i), where the t(i) > 0 are user-defined thresholds. First, the suffix tree of one of the sequences (the reference sequence) is built, and then the other sequences are matched separately against this suffix tree. Second, the resulting pairwise exact matches are combined to multiple exact matches. A clever implementation of this method yields a very fast and space efficient program. This program can be applied in several comparative genomics tasks, such as the identification of synteny blocks between whole genomes.
authors: Faculty of Engineering and Computer Sciences, University of Ulm, Ulm, Germany. enno.ohlebusch@uni-ulm.de
authors: Enno
authors: E
authors: Ohlebusch
authors: Stefan
authors: S
authors: Kurtz
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology; D030561:Databases, Nucleic Acid; D023281:Genomics; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods*