Skip to main content

1.1.1 Sequence-to-Graph Seed: Minimizer

一句话：重叠 k-mer 是“全部候选”，minimizer 是“从这些候选里按窗口选出的稀疏代表”。
minimizer 是重叠 k-mer 的子集，不是另一种完全不同的东西。

1. 重叠 k-mer 是什么？​

把 read 按步长 1 滑动，每次取长度为 kk 的连续子串，就得到所有重叠 k-mer。

例如 read = ACGTACGT，k=5k=5：

  • ACGTA
  • CGTAC
  • GTACG
  • TACGT
  • ACGTA（可能重复）
  • ...

相邻两个 k-mer 重叠 k−1k-1 个碱基。
一条长度为 LL 的 read，大约有 L−k+1L-k+1 个重叠 k-mer。
它们覆盖了 read 的每一个位置，灵敏度高，但数量大。

2. minimizer 是什么？​

minimizer 是一种降采样方法。
它仍然基于 k-mer，但不是把所有 k-mer 都拿去查索引，而是在一个大小为 ww 的滑动窗口里，选哈希值最小（或最大）的那个 k-mer 作为代表。

例如窗口里有 3 个 k-mer：

  • ACGTA
  • CGTAC
  • GTACG

对它们算哈希，假设 CGTAC 哈希最小，那么这个窗口的 minimizer 就是 CGTAC。
窗口继续滑动，可能选出一个新的 minimizer，也可能沿用旧的。

所以 minimizer 集合有几个特点：

  • 它是 k-mer 的子集；
  • 数量远少于所有重叠 k-mer，通常约 L/wL/w 到 2L/(w+1)2L/(w+1) 量级；
  • 相同或相似序列区域，往往能选到相同的 minimizer；
  • 它不保证每个碱基都被覆盖，但每个窗口至少有一个代表。

3. 核心区别​

维度重叠 k-merminimizer
定义所有长度为 kk 的连续子串，步长 1每个窗口内按哈希选出的代表 k-mer
数量约 L−k+1L-k+1，很多约 L/wL/w 到 2L/(w+1)2L/(w+1)，稀疏
集合关系全部候选是重叠 k-mer 的子集
覆盖性每个碱基被多个 k-mer 覆盖不保证每个碱基，但每个窗口有代表
目的高灵敏度，完整候选降采样，减少索引和查询次数
索引若全部索引，索引巨大通常只对 minimizer 建索引
在 seeding 中底层候选短串实际拿去查索引的键，命中后产生 seed

4. 为什么文档里说 “overlapping minimizers”？​

严格说，更准确的表述是：

  1. 先把 read 切成重叠的 k-mer；
  2. 再用滑动窗口从这些 k-mer 里选 minimizer；
  3. 只把 minimizer 拿去查索引，命中后产生 seed。

所以文档里的 “overlapping minimizers” 容易让人误解。
它想表达的是：minimizer 提取时窗口是重叠滑动的，因此 minimizer 在 read 上也有局部覆盖性。
但 minimizer 集合本身并不等于所有重叠 k-mer，而是它们的稀疏代表。

5. 一个直观类比​

  • 重叠 k-mer：把一本书每一页都复印下来，信息全，但太多。
  • minimizer：每几页里只挑一句最有代表性的话做索引，数量少，但相似的书仍能通过这些代表句匹配上。

6. 在 S2G seeding 中的关系​

Seeding 阶段的目标是快速找到 read 可能来自图上的哪些位置。
如果所有重叠 k-mer 都去查索引：

  • 种子数量爆炸；
  • 索引太大；
  • 后续 chaining 压力极大。

所以实际框架通常：

  • 提取重叠 k-mer；
  • 选 minimizer；
  • 用 minimizer 查索引；
  • 每个命中产生一个 seed。

这样既保留了“短串精确匹配”的能力，又把候选数量压到可处理范围。

总结：重叠 k-mer 是原料，minimizer 是精选样品。minimizer 来自重叠 k-mer，但比它稀疏得多；前者追求覆盖和灵敏度，后者追求效率和可控的种子数量。