1 Sequence-to-Graph Mapping Computation
2.2 节 Sequence-to-Graph Mapping Computation 主要是在讲：把一条 DNA read 映射到 pangenome graph 上，并不是一个单独算法，而是一条由多个阶段组成的流水线。它的总体策略是经典的 seed-and-extend：先快速找到很多短精确匹配的“种子”，再逐步筛选、连接、扩展，最后做碱基级精细对齐，得到 read 在图上的最优路径。
可以把它类比成：
你有一段文字（read），要在一张带岔路的地图（pangenome graph）里找出它最可能来自哪条路线。
地图的“顶点”存 DNA 片段，“边”表示合法相邻关系，变异则表现为分叉或小泡。
具体流程如下：
-
Indexing，索引，离线阶段
先对 pangenome graph 做预处理，建立哈希索引：把固定长度的子序列映射到它们在图中各个顶点出现的位置。
目的：之后给定 read 的一小段，可以快速查表，知道它可能出现在图里的哪些地方。
硬件特点：需要大量、不规则的哈希表访问。 -
Seeding，种子生成
把输入 read 切成许多重叠的短特征串，文中叫 minimizers，通常长 – bp。
然后用这些 minimizers 去查上面的索引。每命中一次，就产生一个 seed。
一条长 read 可能产生成千上万甚至上百万个候选 seed。
这一步本质是：先找“可能匹配的小碎片”。
硬件特点：同样是大规模、不规则的哈希查找。 -
Linear Chaining，线性链构建
现在 seed 很多且散乱。线性链阶段会在同一个图顶点内部，把 seed 用稀疏动态规划组织起来，判断哪些 seed 可以连成一条合理的局部链。
评分主要看“对角线一致性”和“间隙罚分”：如果两个 seed 在 query 和 graph 上的相对位置比较一致，就更容易被连起来。
输出是若干 linear chains，也就是局部路线。
硬件特点：稀疏动态规划，计算依赖稀疏，数据复用少。 -
Graph Chaining，图链构建
线性链只解决了同一个顶点内部的问题。图链阶段要跨顶点把这些线性链连起来。
它会计算链端点之间的最短路径，检查能不能通过图中的变异泡，也就是那些分支区域，从一个链走到另一个链。
在复杂区域，图遍历往往会主导运行时间。
硬件特点：需要图遍历、最短路径搜索，依赖不规则。 -
Filtering，过滤
重复区域会产生很多假 seed。过滤阶段用频率阈值和空间一致性检查，去掉这些不可信候选。
可以理解为：如果某个短串在基因组里出现太多次，或者位置关系明显不合理，就把它扔掉。
硬件特点：规则相对简单，但访问模式仍可能不规则。 -
Alignment，比对
最后，对筛选后选出的图路径和 read 做碱基级精细比对，使用 wavefront alignment，简称 WFA。
这一步会算出精确的匹配、插入、删除、替换关系，最终得到最优路径和比对结果。
硬件特点：密集动态规划，计算量大，但局部性比较可预测。
这一节最关键的一句话是：
每个阶段的硬件需求完全不同。
索引和种子生成需要大而不规则的哈希表访问；chaining 是稀疏动态规划，复用少；WFA 对齐是密集动态规划，局部性好。
因此，S2G 映射是一条“异构计算流水线”，很难只靠优化某一个阶段就获得全局最大收益。
所以，2.2 节实际上是在为后文做铺垫：
S2G 不是一个单一 kernel，而是多阶段、异构、候选数据量先大后小的流水线；各阶段计算模式差异大，中间数据又多，因此需要像 PanGaea 这样的统一融合加速器，而不是孤立优化每个阶段。