Waterman M S
J Theor Biol. 1984 Jun 7;108(3):333-7. doi: 10.1016/s0022-5193(84)80037-5.
Sequence alignments are becoming more important with the increase of nucleic acid data. Fitch and Smith have recently given an example where multiple insertion/deletions (rather than a series of adjacent single insertion/deletions) are necessary to achieve the correct alignment. Multiple insertion/deletions are known to increase computation time from O(n2) to O(n3) although Gotoh has presented an O(n2) algorithm in the case the multiple insertion/deletion weighting function is linear. It is argued in this paper that it could be desirable to use concave weighting functions. For that case, an algorithm is derived that is conjectured to be O(n2).
随着核酸数据的增加，序列比对变得越来越重要。菲奇和史密斯最近给出了一个例子，其中需要多个插入/缺失（而不是一系列相邻的单个插入/缺失）才能实现正确的比对。已知多个插入/缺失会将计算时间从O(n2)增加到O(n3)，尽管后藤在多个插入/缺失加权函数为线性的情况下提出了一种O(n2)算法。本文认为使用凹加权函数可能是可取的。对于这种情况，推导了一种推测为O(n2)的算法。
