An efficient string matching algorithm with k differences for nucleotide and amino acid sequences
1986
Landau, G.M. | Vishkin, U. | Nussinov, R.
There are a few algorithms designed to solve the problem of the optimal alignment of one sequence, the pattern, of length m, with another, longer sequence the text, of length n. These algorithms allow mismatches, deletions and insertions. Algorithms to date run in O(mn) time. Let us define an integer, k, which is the maximal number of differences allowed. We present a simple algorithm showing that sequences can be optimally aligned in O(k(2)n) time. For long sequences the gain factor over the currently used algorithms is very large.
显示更多 [+] 显示较少 [-]AGROVOC关键词
书目信息
出版者
Elsevier Inc.
其它主题
Nucleotide sequences; Computer analysis; Amino acid sequence; Base sequence
语言
英语
注释
In the special issue: applications of computers to research on nucleic acids.
类型
Journal Article; Text
2024-02-28
MODS