Skip to main content

3 Expectation density

Compared to using the full set of k-mers, using only the <w,k> minimizers decreases the storage requirements of the index (by a factor of 2/(w+1)2 / (w + 1)) and speeds up index queries.

这个因子 2/(w+1)2/(w+1) 来自 minimizer 在随机序列中的期望密度。简单说：
使用 minimizer 后，索引中需要存储的 k-mer 数量大约只有全部 k-mer 的 2/(w+1)2/(w+1)。

下面分三步解释为什么是这个因子。

一、全 k-mer 索引 vs. minimizer 索引​

  • 全 k-mer 索引：把序列中每一个长度为 k 的子串都存进索引。
    数量 ≈ 序列长度 LL（更准确是 L−k+1L-k+1）。

  • minimizer 索引：只在每个长度为 w 的窗口中，选出一个最小的 k-mer 存进索引。
    但相邻窗口会共享同一个 minimizer，所以实际存储的 minimizer 数量远小于窗口数量。

问题转化为：在随机序列中，平均多少个 k-mer 中会有一个成为 minimizer？

二、为什么 minimizer 的密度是 2/(w+1)2/(w+1)？​

1. 直观理解​

考虑一个长度为 w 的窗口，里面有 w 个 k-mer。
根据排序规则，每个 k-mer 成为这个窗口最小值的概率都是 1/w1/w。
但一个 k-mer 可能同时是多个窗口的最小值。

在随机序列中，一个 k-mer 成为 minimizer，当且仅当它比它左边最多 w-1 个 k-mer 都小，或者比它右边最多 w-1 个 k-mer 都小。
这等价于：它是其周围某个局部范围内的“局部最小值”。

经典结论（Roberts et al. 2004）证明：
在随机序列中，minimizer 的期望数量是

\[ \frac{2L}{w+1} \]

其中 LL 是 k-mer 的总数。

所以 minimizer 占总 k-mer 的比例是

\[ \frac{2L/(w+1)}{L} = \frac{2}{w+1} \]

2. 一个简单验证：w = 1​

如果窗口大小 w = 1，每个窗口只有一个 k-mer，所以每个 k-mer 都是 minimizer。
比例应为 1。
代入公式：2/(1+1)=12/(1+1) = 1，正确。

3. 另一个验证：w = 2​

窗口大小 w = 2，每个窗口有 2 个 k-mer，选较小的那个。
在随机序列中，一个 k-mer 不是 minimizer 当且仅当它比左右两个邻居都大（即它是局部最大值）。
局部最大值的概率约为 1/31/3，所以不是局部最大值的概率是 2/32/3。
因此 minimizer 的比例约为 2/32/3。
公式给出：2/(2+1)=2/32/(2+1) = 2/3，吻合。

所以，2/(w+1)2/(w+1) 就是 minimizer 在随机序列中的期望密度。

三、为什么这能减少存储并加速查询？​

1. 存储减少​

全 k-mer 索引需要存 LL 个 k-mer。
minimizer 索引只需要存约 2L/(w+1)2L/(w+1) 个。
所以存储量变为原来的

\[ \frac{2L/(w+1)}{L} = \frac{2}{w+1} \]

即减少了 (w+1)/2(w+1)/2 倍。

例如：

  • w = 5：存储变为 2/6=1/32/6 = 1/3；
  • w = 10：存储变为 2/11≈18%2/11 \approx 18\%；
  • w = 20：存储变为 2/21≈9.5%2/21 \approx 9.5\%。

索引越小，占用的内存越少，缓存命中率越高。

2. 查询加速​

查询时，只需要用 minimizer 去索引里找位置。
因为索引条目少了，查询时比较的次数、内存访问的次数都减少。
同时，索引更小，可以更好地放在缓存里，减少 DRAM 访问延迟。

论文里说：

Compared to using the full set of k-mers, using only the ∼w,k∼\sim w,k\sim minimizers decreases the storage requirements of the index (by a factor of 2/(w+1)2/(w+1)) and speeds up index queries.

翻译：
与使用全部 k-mer 相比，只用 minimizer 可以把索引存储需求降低到原来的 2/(w+1)2/(w+1)，并加速索引查询。

四、总结​

概念说明
全 k-mer 数量≈ LL
minimizer 数量≈ 2L/(w+1)2L/(w+1)
存储减少因子2/(w+1)2/(w+1)
为什么？因为每个 minimizer 平均被 (w+1)/2(w+1)/2 个窗口共享
效果索引更小、内存占用更低、查询更快

一句话：
在随机序列中，一个 minimizer 平均会被约 (w+1)/2(w+1)/2 个窗口共享，所以 minimizer 的总数只有全部 k-mer 的 2/(w+1)2/(w+1)。因此索引存储量降到原来的 2/(w+1)2/(w+1)，同时查询的键更少，速度更快。