一、双序列比对

动态规划（Dynamic programming）

动态规划 (Dynamic programming, DP) 是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

• 重叠子问题：自底向上
  下面三个函数分别使用了递归、递归+列表、迭代方法求解斐波那契数列。后两种方法仅对重叠子问题求解一次，因而时间复杂度急剧下降。其中迭代呈现的自底向上策略就是动态规划对重叠子问题的处理思路。

• 最优子结构
  简单理解就是问题的最优解是子问题最优解的组合。以比对为例，碱基之间的比对只有三种情况：相同、替换和空位。在使用替换矩阵和空位罚分对三种情况打分后，得分最高者即是该位置的最优比对（公式1,2）。在对所有可能比对情形打分后，即可获得最优比对。由此即可构建下述的双序列比对算法：N-W和S-W。更为详细的推演过程可参考coursera课程：《生物信息学: 导论与方法》。

全局比对（Needleman-Wunch）

全局是指对两条序列所有残基进行比对。分别求三种比对状态的得分，最大值即为该位置最优比对。通过回溯，得到最佳比对结果。
F ( i , j ) = { F ( i 1 , j 1 ) + s ( x i , y j ) , x i : y j F ( i 1 , j ) + d , x i : F ( i , j 1 ) + d , y j : F(i,j)=