[Sequence Alignment Methods] Smith–Waterman algorithm

时间:2022-07-11 09:03:19

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算法。主要解决如下谁最优的问题:

[Sequence Alignment Methods] Smith–Waterman algorithm

首先,Needleman-Wusch algorithm需要一个Score Matrix(可以看成是一个离散的损失函数),用来表示不同匹配对的权值。

[Sequence Alignment Methods] Smith–Waterman algorithm

类似LCS,用动态规划求解,状态转移方程如下:

[Sequence Alignment Methods] Smith–Waterman algorithm

以上为Needleman-Wusch algorithm的步骤,计算局部的Smith–Waterman algorithm只需找到最大的M[i][j],然后回溯即可,

[Sequence Alignment Methods] Smith–Waterman algorithm