Skip to main content

1.1.2 Sequence-to-Graph Seed: Minimizer Option

选哈希值最小（或最大）的那个 k-mer 作为 minimizer，核心目的是：用随机哈希把“选择”变成一种确定性的、与序列内容无关的随机采样。
这样既能保证不同 read、不同样本在相同区域选出一致的 minimizer，又能让 minimizer 分布均匀、变化不频繁，从而降低索引和查询成本。

具体原因可以分成几层：

1. 避免序列组成偏倚​

如果不用哈希，而是用某种固定规则选代表，比如“字典序最小的 k-mer”，会出问题：

  • 某些碱基组成的 k-mer 会总是被选中；
  • 富含 A/T 或 G/C 的区域可能产生过多或过少的 minimizer；
  • 选择结果与序列内容强相关，导致分布不均匀。

哈希函数把每个 k-mer 映射成一个看起来随机的数值。
这样每个 k-mer 被选为窗口最小值的概率大致相等，与它具体是什么序列无关。
于是 minimizer 在基因组上的分布近似均匀，不会偏向某些碱基模式。

2. 保证不同样本间的一致性​

Minimizer 最重要的用途之一是：
不同 read 覆盖同一区域时，应该能选出相同的 minimizer，这样索引才能匹配上。

哈希是确定性的：
同一个 k-mer，无论出现在哪条 read 里，哈希值都一样。
所以在相同窗口内，只要窗口内容相同，选出的最小哈希 k-mer 也相同。

这样：

  • 建索引时，参考序列选出的 minimizer；
  • 查询时，read 选出的 minimizer；

只要它们覆盖同一段保守序列，就能共享相同的键，从而命中。

如果选择规则依赖上下文或随机种子，不同样本可能选出不同代表，索引就无法复用。

3. 窗口滑动时变化少，minimizer 稳定​

在一个大小为 ww 的滑动窗口里，选哈希值最小的 k-mer。
当窗口向右滑动一格：

  • 一个新 k-mer 进入；
  • 一个旧 k-mer 离开。

只有两种情况会改变当前 minimizer：

  1. 新进入的 k-mer 哈希值比当前最小值还小；
  2. 当前最小值恰好是离开窗口的那个 k-mer。

因此，minimizer 不会每滑动一格就变一次，而是成段稳定。
这样：

  • 索引中 minimizer 数量远少于全部 k-mer；
  • 查询时命中的 minimizer 也更集中；
  • 后续 chaining 的种子数量可控。

如果选“字典序最小”，在序列局部波动时可能频繁切换，导致 minimizer 集合不稳定。

4. 对变异有一定鲁棒性​

假设一个窗口内发生了单碱基变异：

  • 如果变异没有改变哈希值最小的那个 k-mer，minimizer 不变；
  • 如果改变了，也只是局部窗口的 minimizer 变化，相邻窗口仍可能保留原来的 minimizer。

这种随机采样性质使得相似序列之间能共享相当比例的 minimizer。
理论上的期望是：两个相似度较高的序列，共享 minimizer 的比例也较高，从而保证 seeding 的灵敏度。

5. 为什么选“最小”或“最大”都可以？​

选最小还是最大只是约定。
只要索引构建和查询使用同一个哈希函数、同一个窗口大小、同一个方向，结果就一致。

通常选最小哈希值，因为实现简单：
维护一个滑动窗口最小值，可以用双端队列在 O(1)O(1) 均摊时间完成。
选最大只是把比较方向反过来，本质一样。

6. 和“随机采样”的关系​

Minimizer 本质上是一种局部随机采样：

  • 每个窗口至少选一个代表；
  • 代表由哈希值决定，而不是由序列本身决定；
  • 采样概率均匀，且确定可复现。

这类似于：
把每个 k-mer 随机分配一个“优先级”，每个窗口选优先级最高的那个。
这样得到的样本既稀疏，又能在不同数据集之间对齐。

总结​

选哈希值最小/最大的 k-mer，是为了：

  1. 消除序列组成偏倚，让选择近似随机均匀；
  2. 保证确定性，相同序列在不同 read 中选出相同 minimizer；
  3. 保持稳定性，窗口滑动时 minimizer 变化不频繁；
  4. 控制数量，用少量代表覆盖整个 read；
  5. 支持跨样本匹配，让索引和查询能共享 minimizer。

所以它不是随便定的规则，而是 minimizer 方法能同时兼顾灵敏度、效率和可复用性的关键设计。