动态规划与序列比对基础

更新：2026-10-13；状态：可用；验证范围：线性缺口全局比对教学实现已运行；空串与回溯分数另有自动检查。

把大问题拆成可复用的小状态，理解全局比对与局部比对的边界条件。

动态规划的四个要素

定义状态、状态转移、初始化和答案位置。重复使用已求出的子问题，可以避免反复枚举相同路径；但前提是状态包含求解所需信息，而不是任何问题都能套二维表。

全局比对的状态

设D(i,j)为前i个字符与前j个字符的最佳全局比对分数。线性缺口罚分g下：

$$D(i,j)=\max{D(i-1,j-1)+s(a_i,b_j),\ D(i-1,j)+g,\ D(i,j-1)+g}.$$

初始化 $D(i,0)=ig$、$D(0,j)=jg$，答案位于D(n,m)。回溯记录获得分数的路径，从而得到比对字符串。仅有最佳分数还不等于有完整比对。

与局部比对的区别

Smith-Waterman局部比对允许从0重新开始并从表中最大值回溯；全局比对覆盖两条序列全长。仿射缺口需要区分开缺口和延伸缺口等状态，不能只把单一罚分改成两个数字而保持原递推。

标准表计算的时间O(nm)，完整表和回溯也可能需要O(nm)空间；只求分数时可滚动行节省空间，恢复路径需要额外方法。启发式搜索见BLAST原理与种子延伸。

已运行例子

匹配+2、错配−1、每个缺口字符−2，ACGT与AGT得到：

ACGT
A-GT
score = 4

实现见基础算法可复现练习。它没有仿射缺口、替换矩阵或大规模索引，不能替代生产比对器。方法来源：Needleman与Wunsch原始论文。