1.1 Genome Reference Indexing
下面用一个极简例子，把 2.1 节里说的 Indexing（索引构建） 拆开讲清楚。
论文里只有一句话：
Indexing pre-processes the reference genome and generates an index of the reference to be later used in the next steps of read mapping.
意思是：Indexing 是预处理步骤，对参考基因组建立索引，供后面的 seeding 快速查找。
我们用一个很小的参考序列，手动走一遍 indexing 全过程。
一、假设的参考基因组和参数
假设参考基因组（reference）只有 8 个碱基：
参考序列：A C G T A C G T
位置编号：0 1 2 3 4 5 6 7
我们选择 k = 3，也就是用长度为 3 的 k-mer 来建索引。
二、Indexing 的核心步骤
步骤 1：确定 k 值
k 是 k-mer 的长度。
k 越大，索引越具体，但可能漏掉有错配的匹配；
k 越小，索引越灵敏，但会产生更多候选位置。
这里取 k = 3。
步骤 2：滑动窗口提取所有 k-mer
从参考序列的位置 0 开始，每次向右滑动 1 个碱基，取出长度为 3 的子串：
| 起始位置 | k-mer |
|---|---|
| 0 | A C G |
| 1 | C G T |
| 2 | G T A |
| 3 | T A C |
| 4 | A C G |
| 5 | C G T |
位置 6 和 7 不够 3 个碱基，所以停止。
步骤 3：建立 k-mer → 位置列表 的映射
把相同的 k-mer 合并，记录它们在参考序列中出现的所有位置：
| k-mer | 出现位置 |
|---|---|
| ACG | 0, 4 |
| CGT | 1, 5 |
| GTA | 2 |
| TAC | 3 |
这个表就是索引。
实际工具中，这个表可能用哈希表、后缀数组、FM-index 等结构存储，但核心思想一样：
给定一个 k-mer，能快速查到它在参考基因组中的所有出现位置。
步骤 4：存储索引
索引是静态的，只需要在预处理阶段构建一次，之后可以反复用于很多 reads 的映射。
所以构建索引的时间可以分摊到大量查询上。
三、用索引做 Seeding：查询例子
假设现在有一个 read：
read：T A C G T
位置：0 1 2 3 4
步骤 1：把 read 也切成 k-mer（k=3）
| read 中的起始位置 | k-mer |
|---|---|
| 0 | T A C |
| 1 | A C G |
| 2 | C G T |
步骤 2：拿这些 k-mer 去索引里查
TAC→ 索引表查到位置 3ACG→ 索引表查到位置 0, 4CGT→ 索引表查到位置 1, 5
步骤 3：根据相对偏移确定候选映射位置
read 中：
TAC在 read 的位置 0；ACG在 read 的位置 1；CGT在 read 的位置 2。
如果 read 整体映射到参考序列的某个起始位置 p，那么：
TAC应出现在参考序列的 p + 0；ACG应出现在参考序列的 p + 1；CGT应出现在参考序列的 p + 2。
我们检查索引查到的位置：
- 若 p = 3，则：
TAC在 3 + 0 = 3 ✅（索引中 TAC 在 3）ACG在 3 + 1 = 4 ✅（索引中 ACG 在 4）CGT在 3 + 2 = 5 ✅（索引中 CGT 在 5）
三个 k-mer 的位置完全吻合。
所以 read TACGT 的候选映射位置就是参考序列的 位置 3。
四、如果没有索引会怎样？
没有索引时，要把 read 的 k-mer 和参考序列的每个位置逐一比较：
- 参考序列长度 8，read 长度 5，需要比较 8 - 5 + 1 = 4 个起始位置；
- 每个位置还要比较 5 个碱基，总共约 20 次字符比较。
有了索引，只需要查 3 次哈希表，再验证相对偏移，计算量大幅减少。
当参考基因组是 30 亿碱基、reads 是数亿条时，索引带来的加速是决定性的。
五、实际工具中的 Indexing 会复杂一些
论文 2.1 节没有展开索引的具体数据结构，但实际 read mapper 常用：
| 索引结构 | 代表工具 | 特点 |
|---|---|---|
| 哈希表 | BWA、Minimap2 | 直接存 k-mer → 位置 |
| 后缀数组 | BWA-SW | 支持更灵活的匹配 |
| FM-index | Bowtie、BWA | 内存占用小，查询快 |
| minimizer 索引 | Minimap2、SeGraM | 只索引窗口内最小的 k-mer，减少索引大小 |
SeGraM 用的就是 minimizer-based indexing：
它不是索引所有 k-mer，而是每个窗口只选一个最小的 k-mer（minimizer）来建索引。
这样索引更小，查询也更快，但仍然是“预处理参考基因组，生成索引，供 seeding 查询”这个思路。
六、一句话总结
Indexing 就是：先选一个 k，把参考基因组所有长度为 k 的子串取出来，记录每个 k-mer 出现的位置，建成一张查询表。之后 read 被切成 k-mer 后，直接查这张表，就能快速找到候选映射位置。
它是 seed-and-extend 流程的第一步，也是后续 seeding 能高效进行的基础。