Skip to main content

1.2.1 Linear Chaining input

“命中”在这里是一个短串级精确匹配的概念：
read 中提取出的某个 minimizer（或 k-mer）在 pangenome graph 的索引里，找到了一个完全相同的短串出现位置。
每找到这样一个位置，就叫一次“命中”，并产生一个 seed。

拆开来看：

1. 索引里存的是什么？​

建索引时，会把 pangenome graph 中所有顶点上的 DNA 序列切成固定长度的 k-mer，然后建立哈希表：

  • 键：k-mer 的序列，或其哈希值；
  • 值：这个 k-mer 在图中出现的位置列表。

每个位置通常记录：

  • 顶点 ID，表示它在哪个图顶点；
  • 顶点内偏移，表示它在该顶点序列中的起始位置；
  • 方向，表示正链还是反向互补链；
  • 可能还有该 k-mer 的长度。

所以索引本质是：
“某个短串 → 它在图中所有出现的地方”。

2. Seeding 时怎么查？​

从 read 中提取一个 minimizer，比如 ACGTAC。
拿它去查索引。
如果索引里存在这个键，就返回一个位置列表：

ACGTAC -> [
  (顶点 v1, 偏移 10, 正链),
  (顶点 v2, 偏移 3,  正链),
  (顶点 v5, 偏移 20, 负链)
]

列表里的每一项，就是一次“命中”。
每次命中都会生成一个 seed anchor，记录：

  • 这个短串在 read 上的位置；
  • 它在图上的顶点 ID；
  • 它在顶点内的偏移；
  • 方向；
  • 长度。

所以：一个命中 = 一个 seed = 一个候选锚点。

3. 为什么一个 minimizer 会命中很多不同顶点？​

因为同一个短串可能在 pangenome graph 的多个地方出现：

  • 重复序列：基因组里有很多拷贝，同一个 k-mer 出现在不同顶点；
  • 多单倍型：pangenome graph 包含很多人的序列，相似区域在不同顶点中可能共享相同短串；
  • 变异泡两侧：分支两侧可能有一段相同的保守序列；
  • 正反链：DNA 双链，索引通常同时包含正向和反向互补，所以一个短串可能命中正链和负链；
  • 同一顶点内多个拷贝：即使在同一顶点，也可能出现多次。

因此，一个 read 的某个 minimizer 可能命中多个顶点；
一个 read 有很多 minimizer，每个又可能命中多个位置，所以种子数量会非常大。

4. 命中不等于正确匹配​

注意，这里的“命中”只是短串完全一致，并不代表整条 read 来自那里。
很多命中是重复区域造成的假阳性。
所以后续需要：

  • Linear Chaining：把同一顶点内的命中按坐标一致性连成局部链；
  • Graph Chaining：跨顶点连接局部链；
  • Filtering：去掉重复区域产生的虚假种子。

5. 和“命中很多不同顶点”的关系​

原文说“种子可能命中 pangenome graph 的很多不同顶点”，意思就是：

read 中某个 minimizer 查索引后，返回的匹配位置分布在多个不同的图顶点上。

每个返回的位置就是一个命中，每个命中产生一个 seed。
后续 Linear Chaining 会先按顶点把这些 seed 分组，只在同一顶点内部连接，所以这些分散在不同顶点的命中会被分开处理。

一句话总结​

命中 = read 中一个短特征串在 pangenome graph 索引里找到了一个完全相同的出现位置。
这个位置由“顶点 + 顶点内偏移 + 方向”确定。
一个短串可能在多个顶点出现，所以会命中多个顶点，产生多个 seed；这些 seed 就是后续 chaining 的候选锚点。