3.2 Frontier and Maker

第三节里的 Frontiers and Markers 是 TALCO 算法最核心的两个概念。它们决定了：

• 计算按什么顺序推进；
• 一个 tile 从哪里开始、到哪里结束；
• 怎么在 tile 边界上找到安全的回溯起点。

下面用尽量直观的方式讲清楚。

---

1. 为什么需要定义 Frontier？

在 DP 矩阵里，每个格子的分数和 traceback 指针，都依赖于它左边、上边、左上边的格子。
如果一格一格随便算，很难知道“哪些格子已经算完了、哪些还没算”。

Frontier（前沿） 就是用来描述“当前算到哪一层了”。

定义：

第 $i$ 个 frontier，记作 $f_i$，是一组格子。
这组格子的分数和 traceback 指针，只依赖于前一个 frontier $f_{i-1}$。
所以如果 $j < k$，那么 $f_j$ 一定比 $f_k$ 先算。

把所有 frontier 合起来，要能覆盖整个 traceback 矩阵。
相邻的 frontier 之间可以有重叠的格子。

你可以把 frontier 想象成一条条“进度线”：

• 从左上角开始，一条一条往右下角推进；
• 每一条线上的格子，只依赖上一条线；
• 算完上一条，才能算下一条。

---

2. 在 X-Drop 中，Frontier 怎么定义？

X-Drop 是按 wavefront（波前） 计算的。
Wavefront 通常指 DP 矩阵中的一条反对角线。

论文里说：

在 X-Drop 算法中，第 $j$ 个 frontier 可以定义为两条相邻 wavefront $W_j$ 和 $W_{j+1}$ 上的格子集合。

为什么是两条，而不是一条？

因为 traceback 指针的依赖关系：

• 一个格子的指针可能指向上、左、左上；
• 对于 wavefront $W_{j+2}$ 上的格子，它的 traceback 指针只能指向：
  • $W_{j+1}$（上或左的情况）；
  • 或者 $W_j$（对角线的情况）。

也就是说，$W_{j+2}$ 只依赖 $W_{j+1}$ 和 $W_j$。
所以把 $W_j$ 和 $W_{j+1}$ 打包成一个 frontier $f_j$，就能保证：

任何从更后面的 frontier $f_k$（$k > j$）出发的回溯路径，都一定会经过 $f_j$。

这个性质非常重要，它保证了 TALCO 可以在 frontier 边界上切 tile，而不会漏掉任何可能的路径。

---

3. 在 WFAA 中，Frontier 怎么定义？

WFAA 是 WFA-Adapt，它的矩阵是三角形的：

• 行对应 alignment score；
• 列对应对角线。

Frontier 的定义取决于打分方式。

3.1 Levenshtein 距离（每个错配/gap 罚 1）

如果每个错配、插入、删除都只罚 1，那么：

• 每一行对应一个分数 $s$；
• 任何分数为 $s+1$ 的比对，一定包含一个分数为 $s$ 的部分比对。

所以，一行就可以作为一个 frontier。

也就是说：

第 $j$ 个 frontier 就是三角矩阵中的第 $j$ 行。

3.2 Affine gap（gap open 和 gap extend 分开罚）

如果使用 affine gap，比如：

• gap open 罚 1；
• gap extend 再罚 1；

那么从分数 $s$ 的比对，可能来自分数 $s-1$ 或 $s-2$。
因为打开一个 gap 要额外罚一次，所以分数会跳。

这时，一行不够，需要两行才能保证依赖关系。

论文里说：

对于 WFAA 算法，第 $j$ 个 frontier 可以定义为两条相邻 wavefront $W_j$ 和 $W_{j+1}$ 上的格子集合。

这和 X-Drop 的定义形式一样，但背后的原因不同：
X-Drop 是因为 traceback 指针跨 wavefront 最多两层；
WFAA 是因为 affine gap 的分数依赖会跨两行。

---

4. Marker 是什么？

Marker 是一个特殊的 frontier，记作 $f_M$。

它的作用是：

把一个 tile 分成两个阶段：Phase 1 和 Phase 2。

在 TALCO 算法里：

• 每个 tile 从某个 frontier 开始；
• 先计算 M 个 frontier，这 M 个 frontier 属于 Phase 1；
• 第 M 个 frontier 就是 marker，记作 $f_M$；
• 到达 marker 后，进入 Phase 2。

Phase 1 的任务：

• 正常计算分数和 traceback 指针；
• 把这些指针存到 tile 的 traceback 矩阵 $TB_{Tile}$ 中。

Phase 2 的任务：

• 从 marker 开始，继续往后计算；
• 但不存 traceback 指针，而是计算 convergence pointer；
• convergence pointer 表示：当前 frontier 上的格子，沿 traceback 往回走，最终会落到 marker 上的哪个格子；
• 如果当前 frontier 上所有格子的 convergence pointer 都指向 marker 上的同一个格子 $C_x$，就说明所有可能的回溯路径都会经过 $C_x$；
• 于是 TALCO 就令 $C_{tb} = C_x$，从这个格子开始回溯当前 tile。

所以 marker 就是 tile 内部的“检查点”：

• Phase 1 把数据准备好；
• Phase 2 从 marker 往后看，等所有路径汇聚；
• 汇聚后，确定回溯起点，完成这个 tile 的 partial alignment。

---

5. 一个直观比喻

把整个 DP 矩阵想象成一条很长的高速公路。

• Frontier 就是路上每隔一段设置的“里程碑”；
• 每个里程碑只依赖前一个里程碑，所以可以按顺序一段一段算；
• Marker 是某个特殊的里程碑，比如一个服务区；
• 在服务区之前，你正常记录路线（Phase 1）；
• 过了服务区，你开始观察：从后面来的所有车，是不是都会经过服务区的同一个出口？
• 如果是，你就可以确定：无论后面的车从哪来，它们回溯时一定经过这个出口；
• 于是你从这个出口开始，反推服务区之前的那段路线，就能拼出完整路线。

---

6. 在 TALCO 算法中的位置

回顾 Algorithm 1：

• 外层循环：多个 tile；
• 内层循环：每个 tile 内按 frontier 推进；
• 当 j - i = M - 1 时，到达 marker；
• 在此之前是 Phase 1，存 traceback 指针；
• 到达 marker 后进入 Phase 2，计算 convergence pointer；
• 当所有 convergence pointer 指向同一个 marker 格子时，确定 $C_{tb}$，结束这个 tile；
• 然后回溯，得到当前 tile 的 partial alignment；
• 再开始下一个 tile。

所以：

• Frontier 是计算和依赖的基本单位；
• Marker 是 tile 内部 Phase 1 和 Phase 2 的分界点；
• 两者配合，使得 TALCO 可以在固定内存下切 tile，同时保证与完整 banded 比对等价。

---

7. 总结

概念	含义	作用
Frontier	一组只依赖前一个 frontier 的格子	决定计算顺序，保证依赖关系
X-Drop 的 frontier	两条相邻 wavefront	因为 traceback 指针最多跨两层
WFAA 的 frontier	Levenshtein：一行；affine gap：两条相邻 wavefront	因为分数依赖可能跨两行
Marker	特殊 frontier $f_M$	分隔 tile 的 Phase 1 和 Phase 2
Phase 1	从 tile 开始到 marker	正常计算并存储 traceback 指针
Phase 2	从 marker 往后	计算 convergence pointer，等待路径汇聚
汇聚点 $C_x$	marker 上所有回溯路径的共同格子	作为当前 tile 的回溯起点 $C_{tb}$

一句话：

Frontier 是计算进度的基本单位，Marker 是 tile 内部的分界点。TALCO 在 marker 之前正常存指针，在 marker 之后观察回溯路径是否汇聚到同一个格子；一旦汇聚，就从这个格子开始回溯，从而在固定内存下保证比对质量。