Skip to main content

1.1 Sequence-to-Graph Seed Stage

Seed 阶段把 read 切成许多重叠的短特征串，核心原因是：短串用于快速精确匹配，重叠用于保证不漏检、抗错误、抗变异，并为后续 chaining 提供连续坐标信息。

可以分两层理解。

1. 为什么要切成“短”特征串？​

因为 seeding 的本质是：拿 read 的一小段去哈希索引里查“它可能出现在图上的哪些位置”。

如果直接用整条 read 去查，会有两个问题：

  • read 通常有测序错误，整条 read 几乎不可能完全精确匹配；
  • 哈希索引通常只对固定长度的短串建表，查全长不现实。

所以要把 read 切成短串，典型长度是 1515–2525 bp。
短串更可能在某处完全精确匹配，而且查表速度快、索引小。

2. 为什么要“重叠”？​

如果只是把 read 切成互不重叠的块，比如每 1515 bp 切一刀，会很容易漏掉真实匹配位置。

原因有三类：

① 防止边界漏检​

假设 read 上真正匹配图的位置，刚好横跨两个非重叠块的边界。
如果两块分开查，可能两块都不完全匹配，但合起来其实是匹配的。
重叠切分后，总有一个短串能完整覆盖这个区域。

② 抗测序错误​

一个碱基错误，会破坏包含它的所有短串。
如果短串不重叠，一个错误可能直接毁掉一整个块。
如果短串重叠，每个碱基被多个短串覆盖，一个错误只影响其中一部分短串，其他不包含该错误的短串仍然能命中。

例如 k=3k=3，read 是 ACGTT...：

  • 非重叠：ACG、TT...
  • 重叠：ACG、CGT、GTT、TTA...

如果第二个碱基出错，ACG 失效，但后面的 GTT、TTA 可能仍然匹配。

③ 抗变异、支持图映射​

Pangenome graph 里有变异泡、插入、删除。
某个短串可能正好落在变异区域而无法匹配，但相邻的重叠短串可能落在保守区域，仍能提供种子。
这样后续 chaining 才能把候选位置连起来。

3. 重叠还方便后续 chaining​

重叠短串在 read 上的位置是连续的。
当它们命中图上的不同位置时，可以比较：

  • read 上的坐标差；
  • graph 上的坐标差；
  • 是否在同一条对角线附近。

这些信息正是线性链和图层链判断“哪些 seed 可以连成一条合理路径”的基础。

4. 但重叠太多会 seed 爆炸，所以用 minimizer​

如果每个位置都取一个 kk-mer，read 会产生大量种子，查索引和后续 chaining 都会很慢。
所以实际框架通常用 minimizer：在滑动窗口里只选哈希值最小的那个 kk-mer。

也就是说：

  • 底层候选是重叠的 kk-mer；
  • minimizer 是在这些重叠 kk-mer 中做降采样；
  • 窗口滑动仍然覆盖整个 read，所以保留了重叠带来的灵敏度和抗错性；
  • 同时控制了种子数量。

一句话总结​

短是为了能快速、精确地查哈希索引；
重叠是为了让每个碱基被多个短串覆盖，从而在测序错误、变异和边界情况下仍然有种子命中，并且为后续 chaining 提供连续的坐标关系。
如果只切非重叠短串，速度快但容易漏；如果全用重叠 kk-mer，灵敏度高但种子太多。minimizer 就是这两者之间的折中。