好吧，其实这么炸裂的名字既不动态，也无关编程技巧，只是Richard Bellman为了吓唬人而取的，hoho…
算法思想
动态规划算法是运筹学的一个分支，最早用于解决最优化决策问题，其基本思想有点儿类似分治法，将一个大问题拆解为数个子问题，各个子问题顺序求解，最终得到整个大问题的解。这种算法很适合应用到序列比对中，著名的BLAST、CLUSTALW、MFOLD、PHYLIP等都利用了其核心思想，主要包括三个部分：
- 递归：即将一个大问题转换为多个子问题的过程。对于序列比对来说，长度为\(N\)的两条序列大约有\(2^{2N}/\sqrt{2\pi N}\)种不同的比对方式，这在实际中几乎不可操作，而利用动态规划，将一整条序列变为一个个的碱基进行比对，从计算规模上给予了解决之道。一般性的递归公式为：
- 动态规划矩阵：自下而上，记录每个子问题的得分及最佳路径；
- 回溯：从最后一个位置\(S(M,N)\)回溯至\((0,0)\)，从而得到整条解决路径，但最佳路径可能不止一条。
对于序列比对来讲，动态规划只是从数学上给出了\(N^2\)规模的计算方法，然而实际应用中可能面对百万级数量的长度不等的序列，这种时间复杂度就变得不可接受，故BLAST等算法往往是动态规划的一种快速逼近。
打分规则
动态规划虽然给出了算法，但对于序列比对来说，面临着如何评价相似性的高低、如何评价indel与mismatch的不同影响、是否考虑遗传变异等等涉及到生物学意义的问题，这就对打分规则提出了要求。
著名的BLOSUM矩阵就是基于这样一个打分公式：\(s(a,b)=\frac1\lambda log\frac{P_{ab}}{f_af_b}\)，其中\(P_{ab}\)为期望的概率，\(f_a\)和\(f_b\)为背景概率，\(\lambda\)仅作为缩放因子。我们也可以根据自身的需求，参照不同的生物学假设，设定不同的打分矩阵，对序列相似性作出个性化的评价。
