DNA

1) Sequence Alignment：两个字符序列，允许的操作是插入"-"，目标是使得对其的字母最多，但是加入"-"要接受惩罚。

初始字符串

加入"-"使得对齐的字符更多

可以看成A, B两个人出牌，每次出一张，可以不出，不能同时不出，A不出的话横着走一格，B不出竖着走一格，都出走到紧接着右下的格子。任何一个人得牌出完了就结束了，图里看就是到达了右边一列或者下边一排的格子。

用GDPP建模

a) $\Omega_{i,j}$的entiries定义为从开始到A出了$i$张牌，B出了$j$张牌的所有路径。

b) 变换定义为$\Omega_{i-1,j}, \Omega_{i,j-1}, \Omega_{i-1,j-1}$里的entries，通过再次出牌变为$\Omega_{i,j}$的entries。

c) 变换的价值定义为：一个人不出的话-1( $\Omega_{i-1,j}, \Omega_{i,j-1}$里过来的 )，都出了但是不一样+0，出了一样+1( $\Omega_{i-1,j-1}里过来的$ )。

d) 最优函数定义为$\mathcal{F}(\Omega_{i,j})$所有路径价值的最大值，阶段是二维index，每个阶段只输出一个值。

e) 递归关系是： $$\mathcal{F}(\Omega_{i,j})=\max[ \mathcal{F}(\Omega_{i-1,j}) - 1, \mathcal{F}(\Omega_{i,j-1}) - 1, \mathcal{F}(\Omega_{i-1,j-1})+ \delta( M_{i,j} = X ) ]$$