Skip to main content

2.3 Graph Burrows-Wheeler Transform (GBWT)

GBWT 全称 Graph Burrows-Wheeler Transform，是 Vg Giraffe 在比对流程的过滤步骤中使用的一种索引结构。要理解它，最好先知道线性 BWT / FM-Index 是做什么的，再看图版本改了什么。

1. 背景：线性 BWT 和 FM-Index​

Burrows-Wheeler Transform（BWT）是一种字符串变换，常用于压缩和索引。它的经典用法是：

  • 把参考基因组看作一条很长的字符串，比如 ...ACGT...。
  • 对字符串的所有循环旋转排序，取最后一列，得到 BWT。
  • 再配合辅助表（如 C 表、Occ 表），就能构建 FM-Index。
  • FM-Index 支持高效的模式匹配：给定一个短序列，快速找到它在参考基因组中的所有出现位置。

线性 FM-Index 的特点是：参考是一条碱基序列，字母表很小，只有 A,T,C,GA,T,C,G 四个字符。因此参考中重复子串很多，查询时可能对应大量前缀，导致内存访问范围大，容易成为内存带宽瓶颈。论文里也提到，之前工作发现线性 BWT 的 FM-Index 是内存带宽密集型的。

2. 图版本要解决什么问题​

在泛基因组图中，参考不再是一条线性序列，而是一个图：

  • 图由节点和有向边组成。
  • 每个节点包含一段碱基序列，也可以简化成节点 ID。
  • 单倍型路径就是图中一条条路径，例如 1→3→51 \rightarrow 3 \rightarrow 5、2→3→42 \rightarrow 3 \rightarrow 4。

在 Vg Giraffe 的过滤步骤中，它要做种子延伸：

  • 已经有一个种子命中，落在某个节点内。
  • 在节点内做精确匹配，允许最多四个错配。
  • 当延伸走到节点末尾时，需要决定：接下来可以走到哪些子节点？
  • 不能随便走，因为很多路径在生物学上不存在。比如有单倍型 1→3→51 \rightarrow 3 \rightarrow 5 和 2→3→42 \rightarrow 3 \rightarrow 4，如果已经走了 1→31 \rightarrow 3，那么下一跳不能是 44，因为没有单倍型支持。

所以需要一个索引，能够回答：

给定已经走过的节点序列 S=(s1,s2,…,sn)S = (s_1, s_2, \ldots, s_n)，有哪些可能的下一跳节点，并且这些路径在已知单倍型中存在？

3. GBWT 的核心思想​

GBWT 就是为这个问题设计的。它把图中的单倍型路径当作多个字符串，构建一个多字符串 BWT。

具体来说：

  • 线性 BWT 作用于单条碱基字符串。
  • GBWT 作用于多个序列，每个序列是单倍型路径的节点 ID 序列，例如 1,3,5 和 2,3,4。
  • 这些序列比碱基序列更长，重复更少。
  • 然后在这些序列上构建 BWT 和 FM-Index，支持反向搜索。
  • 查询时使用 last-first mapping 来查找节点。

所以 GBWT 可以看作一个 haplotype-aware graph FM-Index：它知道哪些路径是真实存在的单倍型，因此可以过滤掉不现实的路径。

4. 工作流程：种子延伸和 find 函数​

在 Vg Giraffe 中，过滤步骤大致是这样：

  1. 种子命中后，在节点内做精确匹配，允许最多四个错配。
  2. 如果延伸到节点末尾，调用 GBWT Index 函数 find。
  3. find 的输入是一个节点序列 S=(s1,s2,…,sn)S = (s_1, s_2, \ldots, s_n)。
  4. 输出是所有可能的下一跳节点，但只保留有已知单倍型支持的路径。
  5. 然后继续延伸，直到不能延伸或达到限制。

论文中提取的代表性 kernel 就是这个 find 函数，因为 Vg Giraffe 实际会调用很多 GBWT Index 函数，而 find 具有代表性。

举个例子：

  • 已知单倍型：1→3→51 \rightarrow 3 \rightarrow 5 和 2→3→42 \rightarrow 3 \rightarrow 4。
  • 当前已经走了 1→31 \rightarrow 3。
  • 那么下一跳候选是 55，而不是 44，因为 1→3→41 \rightarrow 3 \rightarrow 4 没有单倍型支持。
  • GBWT 会快速回答：从 1→31 \rightarrow 3 出发，唯一合理的下一跳是 55。

5. 性能特征：为什么 GBWT 不是内存瓶颈​

论文的一个重要发现是：GBWT 不是内存受限的，这与线性 BWT FM-Index 相反。

原因在于：

  • 线性 FM-Index 处理的是碱基序列，字母表只有 A,T,C,GA,T,C,G，重复子串多。
  • 给定一个短子串，可能有很多可能的前缀，导致大量不连续的内存访问。
  • GBWT 处理的是单倍型路径的节点 ID 序列。节点 ID 空间大，序列更长，重复更少。
  • 因此，对于给定子串，通常只有少数几个可能的前缀，查找范围有限。
  • 索引查询更可能访问相邻节点和相邻表项，局部性好。

所以 GBWT 不会像线性 FM-Index 那样成为内存带宽瓶颈。但它的瓶颈变成了控制流：

  • 数据依赖的控制流导致分支难以预测。
  • 论文的微架构分析显示，GBWT 受 Bad Speculation 和前端停顿影响。
  • 它交替进行压缩数据上的标量操作和查找下一节点的内存访问，形成标量与内存操作的混合。

6. 与线性 BWT 的对比​

特性线性 BWT / FM-IndexGBWT
作用对象单条碱基序列多个单倍型路径（节点 ID 序列）
字母表A,T,C,GA,T,C,G，很小节点 ID，很大
重复性高，前缀多低，前缀少
内存访问范围大，易成内存瓶颈局部性好，不易成内存瓶颈
主要瓶颈内存带宽控制流、分支预测
用途线性参考比对图参考中的种子延伸和路径过滤

7. 一句话总结​

GBWT 是 为泛基因组图设计的多字符串 Burrows-Wheeler 变换索引。它把图中的单倍型路径当作多个节点 ID 序列，构建 BWT 和 FM-Index，支持用 find 函数查询下一跳节点，并且只保留有已知单倍型支持的路径。由于节点 ID 序列重复少，GBWT 的查询局部性好，不是内存瓶颈；但数据依赖的控制流让它容易发生分支预测错误和前端停顿。在 Vg Giraffe 中，它用于过滤步骤的种子延伸，是泛基因组比对中一个重要的图感知索引结构。