title: Efficient q-gram filters for finding all epsilon-matches over a given length.
abstract: Fast and exact comparison of large genomic sequences remains a challenging task in biosequence analysis. We consider the problem of finding all epsilon-matches between two sequences, i.e., all local alignments over a given length with an error rate of at most epsilon. We study this problem theoretically, giving an efficient q-gram filter for solving it. Two applications of the filter are also discussed, in particular genomic sequence assembly and BLAST-like sequence comparison. Our results show that the method is 25 times faster than BLAST, while not being heuristic.
authors.affiliation: International NRW Graduate School in Bioinformatics and Genome Research, Center of Biotechnology, Universität Bielefeld, Germany.
authors.forename: Kim R
authors.initials: KR
authors.lastname: Rasmussen
authors.forename: Jens
authors.initials: J
authors.lastname: Stoye
authors.forename: Eugene W
authors.initials: EW
authors.lastname: Myers
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D030561:Databases, Nucleic Acid; D016678:Genome; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000706:statistics & numerical data*