2.3.1 X-Drop

下面详细讲解 X-Drop，包括它的动机、核心思想、具体流程、一个直观例子，以及它在 TALCO 中的作用。

---

1. X-Drop 是什么？为什么需要它？

经典动态规划（Needleman-Wunsch、Smith-Waterman）要填满整个 $m \times n$ 的分数矩阵。
对于长序列，比如 100 Kbp 的读段，矩阵有 $10^{10}$ 个格子，内存和时间都爆炸。

Banding 技术的思路是：

不去算整个矩阵，只算“看起来有希望”的区域。
把明显不可能成为最优比对的格子提前丢掉。

X-Drop 就是最著名的 banding 技术之一。
它最早出现在 BLAST 中，后来被大量长读段比对工具采用，比如 minimap2、Libgaba 等。

它的核心参数是 X，所以叫 X-Drop。

---

2. 核心思想：落后太多就丢弃

X-Drop 在按对角线（或反对角线）计算 DP 矩阵时，维护一个当前已经见过的最高分数，记作 $H_{\max}$。

对每个新算出来的格子，如果它的分数满足：

$$\text{score} < H_{\max} - X$$

就认为这条路径“落后最佳路径太多”，直接剪枝：

• 不再保存它的 traceback 指针；
• 后续依赖它的格子也视为不可达，分数设为 $-\infty$。

这样，真正被保留的格子只会分布在当前最佳分数附近，宽度大约由 $X$ 控制。
形状像一条沿着主对角线前进的“带子”，所以叫 banding。

---

3. 具体流程（以全局比对为例）

假设我们用 NW 打分：

• 匹配：$+2$
• 错配：$-1$
• gap：$-1$

参数 $X = 3$。

3.1 按反对角线推进

DP 矩阵通常按反对角线计算，因为同一反对角线上的格子互不依赖。
设反对角线索引：

$$d = i + j$$

从 $d = 0$ 开始，依次计算 $d = 1, 2, 3, \dots$。

3.2 维护全局最高分

在计算过程中，记录目前所有格子中的最高分 $H_{\max}$。

3.3 对每个格子做判断

对于格子 $(i,j)$，用 NW 递推算出分数 $F(i,j)$：

$$F(i,j)=\max \begin{cases} F(i-1,j-1)+s(R_i,Q_j)\\ F(i-1,j)+g\\ F(i,j-1)+g \end{cases}$$

如果：

$$F(i,j) < H_{\max} - X$$

则：

• 将 $F(i,j)$ 标记为剪枝；
• 不存储它的 traceback 指针；
• 后续格子如果依赖它，就当作 $-\infty$。

如果：

$$F(i,j) \ge H_{\max} - X$$

则保留它，并更新 $H_{\max}$：

$$H_{\max} = \max(H_{\max}, F(i,j))$$

3.4 剪枝的传播

一旦某个格子被剪枝，它右边、下边、右下边的格子就少了一个候选来源。
如果所有来源都被剪枝，这个格子也会变成 $-\infty$，从而被剪枝。
最终，只有一条“带状区域”会被计算。

---

4. 一个直观例子

设：

• $R = A C G T$
• $Q = A C T$
• 打分：match $= +2$，mismatch $= -1$，gap $= -1$
• $X = 3$

我们按反对角线算。

4.1 初始化

第一行和第一列：

	空	A	C	T
空	0	-1	-2	-3
A	-1
C	-2
G	-3
T	-4

此时 $H_{\max} = 0$。

4.2 计算 (1,1)

$R_1=A$，$Q_1=A$，匹配。

$$F(1,1) = F(0,0) + 2 = 2$$

$H_{\max} = 2$。

保留。

4.3 计算 (1,2) 和 (2,1)

(1,2)：$R_1=A$，$Q_2=C$，错配。

候选：

• 对角线：$F(0,1) + (-1) = -1 -1 = -2$
• 上方：$F(0,2) + (-1) = -2 -1 = -3$
• 左方：$F(1,1) + (-1) = 2 -1 = 1$

所以 $F(1,2)=1$。

检查：$H_{\max} - X = 2 - 3 = -1$。
$1 \ge -1$，保留。

(2,1)：$R_2=C$，$Q_1=A$，错配。

候选：

• 对角线：$F(1,0) + (-1) = -1 -1 = -2$
• 上方：$F(1,1) + (-1) = 2 -1 = 1$
• 左方：$F(2,0) + (-1) = -2 -1 = -3$

所以 $F(2,1)=1$。

$1 \ge -1$，保留。

$H_{\max}$ 仍为 2。

4.4 计算 (1,3) 和 (2,2) 和 (3,1)

(1,3)：$R_1=A$，$Q_3=T$，错配。

候选：

• 对角线：$F(0,2) -1 = -3$
• 上方：$F(0,3) -1 = -4$
• 左方：$F(1,2) -1 = 0$

$F(1,3)=0$。

$H_{\max} - X = -1$，$0 \ge -1$，保留。

(2,2)：$R_2=C$，$Q_2=C$，匹配。

候选：

• 对角线：$F(1,1) + 2 = 4$
• 上方：$F(1,2) -1 = 0$
• 左方：$F(2,1) -1 = 0$

$F(2,2)=4$。

更新 $H_{\max}=4$。

(3,1)：$R_3=G$，$Q_1=A$，错配。

候选：

• 对角线：$F(2,0) -1 = -3$
• 上方：$F(2,1) -1 = 0$
• 左方：$F(3,0) -1 = -4$

$F(3,1)=0$。

此时 $H_{\max}=4$，$H_{\max}-X=1$。
$0 < 1$，所以 (3,1) 被剪枝！

这就是 X-Drop：因为 $F(3,1)=0$ 落后最高分 4 超过 3，所以丢弃。

4.5 继续计算

被剪枝的格子不再提供候选。
最终只有一条带状区域被保留。

如果 $X$ 设得越大，带越宽，越接近完整 DP，但内存和时间也越大。
如果 $X$ 设得越小，带越窄，速度越快，但可能错过最优比对。

---

5. X-Drop 的优点和缺点

优点：

• 大幅减少计算量和内存。
• 对相似序列效果很好，因为最佳路径附近的带很窄。
• 实现简单，容易集成到 NW/SW 等 DP 算法中。
• 被广泛验证，是长读段比对的标准技术。

缺点：

• 不保证最优：如果真正的最优路径在某个点落后超过 $X$，就会被剪掉，导致结果变差。
• 对 $X$ 敏感：$X$ 太小会丢结果，$X$ 太大会失去加速意义。
• 内存仍然随序列长度线性增长：虽然带窄了，但带要沿着整条序列延伸，长度还是 $O(n)$。
• 硬件加速困难：带宽随序列长度增长，片上内存放不下。

---

6. X-Drop 与 WFA-Adapt 的区别

• X-Drop：用于经典 DP（NW/SW），按反对角线计算，根据分数落后程度剪枝。
• WFA-Adapt：用于 WFA，按分数层推进，丢弃三角矩阵中“落后太多”的外侧对角线。
• 两者都是 banding 启发式，都不保证最优。
• 论文中 TALCO 分别应用于 X-Drop 和 WFA-Adapt，形成 TALCO-XDrop 和 TALCO-WFAA。

---

7. X-Drop 在 TALCO 中的作用

TALCO 的目标是：在 tiling 的同时，保证结果与不 tiling 的 X-Drop 完全一致。

怎么做？

1. TALCO 仍然使用 X-Drop 的剪枝规则，所以搜索空间被限制在带内。
2. 把长比对切成多个 tile，每个 tile 只保留固定大小的内存。
3. 在每个 tile 内，先正常计算 X-Drop 的分数和 traceback 指针。
4. 到达 tile 边界（marker）后，进入第二阶段：传播 convergence pointer，看所有回溯路径是否汇聚到 marker 上的同一个格子。
5. 如果汇聚，就从这个格子开始回溯，保证这个 tile 的比对与完整 X-Drop 一致。
6. 然后进入下一个 tile，用 marker 的分数正确初始化。

这样，TALCO-XDrop 既保持了 X-Drop 的 banding 约束，又实现了 tiling 的固定内存，还保证了与不 tiling 的 X-Drop 结果等价。

论文图 4 展示了 TALCO-XDrop 的矩阵和收敛过程。
图 15 显示，TALCO-XDrop 在 1%–30% 错误率下，几乎 100% 产生最优分数，而 GACT、GACT-X、Scrooge 等启发式 tiling 方法则会有明显下降。

---

8. 一句话总结

X-Drop 是一种动态 banding 技术：在 DP 矩阵中按反对角线计算，维护当前最高分 $H_{\max}$，凡是分数低于 $H_{\max}-X$ 的格子就剪枝，只保留最佳分数附近的一条带。它大幅减少内存和计算，但不保证最优。TALCO 利用 traceback 收敛，把 X-Drop 安全地切成 tile，在保持 banding 约束的同时实现任意长序列的加速。