1 Genome Sequence Analysis
下面我按“2.1 Genome Sequence Analysis”这一节的内容，帮你把核心逻辑、流程和术语拆开讲清楚。这一节本质上是在介绍传统线性参考基因组下的 read mapping（读段映射），也就是把测序仪产生的短序列片段（reads）定位到参考基因组上的过程。它是后续所有基因组分析（变异检测、组装、错误校正等）的基础。
一、这一节要解决什么问题？
基因组测序仪不能一次性读出整条 DNA，而是把 DNA 打成很多小片段，这些片段叫 reads。
但测序之后，我们不知道每个 read 来自基因组的哪个位置。
所以需要做 read mapping：把每个 read 找回到参考基因组上的原始位置。
原文说：
Most types of genome sequence analysis start with finding the original locations of the sequenced reads on the reference genome of the organism, via a computational process called read mapping.
翻译过来就是：
大多数基因组分析的第一步，都是通过一个叫 read mapping 的计算过程，找到测序 reads 在参考基因组上的原始位置。
二、核心策略：seed-and-extend（种子-扩展）
为了快速完成映射，现有工具普遍采用 seed-and-extend 策略。
它分成四个阶段：
| 阶段 | 名称 | 是否必须 | 主要任务 |
|---|---|---|---|
| 0 | Indexing（索引） | 必须，预处理 | 为参考基因组建立索引，加速后续查找 |
| 1 | Seeding（ seeding，种子） | 必须 | 把 read 切成 k-mer，在参考基因组中找精确匹配位置 |
| 2 | Filtering / Chaining / Clustering（过滤/链接/聚类） | 可选 | 去掉明显不可能的候选位置，减少后续比对量 |
| 3 | Alignment（比对） | 必须 | 对剩余候选区域做近似字符串匹配，允许错配、插入、删除 |
这四步可以用一个直观类比理解：
- 参考基因组 = 一本很厚的书；
- read = 从书里撕下来的一小段句子；
- Indexing = 给书做目录/索引；
- Seeding = 先拿句子里的几个关键词去目录里快速找可能页码；
- Filtering/Chaining/Clustering = 排除明显不对的页码；
- Alignment = 对剩下的页码逐字比对，允许有错字、漏字、多字，最终确定最可能的位置。
三、逐阶段拆解
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 阶段能快速查找。
为什么要索引？
因为人类基因组有约 30 亿个碱基，如果每个 read 都从头扫一遍，太慢了。
索引相当于“目录”，可以快速定位某个短串可能出现在哪里。
2. Seeding：种子
原文：
Seeding finds the set of k-length substrings (i.e., k-mers) to represent each read and finds the exact matching locations of these k-mers in the reference genome (i.e., seeds).
意思是：
Seeding 把每个 read 切成很多长度为 k 的子串，这些子串叫 k-mer。
然后到参考基因组的索引里，找这些 k-mer 的精确匹配位置。
这些精确匹配的位置就叫 seeds（种子）。
这些 seeds 代表了 read 在参考基因组上的候选映射位置。
注意两个关键词：
- k-mer：长度为 k 的短串，比如 k=15，就是 15 个碱基的片段；
- exact matching：精确匹配，不允许错配，所以这一步很快，但只是“粗略定位”。
Seeding 的目标不是最终确定位置，而是快速缩小范围，给出候选区域。
3. Filtering / Chaining / Clustering：过滤/链接/聚类（可选）
原文：
Many read mappers include an optional filtering/chaining/clustering step to eliminate candidate mapping regions around the seed locations from the previous step that are dissimilar to the query read to decrease the number of alignment operations.
意思是：
很多 read mapper 会加一个可选步骤，对 seeding 得到的候选位置进行过滤、链接或聚类。
目的是：去掉那些明显和 read 不像的候选区域，从而减少下一步 alignment 的工作量。
为什么这一步重要？
因为 seeding 会产生很多候选位置，尤其是重复区域。
如果每个候选都做完整比对，计算量会爆炸。
所以先粗筛一遍，把明显不可能的去掉。
这一步是“可选”的，不同工具可能用不同方法：
- Filtering：直接过滤；
- Chaining：把多个 seed 连成链，看是否一致；
- Clustering：把空间上接近的 seed 聚成一类。
4. Alignment：比对
原文：
Finally, to find the read's optimal mapping location while taking sequencing errors and the differences caused by variations and mutations into account, alignment performs approximate string matching (i.e., ASM) between the read and the reference regions around the non-filtered candidate mapping locations from the previous step.
意思是：
最后，为了找到 read 的最优映射位置，同时考虑测序错误、遗传变异和突变带来的差异，Alignment 会在 read 和剩余候选参考区域之间做近似字符串匹配（ASM）。
这里的关键是 approximate string matching，它不是要求完全一样，而是允许三种差异：
- substitutions（替换）：一个碱基变成另一个；
- insertions（插入）：read 里多了一个碱基；
- deletions（删除）：read 里少了一个碱基。
然后，原文还提到：
As part of the alignment step, traceback is also performed to find the optimal alignment between the read and the reference region, which is the alignment with the highest likelihood of being correct (based on a scoring function) or with lowest edit distance (i.e., total number of edits: substitutions, insertions, deletions).
意思是：
Alignment 阶段还会做 traceback（回溯），找出 read 和参考区域之间的最优比对。
“最优”有两种常见定义：
- 打分函数最高：基于一个 scoring function，认为这个比对最可能是正确的；
- 编辑距离最小：编辑距离 = 替换数 + 插入数 + 删除数，越小越好。
Traceback 的作用是：
不仅算出最小编辑距离，还要还原出具体是怎么比对的，比如哪些位置是匹配、哪些是替换、哪里插入、哪里删除。
四、关键术语总结
| 术语 | 含义 |
|---|---|
| Read | 测序仪产生的短 DNA 片段 |
| Reference genome | 参考基因组，代表一个物种的基准序列 |
| Read mapping | 把 read 定位到参考基因组上的过程 |
| Seed-and-extend | 先用种子快速定位，再扩展比对 |
| Indexing | 为参考基因组建索引，加速查找 |
| k-mer | 长度为 k 的短串 |
| Seed | k-mer 在参考基因组上的精确匹配位置 |
| Candidate mapping location | 候选映射位置 |
| Filtering/Chaining/Clustering | 可选粗筛，减少候选 |
| Alignment | 近似字符串匹配，允许替换、插入、删除 |
| ASM | Approximate String Matching，近似字符串匹配 |
| Edit distance | 替换+插入+删除的总数 |
| Traceback | 回溯，还原最优比对路径 |
| Scoring function | 打分函数，用于判断哪个比对最优 |
五、这一节为什么重要？
原文在后文也提到：
read-to-reference mapping is one of the major bottlenecks of the full genome sequence analysis pipeline
也就是说，read mapping 是整个基因组分析流程的主要瓶颈之一。
而且它计算量大、内存访问不规则，所以后面才会需要 SeGraM 这样的硬件加速器，专门加速 seeding 和 alignment。
2.1 节的作用就是先把这个基础流程讲清楚，让读者明白：
- 为什么需要索引；
- 为什么 seeding 要快；
- 为什么 alignment 最耗时；
- 为什么后续要针对这些步骤做算法/硬件协同设计。
六、一句话总结
2.1 节讲的是：传统线性参考基因组下，如何用 seed-and-extend 四阶段流程，把测序 reads 映射回参考基因组；其中 seeding 负责快速找候选位置，alignment 负责精细比对并允许错配、插入、删除，最终通过打分或编辑距离确定最优位置。
如果你愿意，我也可以继续把 2.2 Graph-Based Genome Sequence Analysis 对照着讲一遍，这样你能更清楚“线性参考”和“图参考”的区别。