Skip to main content

2.5 Transclosure (TC)

Transclosure（TC）是 PGGB 流程中 seqwish 工具的一个核心内核，负责从 all-to-all 比对结果中诱导出泛基因组图的节点集合。它的名字来自“传递闭包”（Transitive Closure）：把通过匹配关系间接相连的字符全部合并成一个等价类，每个等价类对应图中的一个节点。

1. 背景：PGGB 和 seqwish 在做什么​

PGGB（PanGenome Graph Builder）的目标是构建一个无参考偏差的泛基因组图。它的流程大致是：

  1. All-to-all 比对：用 wfmash 对输入的所有基因组序列两两比对，得到大量 pairwise 匹配。
  2. Graph induction：用 seqwish 把匹配关系转换成图。这一步的核心就是 TC。
  3. Polishing：去除冗余结构。
  4. Visualization：可视化评估。

seqwish 的运行时主要由 TC 主导，论文说 TC 占其计算时间超过 75%75\%。

2. TC 要解决什么问题​

All-to-all 比对只给出两两之间的匹配。例如：

  • 序列 S0 的某个字符和 S1 的某个字符匹配。
  • S1 的另一个字符和 S2 的某个字符匹配。
  • 但 S0 和 S2 之间可能没有直接比对到，然而通过 S1，它们实际上是同一段序列。

如果不处理这种传递关系，同一个生物学位置会在图中被表示成多个节点，导致图冗余、不连通、后续分析困难。

TC 的任务就是：

把所有通过匹配关系直接或间接相连的字符合并成一个传递闭包，每个闭包映射为泛基因组图中的一个节点。

3. 一个直观的小例子​

假设有三个序列：

  • S0：A B C
  • S1：A B D
  • S2：A C D

All-to-all 比对给出匹配：

  • S0 的 B 与 S1 的 B 匹配。
  • S1 的 D 与 S2 的 D 匹配。
  • S0 的 C 与 S2 的 C 匹配。

现在看 B 和 D：S0 的 B 与 S1 的 B 匹配；S1 的 D 与 S2 的 D 匹配。但 B 和 D 之间没有直接匹配。不过，如果还有一条匹配：S1 的 B 与 S2 的 B 匹配（假设 S2 也有 B），那么 S0 的 B、S1 的 B、S2 的 B 就构成一个传递闭包，合并成一个图节点。

更简单的传递闭包例子：

  • 匹配 M0：S0 的字符 x 与 S1 的字符 y 匹配。
  • 匹配 M1：S1 的字符 y 与 S2 的字符 z 匹配。
  • 那么 {x,y,z}\{x, y, z\} 属于同一个传递闭包 TC0，映射为一个图节点。

这样，不同序列中对应的字符就统一成了图中的一个节点，后续再根据序列顺序添加边和路径。

4. TC 的算法步骤​

TC 大致做以下事情：

  1. 收集所有匹配：从 all-to-all 比对中提取匹配字符对。
  2. 排序：把匹配按序列和位置排序，便于后续二分查找。
  3. 并查集（Union-Find）：用并查集合并直接和间接匹配的字符。每个集合就是一个传递闭包。
  4. 二分查找：因为匹配已排序，可以用二分查找快速找到与某个字符相连的其他匹配，从而高效扩展闭包。
  5. 映射到图节点：每个传递闭包生成一个图节点。
  6. 插入路径：根据输入序列的顺序，把节点串成路径。

为了处理真实泛基因组图，这些数据结构可能占用 数百 GB 内存。seqwish 使用内存映射文件（memory-mapped files）来让内存受限的系统也能运行 TC。

5. 为什么 TC 是“新任务”​

论文强调，TC 与基因组学中常见的比对算法不同：

  • 它不使用动态规划比对。
  • 它依赖巧妙的数据结构：隐式区间树（implicit interval trees）用于高效并查集操作，原子位向量（atomic bitvectors）等。
  • 它需要高性能排序来保证数据访问效率。
  • 它是异构算法组合：排序 + 并查集 + 二分查找 + 文件映射。

因此，TC 引入了一种新的计算模式，不同于线性基因组学中的比对或组装。

6. 性能特征​

论文的微架构分析显示：

  • TC 的 IPC（Instructions Per Cycle） 为 3.14，是所有内核中最高的。
  • 它不是内存瓶颈，访问模式相对规则。
  • 它大量使用优化数据结构，并能利用一定空间局部性，比如位向量访问。
  • 主要挑战是内存占用大，需要内存映射文件。
  • 计算时间由高效排序、并查集操作、简单数据追加和高度优化排序主导。

所以 TC 是一个高吞吐、规则访问、但内存需求巨大的内核。

IPC 越高，说明 CPU 在每个周期里干活越多，性能越好。它衡量 CPU 在一个时钟周期内平均能执行多少条指令，是反映处理器实际效率的核心指标之一。

7. 与线性基因组学的对比​

线性基因组学通常只有一个参考序列，不需要把多个序列的匹配字符合并成传递闭包。多序列比对可能涉及类似操作，但规模小得多。泛基因组图构建中，TC 要处理成千上万个基因组、数百 GB 的匹配数据，是图构建的核心瓶颈之一。

8. 一句话总结​

TC（Transclosure）是 seqwish 中通过传递闭包把多个 pairwise 比对中的匹配字符合并成泛基因组图节点的过程。它用排序、并查集和二分查找高效处理海量匹配，每个闭包对应一个图节点。TC 不使用比对，而是依赖巧妙的数据结构和内存映射，是 PGGB 构建泛基因组图的关键计算内核，具有高 IPC、规则访问和巨大内存需求的特点。