Skip to main content

4. PE and hops

在 SeGraM 的 BitAlign 中，图节点线性化并拓扑排序后，hop 边产生的多条路径并不会被显式枚举。BitAlign 采用的是位向量动态规划，它把所有可能路径的信息并行地压缩到位向量中，通过拓扑排序保证每个节点只在其所有后继处理完之后才被处理，从而一次性合并所有后继路径的状态。因此，多条路径不会导致路径爆炸，也不会需要单独追踪每条路径。

具体机制如下：

1. 拓扑排序保证处理顺序​

BitAlign 的输入是线性化且拓扑排序后的参考子图。拓扑排序确保：

  • 如果存在一条有向边（包括 hop）从节点 ii 指向节点 jj，那么在线性化序列中，jj 一定排在 ii 的后面。
  • 因此，当算法逆序遍历节点（从后往前）时，处理节点 ii 时，它的所有后继节点 jj 的状态已经计算完毕。

这样，无论从 ii 出发有多少条路径，它们都只会经过 ii 的后继节点，而这些后继的状态已经就绪。

2. 对每个节点，合并所有后继的状态​

BitAlign 算法（论文 Algorithm 1）在处理每个节点 ii 时，会遍历它的所有后继节点：

for j in subgraph-nodes[i].successors do
    R0 ← ((R[j][0] << 1) | curPM) & R0
    ...

这里的 subgraph-nodes[i].successors 包括两类后继：

  • 直接相邻的后继：通过普通边连接。
  • hop 后继：通过非相邻边（即 hop）连接，可能是由于插入、删除或结构变异产生的。

对于每个后继 jj，算法用它的状态位向量 R[j][d] 来更新当前节点 ii 的状态。更新操作是简单的位运算（移位、与、或），并且会与当前累积的结果 R0 进行合并。

这意味着：所有从 ii 出发、经过不同后继的路径，它们的匹配状态被同时考虑并合并到 R0 中。最终 R0 表示的是从节点 ii 出发，在所有可能路径中能够达到的最优匹配状态（例如，最小编辑距离下的部分匹配信息）。

3. 位向量天然支持多条路径并行​

位向量方法的核心在于：每个位向量的一位对应 query read 中的一个位置。当算法对多个后继的状态进行位运算时，实际上是在并行地计算所有路径在同一 query 位置上的匹配情况。

例如，对于 match 位向量：

R0 ← ((R[j][0] << 1) | curPM) & R0
  • R[j][0] 是后继 jj 在 0 错误下的状态。
  • 左移一位表示消耗一个 query 字符。
  • 或上 curPM 表示当前参考字符与 query 字符的匹配。
  • 与上 R0 表示取所有后继路径中都满足匹配的那些位置。

这样，多条路径的信息被“与”或“或”操作合并，最终得到的是在所有路径中都能成立的状态。对于编辑距离 d>0d>0，类似地合并 deletion、substitution、insertion 和 match 位向量。

因此，不需要枚举路径，也不需要为每条路径维护单独的状态。位向量 DP 天然地并行处理了所有路径。

4. 硬件支持：HopBits 和 Hop Queue​

在硬件层面，BitAlign 使用 HopBits 矩阵和 hop queue register 来支持 hop 后继的访问：

  • HopBits 矩阵：一个邻接矩阵，表示节点之间是否存在 hop。当处理节点 ii 时，HopBits 告诉硬件哪些后继节点 jj 是通过 hop 连接的。
  • Hop Queue Register：每个 PE 有一个 hop queue，存储之前节点产生的 R[d] 位向量。当当前节点需要某个 hop 后继的状态时，如果该后继在拓扑顺序中距离较远，它的状态可能已经被移出常规的 PE 间传递链，但 hop queue 会保留它，直到当前节点需要时再取出。
  • 根据 HopBits 的值，硬件选择使用实际的 hop 位向量，或者使用全 1 的位向量（表示无影响）。

论文中通过设置 hop limit = 12 来限制 hop 的最大距离，覆盖超过 99% 的 hop。这是因为大多数遗传变异是 SNP 或小 indel，产生短距离 hop；长距离的结构变异很少。这样既保证了准确性，又控制了硬件开销。

5. 最终结果：所有路径的最优对齐​

通过上述合并，BitAlign 在处理完整个线性化子图后，会得到每个节点在不同编辑距离下的状态位向量。最终，算法通过 traceback 找到从 query read 到参考子图的最优对齐（最小编辑距离或最高分）。这个最优对齐是在所有可能路径中选出的，因为每个节点的状态已经包含了所有后继路径的信息。

因此，hop 边产生的多条路径被位向量 DP 统一处理，不会导致路径数量爆炸，也不需要显式枚举。

总结​

  • 拓扑排序确保后继节点先于当前节点处理。
  • BitAlign 对每个节点遍历所有后继（包括 hop），用位运算将后继状态合并到当前节点的状态中。
  • 位向量 DP 并行处理所有路径，每条路径的信息被压缩在位向量中，通过“与/或/移位”操作同时考虑。
  • 硬件用 HopBits 矩阵和 hop queue 支持 hop 后继的访问，并通过 hop limit 限制硬件开销。
  • 最终得到的是所有路径中的最优对齐，而不是单独追踪每条路径。

所以，SeGraM 处理 hop 边多条路径的方式是：不枚举路径，而是用拓扑排序 + 位向量动态规划，将所有路径的信息并行合并，一次性计算出最优匹配。