Fickett J W
Nucleic Acids Res. 1984 Jan 11;12(1 Pt 1):175-9. doi: 10.1093/nar/12.1part1.175.
We show how to speed up sequence alignment algorithms of the type introduced by Needleman and Wunsch (and generalized by Sellers and others). Faster alignment algorithms have been introduced, but always at the cost of possibly getting sub-optimal alignments. Our modification results in the optimal alignment still being found, often in 1/10 the usual time. What we do is reorder the computation of the usual alignment matrix so that the optimal alignment is ordinarily found when only a small fraction of the matrix is filled. The number of matrix elements which have to be computed is related to the distance between the sequences being aligned; the better the optimal alignment, the faster the algorithm runs.
我们展示了如何加速由Needleman和Wunsch提出（并由Sellers等人推广）的那种类型的序列比对算法。虽然已经引入了更快的比对算法，但总是以可能得到次优比对为代价。我们的修改使得仍然能够找到最优比对，而且通常所需时间仅为原来的十分之一。我们所做的是重新安排常规比对矩阵的计算顺序，这样通常在矩阵只填充了一小部分时就能找到最优比对。必须计算的矩阵元素数量与要比对的序列之间的距离有关；最优比对越好，算法运行得就越快。
