Skip to main content

1.3 Graph Chaining

Graph Chaining 阶段的直接输入是：

Linear Chaining 阶段输出的局部链，以及 pangenome graph 的拓扑结构。

具体来说：

1. 主要输入：Linear Chaining 产生的局部链​

Linear Chaining 在同一个图顶点内部把种子连成局部链。
每条局部链通常包含：

  • 所属的图顶点 ID；
  • 链的起始和结束锚点；
  • 在 query 上的起止位置；
  • 在顶点内的起止偏移；
  • 链的得分；
  • 锚点偏移信息；
  • 方向等。

论文第 3.1 节提到，每条 linear chain 需要 Slc=48S_{lc}=48 字节来存储边界位置、分数和锚点偏移。
这些局部链就是 Graph Chaining 要跨顶点连接的基本单元。

2. 辅助输入：Pangenome graph 的拓扑信息​

Graph Chaining 需要知道图的结构，才能判断两条局部链能不能跨顶点连起来。
它需要：

  • 顶点序列；
  • 边和邻接关系；
  • 顶点之间的可达性；
  • 变异泡的位置和结构。

这些信息通常来自图索引或 Graph Topology Bank。
Graph Chaining 用它们来计算局部链端点之间的最短路径，验证能否通过变异泡。

3. 不直接输入原始种子​

原始种子已经在 Linear Chaining 阶段被组织成局部链。
Graph Chaining 不再直接处理成千上万的零散 seed anchors，而是处理压缩后的局部链。

4. 不输入 Filtering 后的结果​

Filtering 在 Graph Chaining 之后。
所以 Graph Chaining 的输入是未经过滤的局部链，其中可能包含来自重复区域的假阳性链。
Graph Chaining 先把它们跨顶点连接成候选图路径，然后才由 Filtering 根据频率和空间一致性剔除不可信部分。

5. 输出是什么？​

Graph Chaining 的输出是 graph chains，也就是跨顶点的候选路径。
这些图链把多个局部链连接起来，表示 read 可能经过的图路径。

总结​

Graph Chaining 的输入是：

  1. Linear Chaining 输出的局部链，每条链带边界、得分、锚点偏移、所属顶点等信息；
  2. Pangenome graph 的拓扑结构，包括顶点、边、序列和邻接关系，用于最短路径和可达性判断。

它不直接处理原始种子，也不处理过滤后的链。
流程是：
Seeding → Linear Chaining → Graph Chaining → Filtering → Alignment
Graph Chaining 负责把局部链跨顶点连接成候选图路径，为后续过滤和精细比对做准备。