好吧，其实这么炸裂的名字既不动态，也无关编程技巧，只是Richard Bellman为了吓唬人而取的，hoho…

算法思想

动态规划算法是运筹学的一个分支，最早用于解决最优化决策问题，其在序列比对中有比较广泛的应用，如著名的BLAST、CLUSTALW、MFOLD、PHYLIP等都利用了其核心思想，主要包括三个部分：

• 递归：将一个大问题转换为多个子问题。对于序列比对来说，长度为N的两条序列大约有22N/2πN−−−−√种不同的比对方式，这在实际中几乎不可操作，而利用动态规划，将一整条序列变为一个个的碱基进行比对，从计算规模上给予了解决之道。一般性的递归公式为：

  
  

• 动态规划矩阵：自下而上，记录每个子问题的得分及最佳路径；

• 回溯：从最后一个位置S(M,N)回溯至(0,0),从而得到整条解决路径，但最佳路径可能不止一条。

对于序列比对来讲，动态规划只是从数学上给出了N2规模的计算方法，然而实际应用中可能面对百万级数量的长度不等的序列，这种时间复杂度就变得不可接受，故BLAST等算法往往是动态规划的一种快速逼近。

打分规则

动态规划虽然给出了算法，但对于序列比对来说，面临着如何评价相似性的高低、如何评价indel与mismatch的不同影响、是否考虑遗传变异等等涉及到生物学意义的问题，这就对打分规则提出了要求。

著名的BLOSUM矩阵就是基于这样一个打分公式：s(a,b)=1λlogPabfafb，其中Pab为期望的概率，fa和fb为背景概率，λ仅作为缩放因子。我们也可以根据自身的需求，参照不同的生物学假设，设定不同的打分矩阵，对序列相似性作出个性化的评价。

原文链接https://wenlongshen.github.io/2016/12/04/Dynamic-Programming/