FM-index 开关

关掉的是哪一行

只换一个循环：从片段末尾往前，每步两次 rank 查询把区间往里收 ⟶ 从参考的第 0 位开始，一个位置一个位置比过去。参考、片段、错误率全不动。

⇒ n = 120 000、m = 100：后向搜索走 200 步，逐位置比对走 159 962 步——差 800 倍。而真实的参考是这个的两万五千倍长。

啊哈瞬间：200 这个数不会变

后向搜索的步数是 2m——只和片段有多长有关。参考从 2 万拉到 12 万，右上那张图里它是一条平线，另一条是斜的。⇒ 参考再长一万倍，还是 200 步。

★ 而那张瀑布图还露出一件我没写在预期里的事：平均第 9.3 个字符就把候选收到 1 个位置——正好是 log₄(n) = 8.4。 一百个字符里，后面九十来个全是在确认。⇒ 这就是为什么「种子 ＋ 延伸」那条路走得通：你只需要一小段精确的种子。

而这一切来自一个 1994 年为压缩而生的变换：BWT 把相同上下文的字符聚到一起，本是为了让 bzip2 好压；六年后有人发现那个变换过的东西本身可以直接被搜索，不用解开。测序成本这些年掉了六个数量级，通常全算在化学头上——有一半在这里。

⚠ 我预期错了两处

① 我写下「BWT 索引比原文还小」——在随机序列上它几乎压不动：游程数 r / n = 0.748。把重复元件覆盖拉到 4×，才掉到 0.190。⇒ 压缩来自重复，不来自变换本身；真实基因组一半以上是重复序列，FM-index 的便宜是基因组恰好长这样换来的。

② ⚠ 更该记的一处：我第一版把哨兵字符排在了最大而不是最小，LF 映射整个错位，后向搜索每次走到第 9 步就空了。而我量出来的「18 步」「7119 倍」看起来完全正常——因为我只量了步数，没验答案。加一条「两条路必须给出同一个命中数」，当场就抓到了：现在是 50 / 50。

它什么时候不赢

① 它只认精确匹配。错一个碱基，区间当场空掉：错 0 个时定位成功率 100.0%，错 1 个就是 0.0%。Illumina 那种 0.1% 错误率还能靠回溯硬撑；换成纳米孔那种 5~10% 错误率的长读长，这个策略直接归零——所以现代长读长比对器回到了 minimizer 加动态规划的种子延伸路线。

② 建索引本身要排一遍后缀数组，是 O(n) 内存 ＋ 一次性的重活；只找一两条片段的话，直接扫反而更快。它买的是「查得多」，不是「查一次」。