Skip to main content

2.2 Graph-Based Genome Sequence Analysis

下面把论文 2.2 Graph-Based Genome Sequence Analysis 这一节拆开讲清楚。
它的核心是：为什么要用“图”来表示参考基因组，以及“序列到图映射”和传统“序列到序列映射”到底差在哪里。

一、先回顾 2.1 的线性参考有什么问题？​

2.1 讲的是传统做法：
把所有 reads 映射到一条线性的参考基因组上，比如人类参考基因组 GRCh38。

但线性参考有一个根本缺陷：
它只代表一个个体或一小部分人的 DNA 序列，不能代表整个群体的遗传多样性。

论文里说：

A single (i.e., a linear) reference genome is not representative of different sets of individuals (e.g., subgroups) in a species and using a single reference genome for an entire species may bias the mapping process (i.e., reference bias) due to the genetic diversity that exists within a population.

翻译：
单一线性参考基因组不能代表一个物种内不同个体或亚群。
用一条参考基因组去映射所有人的 reads，会因为群体内存在的遗传多样性而产生参考偏差（reference bias）。

举个例子：

  • 参考基因组在某个位置是 A；
  • 但某个人的基因组在这个位置是 G；
  • 如果这个人的 read 携带 G，映射到线性参考时，就可能：
    • 完全比对不上；
    • 或者被错误地比对到别的位置；
    • 或者虽然比对上，但被当成测序错误，而不是真实变异。

这会导致变异检测不准确，比如漏掉疾病相关变异。

论文还提到：

For example, the African genome, with all known genetic variations within the populations of African descent, contains (10%) more DNA bases than the current linear human reference genome.

意思是：
非洲人群的基因组，如果包含所有已知遗传变异，比当前线性人类参考基因组多出约 10% 的 DNA 碱基。
这说明线性参考严重低估了人类遗传多样性。

二、基因组图（Genome Graph）是什么？​

为了解决参考偏差，研究者提出用图结构来表示参考基因组，叫 genome graph（基因组图）。

论文定义：

A genome graph enables a compact representation of the linear reference genome, combined with the known genetic variations in the entire population as a graph-based data structure.

翻译：
基因组图把线性参考基因组和整个群体中已知的遗传变异结合在一起，用一种图结构紧凑地表示出来。

图的基本组成：

  • 节点（node）：代表一个或多个碱基，比如 ACG、T、G 等；
  • 边（edge）：连接两个节点，表示它们在基因组序列中相邻；
  • 多条出边：表示遗传变异，比如 SNP、插入、删除、结构变异等。

论文 Figure 1 给了一个例子：

Sequence #1: ACGTACGT
Sequence #2: ACGGACGT
Sequence #3: ACGTTACGT
Sequence #4: ACGACGT

这四条序列相关但不同。
用图表示时，可以共享相同部分，只在变异处分支：

  • 一个节点 ACG；
  • 然后分支：
    • 一条路走 T，再走 ACGT（对应 Sequence #1）；
    • 一条路走 G，再走 ACGT（对应 Sequence #2）；
    • 一条路走 TT，再走 ACGT（对应 Sequence #3）；
    • 一条路直接走 ACGT（对应 Sequence #4，相当于删除了中间的 T）。

这样，图既保留了线性参考，又包含了已知变异。
比存储多条完整线性序列更紧凑，也更能代表群体多样性。

论文说：

Genome graphs are better suited for expressing the genomic regions that have SNPs, indels and SVs than a linear reference sequence.

翻译：
基因组图比线性参考序列更适合表达含有 SNP、indel、SV 的基因组区域。

其中：

  • SNP：单核苷酸多态性，单个碱基不同；
  • indel：插入或删除；
  • SV：结构变异，比如大片段倒位、易位、拷贝数变化等。

三、Sequence-to-Graph Mapping（序列到图映射）流程​

传统是 Sequence-to-Sequence (S2S) mapping：read → 线性参考。
现在是 Sequence-to-Graph (S2G) mapping：read → 基因组图。

论文说 S2G 也遵循 seed-and-extend 策略，和 S2S 类似，但更复杂。

流程分两大阶段：

1. 预处理阶段（Pre-processing）​

  • 第一步：构建基因组图
    用线性参考基因组 + 已知变异（VCF 文件）构建图。

  • 第二步：索引图节点
    对图中的节点建立索引，供后续 seeding 快速查找。

2. 在线阶段（Online，处理 reads）​

  • 第一步：Seeding
    把 read 切成 k-mer，在图的索引中找精确匹配位置，得到候选映射区域。

  • 第二步：过滤/链接/聚类（可选）
    减少候选位置数量，去掉明显不对的。

  • 第三步：Alignment
    在 read 和候选子图之间做近似字符串匹配，允许替换、插入、删除，找到最优比对。

论文 Figure 2 展示了这个流程。
它和 S2S 流程看起来很像，但关键区别在于：参考不再是线性序列，而是图。

四、Sequence-to-Graph Alignment 与 Sequence-to-Sequence Alignment 的核心区别​

这是 2.2 节最重要的部分，也是 S2G 比 S2S 难的根本原因。

论文 Figure 3 对比了两者：

1. S2S 对齐（图 3a）​

线性参考：A C G T A C G T
查询 read：A C G T

做动态规划（DP）时，每个单元格只依赖相邻的三个单元格：

  • 左、上、左上。

因为线性序列中，字符是按顺序排列的，没有“跳转”。

2. S2G 对齐（图 3b）​

图参考：

A → C → G → T → G → A → C → G → T
              ↑_________|

存在一条边（hop）从后面的 G 跳回前面的 A，表示变异或重复。

这时，计算某个单元格时，不仅要看相邻单元格，还要看所有有边连到当前节点的非相邻节点。

论文说：

In contrast to S2S alignment, S2G alignment must incorporate non-neighboring characters as well whenever there is an edge (i.e., hop) from the non-neighboring character to the current character.

翻译：
与 S2S 对齐不同，S2G 对齐只要存在从非相邻字符到当前字符的边（即 hop），就必须把这些非相邻字符也纳入计算。

这意味着：

  • S2S：每个单元格依赖 3 个邻居；
  • S2G：每个单元格可能依赖很多个非邻居，取决于图中有多少条入边。

这直接导致：

  • 数据依赖更复杂；
  • 内存访问不规则；
  • 计算量更大；
  • 无法直接套用 S2S 的优化和启发式方法。

论文还提到：

A DP-based algorithm operates on a table, where each column corresponds to a reference character, and each row corresponds to a query read character.

DP 表格：

  • 列 = 参考字符；
  • 行 = read 字符；
  • 每个单元格 = 局部比对代价。

在 S2S 中，列就是线性序列的顺序。
在 S2G 中，列对应图的节点，但节点之间可能有跳跃的边，所以表格不再是简单的二维网格，而是带有图结构的依赖关系。

五、为什么 S2G 比 S2S 更难？论文总结了四个问题​

在 3.2 节，论文明确列出 S2G 更复杂的四个原因。虽然不在 2.2 节，但和 2.2 直接相关，可以提前理解：

  1. Alignment 更贵
    因为要处理图中的 hop，S2S 已经很贵的 alignment 在 S2G 中更贵。

  2. 执行流不规则
    hop 可以来自图中任意顶点，导致数据依赖更多、内存访问更不规则。

  3. S2S 的启发式不适用
    比如 chaining（把多个 seed 连成链）假设参考是线性的；
    但在图中，两个 seed 之间可能有多条路径，不能简单链起来。

  4. 搜索空间更大
    图包含线性参考 + 所有已知变异，read 的候选映射区域比线性参考大得多。

六、为什么不能直接用现有的 S2S 加速器？​

论文说：

Existing S2S mapping accelerators can mimic the behavior of S2G mapping by taking all paths that exist in the genome graph into account and aligning the same read to each of these paths one at a time. However, this would be prohibitively inefficient in terms of both computation and memory requirements.

翻译：
现有 S2S 加速器可以把图中所有路径都展开成线性序列，然后逐条比对。
但这在计算和内存上都极其低效，因为要存储所有可能的图路径，内存会爆炸。

所以，必须专门为 S2G 设计新的算法和硬件。
这就是 SeGraM 的动机：
MinSeed 加速 seeding，BitAlign 加速 alignment，并且两者都支持图结构。

七、一张表总结 S2S 与 S2G 的区别​

维度S2S（序列到序列）S2G（序列到图）
参考结构线性序列图（节点 + 边）
变异表示不包含或只包含一个参考包含群体已知变异
参考偏差严重显著降低
对齐依赖每个单元格依赖 3 个邻居依赖邻居 + 所有入边 hop
执行规律性规则不规则
内存访问较规则大量随机访问
搜索空间较小大得多
现有加速器很多几乎没有
代表工具BWA、Bowtie、Minimap2GraphAligner、vg、HGA、PaSGAL

八、一句话总结 2.2 节​

2.2 节讲的是：线性参考存在参考偏差，因此用基因组图（节点+边）来表示参考基因组和群体变异；序列到图映射仍然采用 seed-and-extend 流程，但 alignment 阶段必须处理图中的 hop（非相邻边），导致数据依赖更复杂、内存访问更不规则、搜索空间更大，因此需要专门为图结构设计新的算法和硬件加速器。