2.4 Graph Wavefront Algorithm (GWFA)
GWFA 全称 Graph Wavefront Algorithm，是 Minigraph 在 clustering/chaining 阶段用来连接两个锚点（anchor）的动态规划算法。它虽然用在 chaining 里，但计算模式和比对算法很像，论文把它归为动态规划类内核。
要理解 GWFA，最好先看线性 WFA 在做什么，再看图版本改了什么。
1. 背景：锚点和 chaining
在 Seq2Graph 比对流程中：
- Seeding 找到一些精确匹配的种子，称为 seed hits。
- 这些种子在参考图中的位置就是 锚点（anchor）。
- Chaining 要把这些锚点连起来，形成一条合理的路径，估计它们之间的顺序和距离。
问题是：两个锚点之间可能隔着一段序列，怎么知道它们能不能连、距离多远？
GWFA 的任务就是：
给定两个锚点，在参考图中找到一条连接它们的路径（节点序列），并计算编辑距离。
2. 线性 WFA：按对角线推进的编辑距离算法
Wavefront Algorithm（WFA）是一种计算编辑距离的算法。它不像 Smith-Waterman 那样填满整个动态规划矩阵，而是只计算编辑距离不超过某个阈值的区域。
线性 WFA 的核心概念是 wavefront：
- 在动态规划矩阵中，对角线是 为常数的线。
- 编辑距离 表示已经发生了多少次插入、删除或错配。
- 表示在编辑距离为 时，每条对角线上最远到达的单元格集合，也就是最靠下、最靠右的那些格子。
算法迭代过程：
- 从编辑距离 开始，沿着对角线尽量匹配，直到遇到不匹配。
- 遇到不匹配后，扩展出新的对角线，对应插入或删除操作，编辑距离加 。
- 每次迭代计算新的 wavefront 。
- 直到某条对角线到达终点，就找到了最小编辑距离。
因为只计算 wavefront，不填满整个矩阵，所以 WFA 比传统动态规划快很多。论文提到，线性 WFA 很容易自动向量化。
但线性 WFA 也有一个问题：不同对角线前进的距离不同。有的对角线能走很远，有的很快遇到不匹配。这导致控制流分歧，分支难以预测。
3. 图版本 GWFA：每个节点一个小矩阵
在泛基因组图中，参考不是一条线性序列，而是一个图。GWFA 的做法是：
- 每个节点有自己的动态规划矩阵：查询序列在一个轴上，节点序列在另一个轴上。
- 节点之间通过有向边连接。
- 当一条对角线走到当前节点的末尾时，它不能简单继续，因为接下来可能走到多个子节点。
- 于是，GWFA 把 wavefront 扩展到每个子节点，在子节点的矩阵里继续推进。
这就像：
- 线性 WFA 在一个大网格上沿对角线走。
- 图 WFA 在很多个小网格（每个节点一个）上走，走到边界时，通过边跳到下一个网格。
论文里用 Figure 4d 举例：蓝色对角线到达节点末尾后，会扩展到所有子节点，导致 wavefront 变得更大，单元格散布在不同节点中。
4. 为什么 GWFA 快，但又难预测
快的原因：
- 它只计算编辑距离小的区域，不填满整个 DP 矩阵。
- 论文指出，GWFA 计算的 DP 矩阵单元格远少于 GSSW 和 GBV，因此是“最快的比对算法”。
- 它使用非仿射 gap scoring，也就是每个插入/删除单独计费，不区分 gap 开放和延伸。这比仿射评分简单，计算量更小。
难预测的原因：
- 不同对角线前进距离不同，导致控制分歧。
- 到达节点末尾时，要跳到子节点，访问模式不规则。
- wavefront 中的单元格散布在不同节点，内存访问不连续。
- 论文的微架构分析显示，GWFA 主要受 Bad Speculation 限制，来源有两个：
- 沿对角线扩展直到错配，这段代码数据依赖强，分支行为差。
- 检查对角线是否到达节点末尾，图版本的边界检查比线性版本更不可预测。
另外，论文还发现 GWFA 的向量指令很少。这很意外，因为线性 WFA 很容易自动向量化。原因是图相关的修改让编译器 g++ 11 无法自动向量化。手动向量化可能带来性能提升。
5. 和 GSSW、GBV 的对比
| 特性 | GWFA | GSSW | GBV |
|---|---|---|---|
| 使用工具 | Minigraph | Vg Map | GraphAligner |
| 阶段 | Chaining | Alignment | Alignment |
| 评分方式 | 非仿射 gap | 仿射 gap | 简单编辑距离 |
| 精度 | 较低 | 高 | 较低 |
| 速度 | 最快 | 较慢 | 较快 |
| 主要瓶颈 | 分支预测错误 | 核心 + 内存 | 分支预测错误 |
| 向量化 | 少，难自动向量化 | 多，手工向量化 | 位向量，SIMD |
6. 一句话总结
GWFA 是 Wavefront Algorithm 的图版本，用于在 Minigraph 的 chaining 阶段连接两个锚点。它不填满整个动态规划矩阵，而是只计算编辑距离小的 wavefront，并沿对角线推进；遇到节点边界时，把 wavefront 扩展到所有子节点。它计算量小、速度快，但图结构导致控制分歧和不规则访问，分支预测错误成为主要瓶颈。