动态规划与序列比对：从编辑距离到 BLAST 思想

动态规划是解决序列比对这一生物信息学核心问题的数学基石。本文从经典的"编辑距离"出发，逐步引出全局比对（Needleman-Wunsch）与局部比对（Smith-Waterman），并解释 BLAST 为何能秒级完成海量数据库搜索。

在生物信息学中，sequence alignment 是最基础也最核心的操作之一：判断两段 DNA 或蛋白质序列的相似程度，几乎是一切进化分析、基因注释和变异检测的前置步骤。而支撑它的数学工具，正是动态规划（Dynamic Programming, DP）。

从「编辑距离」说起

动态规划的经典入门题是编辑距离（Levenshtein distance）：把一个字符串变成另一个，最少需要多少次插入、删除、替换。它的状态定义非常直觉——dp[i][j] 表示把 A[0..i] 变成 B[0..j] 的最小代价。状态转移只依赖左上、上、左三个相邻格子，因此可以用一张二维表自底向上填满。

def edit_distance(a: str, b: str) -> int:
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(
                dp[i - 1][j] + 1,        # 删除
                dp[i][j - 1] + 1,        # 插入
                dp[i - 1][j - 1] + cost  # 替换/匹配
            )
    return dp[n][m]

这张填表过程本身就是一张比对矩阵的雏形。把「代价最小化」换成「相似度最大化」，并引入匹配得分与空位罚分，就得到了序列比对算法。

图1：编辑距离动态规划矩阵，每行每列只依赖相邻三个格子

全局比对与局部比对

Needleman-Wunsch 算法用同样的填表思想求两段序列的全局最优比对，目标是整条序列的总得分最高。而 Smith-Waterman 算法只关心局部最相似的子段——它允许得分从 0 重新开始，非常适合在长序列中找出一段保守结构域。两者都依赖「回溯」：从矩阵的右下角（或局部最大值）沿转移路径走回起点，路径上的斜线代表匹配/替换，横线竖线代表空位。

图2：全局比对的回溯结果，路径决定每个位置是匹配、替换还是空位

为什么 BLAST 这么快

严格的 DP 比对时间复杂度是 $O(nm)$ ，对全基因组尺度的数据库不可行。BLAST 的巧妙之处在于启发式：它先找出两段序列中短而精确匹配的「种子」（word seed），只在这些种子附近做局部 DP 扩展。绝大多数不相关的区域被直接跳过，因此能在秒级完成对海量数据库的搜索。理解 DP 是理解 BLAST 为何「快且准」的根基。

动态规划不只属于生物信息学——它同样支撑着字符串相似度、拼写纠错、版本差异比较（diff）等无数编程场景。掌握这张「填表」的思维方式，你会在很多看似无关的问题里认出同一个模式。

---