Landau G M, Vishkin U, Nussinov R
Nucleic Acids Res. 1986 Jan 10;14(1):31-46. doi: 10.1093/nar/14.1.31.
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(k2n) time. For long sequences the gain factor over the currently used algorithms is very large.
有一些算法旨在解决长度为m的一个序列（模式）与另一个更长的长度为n的序列（文本）的最优比对问题。这些算法允许错配、删除和插入。迄今为止的算法运行时间为O(mn)。我们定义一个整数k，它是允许的最大差异数。我们提出一种简单算法，表明序列可以在O(k²n)时间内进行最优比对。对于长序列，相对于当前使用的算法，增益因子非常大。
