1.3. 全局比对¶
动态规划算法 ：
可以构造一张隐含包含所有可能比对的图表，其形式是一个矩阵，类似于绘制点阵图时所用的矩阵。一条 序列 的残基作为行索引，另一条序列的残基作为列索引。矩阵中从左上到右下的任意一条路径都对应一种比对。
动态规划 是一种通过把两条序列之间所有可能的字符对进行匹配来确定“最优比对”的方法。
它与点阵方法在本质上是相似的，因为二者都会创建一个二维比对网格。不过，它以更定量的方式寻找比对：把点阵转换成一个计分矩阵，以计入序列之间的匹配与错配。通过在该矩阵中搜索最高得分的集合，就能准确地得到最佳比对。
动态规划如何工作 ？
动态规划的工作方式是：先构造一个二维矩阵，其两条轴分别是要比较的两条序列。残基的匹配依据某个特定的计分矩阵。得分逐行计算。首先用一条序列的第一行，去扫描另一条序列的整个长度，然后扫描第二行。匹配得分随之计算出来。第二行的扫描会考虑第一轮中已经得到的分数。这一过程反复进行，直到所有单元格的值都被填满。于是，分数沿着从左上角到右下角的对角线累积。一旦分数在矩阵中累积完毕，下一步就是找出代表最优比对的那条路径。这要 从矩阵的右下角开始，沿相反顺序回溯穿过矩阵，直至矩阵左上角的原点。最佳匹配路径就是总得分最大的那条路径。如果两条或更多路径达到相同的最高得分，就任意选取其中一条作为最佳比对。路径在某个位置也可以水平或垂直移动，这对应于为两条序列之一引入一个空位，即一次插入或删除。
比对图的动态规划递推式 ：
成对序列比对的总体目标 ：
是找出两条序列的最佳配对，使残基之间具有最大的一致性。为了实现这一目标，需要将一条序列相对于另一条平移，找到匹配数最多的位置。常用的两种不同比对策略是：全局比对与局部比对。
全局比对的动态规划 ：
在全局比对中，假定要比对的两条序列在整个长度上大体相似。
比对从两条序列的开头进行到末尾，以在两条序列的整个长度上找到尽可能最佳的比对。
要比对的两条序列长度可以不同。
它必须从两条序列的开头延伸到末尾，才能获得最高的总得分。换言之，比对路径必须从矩阵的右下角走到左上角。专注于为全长序列比对取得最高得分，其缺点是可能错过最佳的局部相似性。
对于差异较大的序列，或结构域不同的序列，该方法无法产生最优比对。
全球一对一比对的少数网络服务器之一是“GAP”。
使用动态规划的经典全局成对比对算法是 Needleman–Wunsch 算法。在该算法中，最优比对是在两条序列的整个长度上获得的。
全局比对问题 ：在给定计分矩阵下，求两个字符串得分最高的比对。
输入 ：两个字符串以及计分矩阵 score。
输出 ：两个字符串的一种比对，其比对得分在二者的所有比对中最大。
要解决全局比对问题 ：
Needleman–Wunsch 算法更适用于 ：
比对两条长度大致相同、亲缘关系密切的序列。
对于差异较大的序列和长度可变的序列，该方法可能无法产生最优结果，因为它无法识别两条序列之间高度相似的局部区域。
NEEDLEMAN-WUNSCH 算法包含三个步骤 ：
1. 初始化得分矩阵与回溯矩阵 ：
在初始化过程中，得分矩阵和回溯矩阵的第一行与第一列被初始化。
2. 计算得分并填写得分矩阵与回溯矩阵 ：
下一步是迭代地求出结果矩阵中所有元素的得分值。
3. 从回溯矩阵推断比对 ：
回溯是从回溯矩阵推导出最佳比对的过程。
回溯总是从最后一个单元格（右下角，最高得分所在处）开始，一直进行到左上角。
推导最佳比对：
沿回溯路径有三种可能的移动：
对角：两条序列的字母对齐。
左：向左序列引入一个空位。
上：向上序列引入一个空位。
我们有两个二维矩阵：得分矩阵和回溯矩阵。
