Question

生物学中常用的两种动态规划算法

Answer 1

动态规划算法(Dynamic Programming Algorithm)是一种计算方法，它的主要思路是把一个问题分成若干个小问题来解决

在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局部比对）

（1）全局序列比对：

1）两条序列可以在一个x- 和y-轴的矩阵中得到比对；

2）如果序列一致，则可以得到一条通过对角线的路径；

3）寻找最佳的次路径，然后将它们加起来得到最好的得分，

这包括：

需要时插入空隙（gap）

允许保守替代

选择打分系统（简单的或复杂的）

Needleman-Wunsch算法可以保证得到最佳的比对

（2）局部序列比对：局部比对的目标是寻找两序列最优比对区（子序列），不需要延伸到序列的两端；局部比对是数据库搜索是最常用的算法，在寻找序列之间的结构域时相当有用。 1）Smith-Waterman 算法

1. 设置一个矩阵，大小为（m+1, n+1）

2. 矩阵中的值必须不小于0。

3. 矩阵中的每个单元格的分值S是以下四者中的最大值：

1. 算法的目的是寻找矩阵中的最大值，这代表了比对中的结尾处（羧基端）。

2. 回溯过程从最大值的位置开始，沿着对角线向上向左直到碰到一个零分值的单元格。

3. 算法需要的一个条件是随机匹配的期望分值为负，保证不相关的长序列不能得到高分值（大多打分矩阵满足此条）