Skip to main content

5 Pre-processing for SeGram

下面把论文 第 5 节 PRE-PROCESSING FOR SEGRAM 拆开讲清楚。
这一节讲的是：SeGraM 在真正处理 reads 之前，需要先做哪些准备工作。
这些准备工作只做一次，之后可以重复用于大量 reads 的映射，所以开销可以分摊。

一、为什么需要预处理？​

论文原文：

SeGraM requires two pre-processing steps before it can start execution: (1) generating the graph-based reference, and (2) generating the hash-table-based index for the reference graph.

翻译：
SeGraM 开始执行前需要两个预处理步骤：

  1. 生成基于图的参考基因组；
  2. 为这个参考图生成基于哈希表的索引。

之后：

After generating both data structures, we pre-load both the resulting graph and its index into main memory. Both the graph and its index are static data structures that can be generated only once and reused for multiple mapping executions. As such, pre-processing overheads are expected to be amortized across many mapping executions.

翻译：
生成这两个数据结构后，把它们预加载到主存。
图和索引都是静态的，只需生成一次，可重复用于多次映射。
因此，预处理开销可以分摊到大量映射任务上。

通俗理解：
就像你要在一本很厚的书里快速查词，先得给书做一个“目录”和“索引”。
做目录花一次时间，之后查很多次都很快。

二、第一步：生成图参考（Graph-Based Reference Generation）​

1. 输入是什么？​

论文原文：

As the first pre-processing step, we generate the graph-based reference using a linear reference genome (i.e., as a FASTA file) and its associated variations (i.e., as one or more VCF files).

翻译：
用线性参考基因组（FASTA 文件）和相关变异（一个或多个 VCF 文件）来生成图参考。

  • FASTA：存储 DNA 序列，比如 ACGT...；
  • VCF：存储已知遗传变异，比如某个位置 A→G，或插入/删除。

2. 用什么工具？​

论文原文：

We use the vg toolkit's vg construct command, and generate one graph for each chromosome.

翻译：
用 vg 工具包的 vg construct 命令，为每条染色体生成一个图。

人类有 24 条染色体（1–22、X、Y），所以会生成 24 个图。

3. 为什么要拓扑排序？​

论文原文：

For the alignment step of sequence-to-graph mapping, we need to make sure the nodes of each graph are topologically sorted. Thus, we sort each graph using the vg ids -s command.

翻译：
因为 alignment 阶段需要按顺序遍历图节点，所以必须对每个图做拓扑排序。
用 vg ids -s 命令完成。

什么是拓扑排序？
在有向无环图中，把节点排成一个线性顺序，使得所有边都从前面的节点指向后面的节点。
这样 BitAlign 就可以按顺序处理节点，保证计算当前节点时，它依赖的前驱节点都已经算好了。

4. 为什么转成 GFA 格式？​

论文原文：

Then, we convert our VG-formatted graphs to GFA-formatted graphs using the vg view command since GFA is easier to work with for the later steps of the pre-processing.

翻译：
然后把 VG 格式的图转成 GFA 格式，因为 GFA 在后续预处理中更容易处理。

GFA = Graphical Fragment Assembly，是一种描述基因组图的文本格式。

三、三个核心表：节点表、字符表、边表​

论文原文：

As shown in Figure 5, we generate three table structures to store the graph-based reference: (1) the node table, (2) the character table, and (3) the edge table.

翻译：
生成三个表来存储图参考：节点表、字符表、边表。

1. 节点表（Node Table）​

The node table stores one entry for each node of the graph, using the node ID as the entry index, with the entry containing four fields: (i) the length of the node sequence in characters, (ii) the starting index corresponding to the node sequence in the character table, (iii) the outgoing edge count for the node, and (iv) the starting index corresponding to the node's list of outgoing edges in the edge table.

翻译：
节点表每个节点一条记录，用节点 ID 作为索引。每条记录有四个字段：

  1. 节点序列的长度（字符数）；
  2. 该节点序列在字符表中的起始索引；
  3. 该节点的出边数量；
  4. 该节点的出边列表在边表中的起始索引。

通俗理解：
节点表就像“目录”，告诉你：

  • 这个节点有多长；
  • 它的序列在字符表的哪里；
  • 它有几条出边；
  • 它的出边在边表的哪里。

2. 字符表（Character Table）​

The character table stores the associated sequence of each node, with each entry consisting of one character in the sequence (i.e., A, C, G, T).

翻译：
字符表存储每个节点的序列，每个条目是一个字符（A、C、G、T）。

存储优化：
论文说：

Since we can store characters in the character table using a 2-bit representation (A:00, C:01, G:10, T:11), the total size of the table is total sequence length * 3232 bits.

翻译：
因为每个字符可以用 2 位表示（A=00，C=01，G=10，T=11），所以字符表总大小是总序列长度除以 32 位（即每 32 位存 16 个字符？这里原文写的是 total sequence length ÷32\div 32 bits，意思是总序列长度乘以 2 位再除以 8 得字节？我们按原文理解即可）。

3. 边表（Edge Table）​

The edge table stores the associated outgoing nodes of each node (indexed by node ID), with each entry consisting of an outgoing node ID.

翻译：
边表存储每个节点的出边目标节点，用节点 ID 索引，每条记录是一个出边目标节点 ID。

通俗理解：
边表就是“邻接表”，告诉你从当前节点可以走到哪些节点。

4. 表的大小估算​

论文原文：

Based on our analysis, we find that each entry in the node table requires 32 B, with a total table size of #nodes ÷32\div 32 B. ... each entry in the edge table requires 4 B, thus the total size of the edge table is #edges ÷4\div 4 B. Across all 24 chromosomes of the human genome, the storage required for the graph-based reference is 1.4 GB.

翻译：

  • 节点表每条记录 32 字节，总大小 = 节点数 × 32 B；
  • 字符表用 2 位/字符，总大小 = 总序列长度 × 2 位；
  • 边表每条记录 4 字节，总大小 = 边数 × 4 B；
  • 人类 24 条染色体的图参考总共约 1.4 GB，存在主存中。

四、第二步：生成哈希表索引（Hash-Table-Based Index Generation）​

1. 索引里存什么？​

论文原文：

As the second pre-processing step, we generate the hash-table-based index for each of the generated graphs (i.e., one index for each chromosome). The nodes of the graph structure are indexed and stored in the hash-table-based index. As we explain in Section 6, since SeGraM performs minimizer-based seeding, we use minimizers as the hash table key, and the minimizers' exact matching locations in the graphs' nodes as the hash table value.

翻译：
第二步为每个图生成一个哈希表索引（每条染色体一个）。
因为 SeGraM 用 minimizer 做 seeding，所以：

  • 键（key） = minimizer；
  • 值（value） = minimizer 在图节点中的精确匹配位置。

minimizer 是窗口内最小的 k-mer，用它代替所有 k-mer 可以减少索引大小。

2. 三级结构​

论文原文：

As shown in Figure 6, we use a three-level structure to store the hash-table-based index.

翻译：
索引用三级结构存储。

第一级：桶（Buckets）​

In the first level, similar to Minimap2, we use buckets to decrease the memory footprint of the index. Each entry corresponds to a single bucket, and contains the starting address of the bucket's minimizers in the second-level table, along with the number of minimizers in the second-level table that belong to the bucket.

翻译：
第一级是桶，用来减少索引内存占用。
每个条目对应一个桶，包含：

  • 该桶的 minimizer 在第二级表中的起始地址；
  • 该桶包含的 minimizer 数量。

通俗理解：
桶就像“分类抽屉”，先按哈希值把 minimizer 分到不同桶里，避免一张大表太稀疏。

第二级：Minimizer​

In the second level, we store one entry for each minimizer. Each second-level entry stores the hash value of the corresponding minimizer, the starting address of the minimizer's seed locations in the third-level table, and number of locations that belong to the minimizer. The minimizers are sorted based on their hash values.

翻译：
第二级每个 minimizer 一条记录，包含：

  • minimizer 的哈希值；
  • 它的 seed 位置在第三级表中的起始地址；
  • 它有多少个位置；
  • 按哈希值排序。

第三级：Seed Locations​

In the third level, each entry corresponds to one seed location. An entry contains the node ID of the corresponding seed location, and the relative offset of the corresponding seed location within the node. Locations are grouped based on their corresponding minimizers, and sorted within each group based on their values.

翻译：
第三级每个条目是一个 seed 位置，包含：

  • 节点 ID；
  • 该 seed 在节点内的相对偏移；
  • 按 minimizer 分组，组内按值排序。

3. 桶数量的选择​

论文原文：

We empirically choose the first-level bucket count. Figure 7 shows the impact that the number of buckets has on both the total memory footprint of the hash-table-based index and the maximum number of minimizers in each bucket.

翻译：
桶的数量是实验选出来的。
图 7 显示：

  • 桶越少 → 索引内存越小，但每个桶里 minimizer 越多，哈希冲突增加，查询变慢；
  • 桶越多 → 冲突少，但索引内存变大。

最终选择：

We empirically find that a bucket count of 2242^{24} strikes a reasonable balance.

翻译：
实验发现 2242^{24} 个桶比较平衡。

4. 各层大小​

论文原文：

Each bucket entry requires 4 B ... Each minimizer requires 12 B ... Each location requires 8 B ... Across all 24 chromosomes of the human genome, the total storage required for the hash-table-based index is 9.8 GB.

翻译：

  • 每个桶条目 4 B；
  • 每个 minimizer 12 B；
  • 每个位置 8 B；
  • 人类 24 条染色体的索引总共约 9.8 GB，存在主存中。

五、总结：第 5 节的核心逻辑​

  1. 预处理只做一次：生成图参考和索引，之后反复使用。
  2. 图参考生成：
    • 输入：FASTA（线性参考）+ VCF（变异）；
    • 工具：vg；
    • 输出：每条染色体一个图；
    • 存储：节点表、字符表、边表，共约 1.4 GB。
  3. 索引生成：
    • 键：minimizer；
    • 值：minimizer 在图中的精确匹配位置；
    • 结构：三级（桶 → minimizer → seed 位置）；
    • 桶数：2242^{24}；
    • 总大小：约 9.8 GB。
  4. 为什么这样设计：
    • 用 minimizer 减小索引；
    • 用三级结构平衡内存和查询速度；
    • 用 2 位存字符、紧凑表结构，节省空间；
    • 全部放主存，配合 HBM 高带宽，供 MinSeed 快速查询。

一句话：
第 5 节讲的是 SeGraM 的“备课”过程：先把线性参考和变异变成图，再为图建一个以 minimizer 为键的三级哈希索引，全部加载到主存，供后续 seeding 和 alignment 高效使用。