title: An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences.
abstract: Given a text of length n, a pattern of length m and an integer k, we present an algorithm for finding all occurrences of the pattern in the text, each with at most k substitutions. The algorithm runs in O(k(m log m + n)) time, and requires O(nk) space. This algorithm has direct implications for nucleotide and amino acid sequence comparisons.
authors: Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Israel.
authors: G M
authors: GM
authors: Landau
authors: U
authors: U
authors: Vishkin
authors: R
authors: R
authors: Nussinov
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D004247:DNA; D011506:Proteins; D012689:Sequence Homology, Nucleic Acid
chemical_list: D011506:Proteins; D004247:DNA