序列比对（八）第一部分的小结

现在想来，动态规划最适用于这一类问题：即复杂系统的最终结果分多步实现，每一步的状态与上一步（或上几步）有关。

具体来说，动态规划算法运用到序列比对的关键部分有三个：

1. 初始条件的设置：比如 F(i, 0) 以及 F(0, j) 控制着是否要对头部序列进行罚分。全局比对中是要罚分的，而交叉比对就不需要罚分。
2. 迭代方程的建立。这一步最关键，如何选择一个清晰有效好实现的迭代元素需要仔细考量。
3. 终止条件的确立。以得分矩阵而言，全局比对回溯的终止条件是到达F(0, 0)，而局部比对是到达分值为0的单元，交叉比对则是到达F(i, 0)或者F(0, j)的行或列。

说是第一部分的小结，是这一部分内容的序列比对都是建立在一个简单的概率论模型（比对分值就是对数机率比）上的。后面的文章可能会涉及到新的概率论模型，因而会有新的比对方法。