在利用动态规划进行全局比对(二)中我们探讨了两条序列全局比对的算法原理。 这一算法是由芝加哥的Needleman和Wunsch两位于上个世纪70年代初提出的。 也常被称之为Needleman-Wunsch算法。 如前所述，这个算法可以针对用户指定的打分函数，确定性地找出两条序列间的最优比对。这一算法在早期的蛋白质序列比对中得到了广泛的应用。
然而随着生物学的发展，人们发现有的蛋白序列虽然在序列整体上表现出较大的差异性，但是在某些局部区域能独立的发挥相同的功能，序列相当保守。这时候依靠全局比对明显不能得到这些局部相似序列的。其次，在真核生物的基因中，内含子片段表现出了极大变异性，外显子区域却较为保守，这时候全局比对表现出了其局限性，无法找出这些局部相似性序列。
于是， 在1981年当时物理学家Temple Smith和数学家Michael Waterman对之前的Needle-Wunsch算法进行了改进，提出了后来被称之为Smith-Waterman的局部比对算法。局部比对算法与全局比对算法在状态转移方程（也即二中所述的填网格的公式）较为相似，只是在公式右边多加了一项：当原先的三个公式的取值都小于0时，则在当前位置填入0。这时公式就是下面这样的了：
image.png
如图，上面表示的是全局比对的公式，下面表示的是局部比对的公式，两个的差别仅仅也只是多了一个0。然而正是这个0使得比对的得分有了一个止损下限。 Smith-Waterman算法实质上提供了在差异过大区域之后“重启”比对的能力。 从而可以有效地发现局部水平上的相似性。
参考：北京大学公开课——生物信息学: 导论与方法
网友评论