一周总结

Needleman and Wunsch

Landau-Vishkin

博客链接

Smith and Waterman

打分阶段分数不为负非常重要，这使得Smith and Waterman算法支持对序列进行局部比对。

当任何一个位置的分数低于0时，代表之前的序列没有相似性，达到了“重设”的效果，让从这个位置开始的比对不受之前的影响。

由于Needleman and Wunsch考虑的是整个序列，所以空位也需要罚分。

Ukkonen

Hirschberg

Hirschberg算法通过分治的思想，使用递归计算矩阵每个点的分数，将空间复杂度优化到了O(min{m,n})，不过没有对时间复杂度产生优化。

该算法用于进行全局比对。

Myers and Miller

将Hirschberg算法进行了改进，增加了间隙惩罚。

Myers bit-vector algorithm

该算法将Needleman and Wunsch的分数矩阵的计算过程进行转化，将二维DP转化为向量的形式。

首先想到，这个分数矩阵实际上只需要两行就能算出所有答案了，所以只需要考虑两行之间的转换。

将罚分全部统一为0或1（如：Ins/Del的分数是1，Match的分数是0），可以想到，在相邻的两个格子的更新中，可以用值为0/1的多维向量表示更新过程。（向量的每一维是罚分的一种操作，如Match/Instert）

然后，把这种值为0/1的向量用一个字长表示出来，一个unsigned long long就可以表示一种操作在各个位置的向量值，再增加几个这种unsigned long long，就可以利用位运算进行矩阵更新。