3.2 Accelerating Sequence-to-Graph Mapping
下面把论文 3.2 Accelerating Sequence-to-Graph Mapping 这一节拆开讲清楚。
这一节的核心结论是：现有的加速器（无论是为 S2S 设计的，还是通用的图处理加速器）都不能直接用来加速 S2G，因为 S2G 的瓶颈是 alignment，而 alignment 在图中变得异常复杂。因此必须专门为 S2G 设计算法和硬件。
一、先明确 S2S 与 S2G 的关系
论文说：
S2S mapping is a special case of S2G mapping, where all nodes have only one edge.
翻译：
S2S 映射是 S2G 映射的一个特例，在这个特例里，图中的每个节点只有一条出边。
也就是说，线性参考序列可以看作一个非常简单的图：每个节点只连向下一个节点，没有分支。
而真正的基因组图有：
- 多条出边（表示 SNP、插入、删除、结构变异）；
- 非相邻节点之间的边，叫 hop（跳转）。
所以：
- S2S 加速器只适用于“单出边”的简单情况；
- S2G 需要处理“多出边 + hop”的复杂情况。
二、S2S 加速器为什么不能直接用于 S2G？
论文说：
Existing accelerators are limited to only this special case, and are unsuitable for the more general S2G mapping problem, where we also need to consider multiple edges (i.e., hops) that a node can have.
翻译：
现有加速器只支持“每个节点一条出边”的特例，无法处理更一般的 S2G 问题，因为 S2G 需要考虑一个节点可能有多条出边（即 hop）。
类比理解
- S2S：像一条单车道公路，每个路口只能直行，不能拐弯。
- S2G：像一张城市路网，有岔路、环岛、立交桥。
- 现有 S2S 加速器只会在单车道上前进，遇到岔路就不知道怎么办。
所以，不能直接把 S2S 加速器拿来跑 S2G。
三、S2G 比 S2S 复杂在哪里？论文列出四个问题
论文原文：
S2G mapping is a more complex problem than S2S mapping since the graph structure is more complex than a linear sequence. This additional complexity results in four issues.
翻译：
S2G 比 S2S 更复杂，因为图结构比线性序列复杂。这种额外复杂性带来四个问题。
问题 1：Alignment 本身更贵
First, even though solutions for both problems follow the seed-and-extend approach, the already-expensive alignment step of S2S mapping is even more expensive in S2G mapping due to the hops in the graph that must be handled.
翻译：
虽然两者都采用 seed-and-extend 策略，但 S2S 中已经很贵的 alignment，在 S2G 中因为要处理图中的 hop，变得更加昂贵。
原因：
S2S 对齐时，每个单元格只依赖相邻的三个单元格。
S2G 对齐时，只要存在 hop，当前单元格还要依赖所有有边连过来的非相邻节点。
依赖变多 → 计算量变大 → alignment 更慢。
问题 2：执行流不规则，内存访问不规则
Second, these hops add irregularity to the execution flow of alignment since they can originate from any vertex in the graph, leading to more data dependencies and irregular memory accesses.
翻译：
hop 可以来自图中任意顶点，这给 alignment 的执行流带来不规则性，导致更多数据依赖和更不规则的内存访问。
类比：
单车道公路上，你只需看前一个路口。
城市路网中，你要看所有可能拐进来的路，而且这些路可能来自任意方向。
这会让 CPU/GPU 的缓存和预取机制失效，内存访问变得随机。
问题 3：S2S 的启发式方法不适用于图
Third, the heuristics used in S2S alignment are often not directly applicable to the S2G problem, as they assume a single linear reference sequence. For example, chaining, which is used to combine different seed hits in long read mapping (assuming they are part of a linear sequence), cannot be used directly for a genome graph because there can be multiple paths connecting two seeds together in the graph.
翻译：
S2S 中使用的启发式方法通常不能直接用于 S2G，因为它们假设参考是一条线性序列。
例如，chaining（把多个 seed 连成链）在长读段映射中用来组合不同 seed，它假设这些 seed 属于同一条线性序列。
但在基因组图中，两个 seed 之间可能有多条路径连接，所以不能直接链起来。
原因：
线性序列中，两个 seed 之间的顺序和距离是唯一的。
图中，两个 seed 之间可能有多条路径，距离也不唯一。
所以 S2S 的优化技巧在图中失效。
问题 4：搜索空间大得多
Fourth, since the genome graph contains both the linear reference sequence and the genetic variations, the search space for the query reads is much larger in S2G mapping than in S2S mapping.
翻译：
基因组图既包含线性参考序列，又包含遗传变异，所以 S2G 中查询 read 的搜索空间比 S2S 大得多。
原因：
线性参考只有一条序列。
基因组图包含参考 + 所有已知变异，可能有很多分支。
read 要尝试匹配的位置数量大幅增加。
四、为什么不能把图展开成线性路径，再用 S2S 加速器？
论文说：
Existing S2S mapping accelerators can mimic the behavior of S2G mapping by taking all paths that exist in the genome graph into account and aligning the same read to each of these paths one at a time. However, this would be prohibitively inefficient in terms of both computation and memory requirements (e.g., it would require an exorbitant memory footprint to store all possible graph paths as separate linear sequence strings).
翻译：
现有 S2S 加速器可以这样模拟 S2G：把图中所有路径都展开成线性序列，然后把同一个 read 逐条比对。
但这样做在计算和内存上都极其低效。
例如，要把所有可能的图路径都存成独立的线性字符串，内存占用会爆炸。
类比：
城市路网有无数条从 A 到 B 的路线。
如果你想用“单车道加速器”处理，就得先把所有路线都写成独立的单车道清单。
这个清单会大到无法存储，计算量也大到无法接受。
所以，不能靠展开路径来绕过问题。
五、图处理加速器为什么也不行？
论文说：
Unlike typical graph traversal workloads, sequence-to-graph mapping involves high amounts of both random memory accesses (due to the seeding step) and expensive computations (due to the alignment step). Seeding enables the mapping algorithm to detect and focus on only certain candidate subgraphs, eliminating the need for a full graph traversal. Alignment is not a graph traversal workload, and instead is an expensive bitvector-based or DP-based computational problem. While existing graph accelerators could potentially be customized to help the seeding step of the sequence-to-graph mapping pipeline, they are unable to handle the major bottleneck of sequence-to-graph mapping, which is alignment.
翻译：
与典型的图遍历工作负载不同，S2G 映射既包含大量随机内存访问（来自 seeding），又包含昂贵计算（来自 alignment）。
Seeding 让映射算法只关注某些候选子图，不需要完整遍历图。
Alignment 不是图遍历工作负载，而是一个昂贵的基于位向量或动态规划的计算问题。
现有图加速器可能可以定制来帮助 seeding，但它们无法处理 S2G 的主要瓶颈——alignment。
关键点：
- 图处理加速器（如 GraphPIM、GraphR 等）擅长的是 图遍历，比如 BFS、PageRank、最短路径。
- S2G 的瓶颈不是图遍历，而是 alignment，即近似字符串匹配。
- Alignment 需要大量位运算和动态规划，不是“沿着边走”那么简单。
- 所以图加速器帮不上 alignment 的忙。
六、总结：为什么必须专门设计 S2G 加速器？
把以上内容串起来：
- S2S 加速器：只能处理单出边的线性参考，无法处理多出边和 hop。
- 展开路径法：内存和计算爆炸，不可行。
- 图处理加速器：擅长图遍历，但 S2G 瓶颈在 alignment，不是图遍历。
- S2G 的四个复杂点：alignment 更贵、执行不规则、S2S 启发式失效、搜索空间更大。
因此，论文的结论是：
Thus, with the growing importance and usage of genome graphs, it is crucial to have efficient designs optimized for sequence-to-graph mapping, which can effectively work with both short and long reads.
翻译：
随着基因组图越来越重要，必须专门设计高效的 S2G 映射方案，能够同时处理短读段和长读段。
这就是 SeGraM 的动机：
- MinSeed 专门加速 seeding，支持图结构；
- BitAlign 专门加速 alignment，支持 hop 和位向量计算；
- 两者协同，才能高效完成 S2G。
七、一张表总结 3.2 的核心逻辑
| 问题 | 说明 |
|---|---|
| S2S 加速器能用于 S2G 吗？ | 不能，因为 S2S 是单出边特例，S2G 有多出边和 hop |
| 把图展开成线性路径可行吗？ | 不可行，内存和计算爆炸 |
| 图处理加速器能帮忙吗？ | 只能帮 seeding，帮不了 alignment（瓶颈） |
| S2G 比 S2S 复杂在哪？ | ① alignment 更贵；② 执行不规则；③ 启发式失效；④ 搜索空间更大 |
| 结论 | 必须专门为 S2G 设计算法和硬件，即 SeGraM |
八、一句话总结
3.2 节讲的是：现有 S2S 加速器和通用图加速器都无法有效加速 S2G，因为 S2G 的瓶颈是带 hop 的 alignment，它比 S2S 复杂得多；把图展开成路径又不可行；因此必须专门为 S2G 设计算法和硬件，这正是 SeGraM 的出发点。