An efficient string matching algorithm with K substitutions for nucleotide and amino acid sequences.
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.
Landau
G M
GM
Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Israel.
Vishkin
U
U
Nussinov
R
R
D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D004247:DNA; D011506:Proteins; D012689:Sequence Homology, Nucleic Acid
D011506:Proteins; D004247:DNA