序列比对（二） 局部比对算法以及两种空位插入的优化策略

引言

上篇讲的Needleman-Wunsch算法是一种全局比对算法，也就是会将两条序列的所有部分都考虑进来。但针对短序列比对到长序列时，这种全局比对算法就不太合适了。也就是说，我们需要一种序列比对算法可以解决这种局部比对的问题。其实局部比对算法可以说是，全局比对算法的一种变型，下面我们来介绍具体的算法，Smith-Waterman算法。同时，也会介绍两种优化的策略：末端空位自由比对和空段罚分比对。这两种策略都是对于空位的插入罚分的优化，可以让空段合理连续插入并且可以在首位和末尾插入。

算法介绍

（1）Smith-Waterman算法

Smith-Waterman算法与Needleman-Wunsch算法的步骤基本一致，主要在以下三个方面做了调整：

1.初始化相似性分数矩阵时，与空位的相似性分数都为0；

2.计算相似性分数，考虑三个方向的最大值时，最小值为0；

3.回溯时，遇到0则停止。

（2）末端空位自由比对

末端空位自由比对与全局比对算法一致，主要在以下方面做了调整：

1.初始化相似性分数矩阵时，与空位的相似性分数都为0；

2.回溯时，从最后一列和最后一行的最大值开始回溯。

（3）空段罚分比对

空段罚分比对主要是在迭代计算相似性分数方法上进行了优化，在空段罚分时，考虑了该位置周围的比对情况，对相应的位置的罚分进行了校正。
其中，在考虑空段时，插入空位和空位延伸给予了不同的罚分，Ws表示空位插入的罚分，Wg表示的是空位延伸的罚分，所以在初始化的过程中就会考虑空位的延伸问题，而不是将每一个空位的罚分都设为固定值。

具体迭代计算规则如下：

V(i,j) = Max(M(i,j),E(i,j),F(i,j))

M(i,j) = Max(M(i-1,j-1)+S(D,Q),E(i-1,j-1)+S(D,Q),F(i-1,j-1)+S(D,Q))

E(i,j) = Max(M(i,j-1)+Ws+Wg,E[i,j-1]+Ws)

F(i,j) = Max(M(i-1,j)+Ws+Wg,F(i-1,j)+Ws)

总结

以上算法介绍部分的（2）和（3）是比对中引入的两种策略，这两种策略可以添加到全局比对和局部比对中去，都是对空位的处理方式的一种优化。