Hirschberg 算法

快速概览

Hirschberg 算法是 Needleman-Wunsch 的线性空间优化版本：它使用分治策略将空间复杂度从 O(mn) 降低到 O(min(m,n))，同时仍能得到最优全局比对。

核心思想是将问题分解为子问题，递归求解
它是动态规划空间优化的经典案例

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

Hirschberg 算法是 1975 年提出的用于全局序列比对的动态规划算法。它解决了 Needleman-Wunsch 算法的空间瓶颈问题：

在保持 O(mn) 时间复杂度的同时，将空间复杂度从 O(mn) 降低到 O(min(m,n))。

这个算法是分治法（divide and conquer）在序列比对中的经典应用。

要解决什么生物信息学问题

Needleman-Wunsch 算法的主要限制是空间复杂度：对于长序列（如基因组级别的比对），存储完整的 O(mn) 矩阵往往不可行。

Hirschberg 算法解决了这个问题，使得：

可以对较长的序列进行精确的全局比对
在内存受限的环境中仍然能够运行
为其他需要空间优化的动态规划问题提供思路

数学模型

Needleman-Wunsch 的空间问题

在 Needleman-Wunsch 中，计算 F[i][j] 只需要：

F[i-1][j-1]：左上角
F[i-1][j]：上方
F[i][j-1]：左方

这意味着理论上只需要存储两行或两列就能计算得分。但是，要回溯得到比对路径，需要保存整个矩阵。

Hirschberg 的核心思想

Hirschberg 使用分治策略：

将序列 X 从中间分成两部分
找到序列 Y 的最优分割点
递归地解决两个子问题
合并结果

关键观察：如果我们知道最优比对在序列 Y 中的分割点，就可以独立地解决两个子问题。

算法步骤

步骤 1：前向和后向得分计算

定义两个辅助函数：

前向得分 ScoreL(i, j)：序列 X 的前 i 个字符与序列 Y 的前 j 个字符的最优比对得分。

后向得分 ScoreR(i, j)：序列 X 的后 i 个字符与序列 Y 的后 j 个字符的最优比对得分。

这两个得分都可以用 O(min(m,n)) 空间计算。

步骤 2：找到最优分割点

假设序列 X 的长度为 m，我们将 X 从中间分割：k = m/2。

我们需要找到 j，使得：

\max_{j} \{ \text{ScoreL}(k, j) + \text{ScoreR}(m-k, n-j) \}

这个 j 就是序列 Y 的最优分割点。

步骤 3：递归求解

将问题分解为两个子问题：

比对 X[1:k] 与 Y[1:j]
比对 X[k+1:m] 与 Y[j+1:n]

递归地解决这两个子问题，直到子问题足够小（可以直接用 Needleman-Wunsch 求解）。

步骤 4：合并结果

将两个子问题的比对结果拼接起来，得到最终的全局比对。

示例

考虑两条序列：

X = AGTACG（长度 m = 6）
Y = ACATAG（长度 n = 6）

使用以下打分体系：

匹配得分：+1
错配得分：-1
Gap 罚分：-2

步骤 1：计算前向得分

计算 ScoreL(i, j) 对于所有 j，其中 i = k = 3（X 的前半部分 “AGT”）：

使用 Needleman-Wunsch 的递推公式，但只保留当前行：

	ε	A	C	A	T	A	G
ε	0	-2	-4	-6	-8	-10	-12
A	-2	1	-1	0	-2	-4	-6
G	-4	-1	0	-1	-2	-4	-3
T	-6	-3	-2	-2	0	-2	-4

前向得分（第 3 行）：[-6, -3, -2, -2, 0, -2, -4]

步骤 2：计算后向得分

计算 ScoreR(i, j) 对于所有 j，其中 i = m - k = 3（X 的后半部分 “ACG”）：

这里需要从右向左计算，相当于将序列反转后做前向计算：

反转后的序列：X' = GCA，Y' = GATACA

计算前向得分：

	ε	G	A	T	A	C	A
ε	0	-2	-4	-6	-8	-10	-12
G	-2	1	-1	-3	-5	-7	-9
C	-4	-1	0	-2	-4	-3	-5
A	-6	-3	0	-1	-1	-3	-2

后向得分（第 3 行，反转）：[-2, -3, -1, -1, -2, 0, -6]

步骤 3：找到最优分割点

计算 ScoreL(3, j) + ScoreR(3, 6-j)：

j	ScoreL(3, j)	ScoreR(3, 6-j)	总和
0	-6	-2	-8
1	-3	-3	-6
2	-2	-1	-3
3	-2	-1	-3
4	0	-2	-2
5	-2	0	-2
6	-4	-6	-10

最大值为 -2，出现在 j = 4 或 j = 5。我们选择 j = 4。

步骤 4：递归求解

子问题 1：比对 X[1:3] = "AGT" 与 Y[1:4] = "ACAT"

子问题 2：比对 X[4:6] = "ACG" 与 Y[5:6] = "AG"

递归地解决这两个子问题（此处省略详细计算），最终得到：

子问题 1 的比对：

AG-T
|  |
ACAT

子问题 2 的比对：

ACG
| |
A-G

步骤 5：合并结果

AG-TACG
|  | | |
ACATA-G

得分验证：1 + (-2) + 1 + 1 + 1 + (-2) = 0

复杂度分析

时间复杂度

每一层递归需要计算前向和后向得分：O(mn)
递归深度为 O(log m)
总时间复杂度：O(mn log m)

但实际上，通过仔细分析，总时间复杂度仍然是 O(mn)，因为每一层处理的子问题规模总和不超过原问题。

空间复杂度

前向和后向得分：O(min(m, n))
递归栈：O(log m)
总空间复杂度：O(min(m, n))

与 Needleman-Wunsch 的对比

维度	Needleman-Wunsch	Hirschberg
时间复杂度	O(mn)	O(mn)
空间复杂度	O(mn)	O(min(m,n))
实现复杂度	简单	较复杂（递归）
适用场景	短序列或内存充足	长序列或内存受限

算法优缺点

优点

空间效率极高，适合长序列比对
仍能得到最优比对，不是近似算法
为其他动态规划空间优化提供思路

缺点

实现复杂，需要递归和额外的得分计算
常数因子较大，实际运行可能比 Needleman-Wunsch 慢
对于短序列，优势不明显

与真实工具或流程的连接

Hirschberg 算法本身较少直接用于现代生物信息学工具，主要因为：

现代工具通常使用 seed-and-extend 等启发式方法
对于大规模数据，近似算法通常足够
硬件发展使得内存限制不再是主要瓶颈

但 Hirschberg 算法在以下方面仍有价值：

作为教学示例展示分治法和空间优化
在需要精确比对但内存受限的场景
为其他算法优化提供理论基础

参考资料

Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6), 341-343.
Durbin, R., Eddy, S., Krogh, A., & Mitchison, G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge university press.