Smith–Waterman algorithm
首先需要澄清一个事实，Smith–Waterman algorithm是求两个序列的最佳subsequence匹配，与之对应的算法但是求两个序列整体匹配的算法是Needleman-Wusch algorithm，即
Smith–Waterman algorithm：Local
Needleman-Wusch algorithm: Global
Needleman-Wusch algorithm与longest common subsequence (LCS)很相似，最大差别在于它给LCS中增、减、替换等操作赋予了不同的负权值，甚至不同的匹配对(a,a),(b,b)也有不同的正权值。可以这么说，Needleman-Wusch algorithm是改进的LCS算法。主要解决如下谁最优的问题：
首先，Needleman-Wusch algorithm需要一个Score Matrix（可以看成是一个离散的损失函数），用来表示不同匹配对的权值。
类似LCS，用动态规划求解，状态转移方程如下：
以上为Needleman-Wusch algorithm的步骤，计算局部的Smith–Waterman algorithm只需找到最大的M[i][j]，然后回溯即可，
[Sequence Alignment Methods] Smith–Waterman algorithm
原文：http://www.cnblogs.com/littletail/p/5210568.html