1.4. 本地对齐¶
“局部比对”的概念由 Smith & Waterman 提出。两个序列的局部比对是这两个序列部分之间的比对。两个蛋白质可能仅共享一段高度序列相似的区域，但在该区域之外非常不同。此类序列的全局（N-W）比对将具有：(i) 在高度序列相似区域中有大量匹配 (ii) 在相似区域之外有大量错配和空位（插入/删除）。因此，寻找最佳局部比对是有意义的。
输入: 这两个序列可能相关，也可能不相关。
目标: 确定一个序列中的子字符串是否与另一个序列中的子字符串高度相关。
算法：史密斯-沃特曼动态规划
应用场景 ：在大型序列（如新测序的基因组）中寻找局部相似性。在两个蛋白质中寻找保守的结构域或模式。
局部对齐算法由3个步骤组成：
初始化得分矩阵和回溯矩阵 • 计算得分并填充得分矩阵和回溯矩阵 • 从回溯矩阵推断排列 •
我们有两个二维矩阵： 得分矩阵 和 回溯矩阵 。
1.4.1. 评分矩阵¶
在本地对齐时：
初始化第一行和第一列为0，因为所有负值都转换为0，并且我们根据间隙惩罚填充第一行和第一列。
最佳局部对齐的分数是整个数组中最大值。
1.4.2. 回溯分析¶
要找到实际的局部对齐：
从最高分项开始访问
反向追踪如常
当我们到达一个分数为 0 的条目时，停止
