动态规划（有向无环图）——一种算法

大问题划分为小问题。理查德.贝尔曼1957年提出的一种表格处理方法，自底向上先求解最小子问题，把结果储存在表格种，求解大子问题时可以用已求解的小问题，提高效率。
使用动态规划的条件：最优子结构（最优解所包含的子问题的解也是最优的）；子问题重叠（子问题之间不是独立的）；无后效性
（1）状态表示
（2）阶段划分
（3）状态转移方程式核心
（4）边界条件
（5）求解目标：max、min

图片.png

三个箭头都算一遍，求极大值，斜线是配对（包含错配），横线代表横的那条序列和空缺比对，竖线代表竖的那条序列和空缺比对，据此算分

看看老师用excel做DP alignment，很酷啊：
首先，第一个表先规定：A和G配对0分，C和T配对0分，交叉配对-1分，匹配1分，gap0分

图片.png

腺嘌呤（A）、鸟嘌呤（G）、胸腺嘧啶（T）和胞嘧啶（C）。

然后，第二个表来做匹配不匹配的算分（要用到第一个表）：

每一格的分数是怎么算出来的呢？

用下面公式

图片.png

解释：
=INDEX(选中第一个表中的分数区域，匹配行号，匹配列号)
=MATCH(lookup_value, lookup_array, [match_type])
lookup_value：表示你要查找的数值；
lookup_array：表示你要查找的范围；
[match_type]：可选参数，数值-1、0、1三个参数；（如果不填写默认是1）。1表示会查找小于或等于“lookup_value”的最大值；
0表示会查找等于“lookup_value”的第一个值；
-1表示会查找大于或等于“lookup_value”的最小值；

第三个表来算最大的得分：

图片.png

第四个表来算得到最大得分的路径：

图片.png

最后一个表就可以回溯回去了：

图片.png

SEARCH(find_text,within_text,[start_num]),返回的是第一个文本字符串的起始位置的编号
ISNUMBER函数，只有一个参数value，表示进行检验的内容，如果检验的内容为数字，将返回TRUE，否则将返回FALSE。
And函数，所有参数的逻辑值为真时，返回TRUE；只要有一个参数的逻辑值为假，即返回 FALSE。

最后，表在这里：https://www.dropbox.com/s/ksh4qfl5eb182p6/Lecture02_DP%20Alignment%20In%20Excel.xlsx?dl=0
大家可以自己下载下来慢慢琢磨，挺厉害的。

（MIT 6.047 | 基因组学机器学习(2020·完整版)-第二课）