7 BitAlign Algorithm

下面把论文 第 7 节 BITALIGN ALGORITHM 拆开讲清楚。
这一节讲的是 SeGraM 中负责 alignment（精细比对） 的算法：BitAlign。
它的任务是：对 MinSeed 找到的每个候选子图，计算它和 query read 之间的编辑距离和最优比对。

---

一、BitAlign 的定位

前面第 4 节说：

• MinSeed 负责 seeding，输出候选子图；
• BitAlign 负责 alignment，对每个 (read, subgraph) 对做精细比对。

第 7 节就是讲 BitAlign 的算法原理。
它基于 GenASM（一个已有的 S2S 比对加速器），但做了关键修改，使其能处理图结构。

---

二、先回顾 GenASM：为什么用 bitvector？

论文原文：

GenASM makes the bitvector-based Bitap algorithm suitable for efficient hardware implementation. ... both algorithms operate on tables. The key difference is that cell values are bitvectors in GenASM, whereas cell values are numerical values in DP-based algorithms.

翻译：
GenASM 把基于位向量的 Bitap 算法改造成适合硬件实现的形式。
它和传统动态规划（DP）一样，都在表格上操作。
区别在于：

• DP：单元格里存数值（编辑距离）；
• GenASM：单元格里存位向量（用二进制位表示匹配状态）。

为什么位向量好？
因为位运算（AND、OR、移位）在硬件里非常快，可以一次处理很多位，实现并行加速。

---

三、S2S 与 S2G 对齐的核心区别

论文原文：

There is a major difference between sequence-to-sequence alignment and sequence-to-graph alignment: for the current character, sequence-to-sequence alignment needs to know about only the neighboring (i.e., previous/adjacent) text character, whereas sequence-to-graph alignment must incorporate non-neighboring characters as well whenever there is an edge (i.e., hop) from the current character to the non-neighboring character.

翻译：
S2S 对齐时，当前字符只依赖相邻的前一个字符；
S2G 对齐时，只要存在从非相邻字符到当前字符的边（即 hop），就必须把这些非相邻字符也纳入计算。

通俗理解：

• S2S 像一条直线，每个位置只看前一个位置；
• S2G 像一张图，当前节点可能有多个前驱，其中一些可能来自很远的节点（hop）。

所以 BitAlign 必须显式处理 hop。

为了高效处理依赖，论文说：

To ensure that each of these data dependencies can be resolved as quickly as possible, we topologically sort the input graph during pre-processing.

翻译：
为了尽快解决这些数据依赖，我们在预处理阶段对输入图做拓扑排序。

拓扑排序保证：

• 所有边都从前面的节点指向后面的节点；
• 按顺序遍历时，当前节点依赖的所有前驱都已经计算完毕。

---

四、Algorithm 1：BitAlign 算法流程

论文给出了算法 1。我们逐步拆解。

输入和输出

• 输入：线性化且拓扑排序的子图（reference）、query read（pattern）、编辑距离阈值 k。
• 输出：最小编辑距离 editDist、CIGAR 字符串（描述比对结果，比如匹配、替换、插入、删除）。

步骤 1：生成本模式位掩码

PM ← genPatternBitmasks(query-read)

为 query read 生成四个模式位掩码，分别对应 A、C、G、T。
每个位掩码表示：read 中哪些位置是该字符。

步骤 2：初始化 allR

allR[n][d] ← 111...111

• n：线性化子图的长度（节点数）；
• d：编辑距离，从 0 到 k；
• allR 存储所有迭代的状态位向量，后面 traceback 要用。

步骤 3：从后往前遍历每个节点

for i in (n-1):-1:0 do

为什么从后往前？
因为拓扑排序后，后面的节点是前面的节点的后继。
从后往前计算，可以保证当前节点依赖的后继节点已经算好。

步骤 4：处理 d = 0（精确匹配情况）

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

• curChar：当前节点的字符；
• curPM：该字符对应的模式位掩码；
• 遍历当前节点的所有后继（包括 hop）；
• 对每个后继 j，取它的 R[j][0]，左移一位，与 curPM 做 OR，再与 R0 做 AND；
• 最终得到当前节点在编辑距离 0 下的状态位向量。

关键：这里遍历了所有后继，所以 hop 被自然处理。

步骤 5：处理 d = 1 到 k（允许编辑）

for d in 1:k do
    I ← (allR[i][d-1] << 1)
    R0 ← I
    for j in subgraph-nodes[i].successors do
        D ← allR[j][d-1]
        S ← allR[j][d-1] << 1
        M ← (allR[j][d] << 1) | curPM
        R0 ← D & S & M & Rd
    allR[i][d] ← Rd

这里计算四种操作：

• I（插入）：(allR[i][d-1] << 1)，插入不消耗参考字符，所以只看当前节点的 d-1；
• D（删除）：allR[j][d-1]，删除消耗参考字符，所以看后继的 d-1；
• S（替换）：allR[j][d-1] << 1，替换同时消耗 read 和参考字符；
• M（匹配）：(allR[j][d] << 1) | curPM，匹配不增加编辑距离，看后继的 d。

然后 R0 = D & S & M & Rd，得到当前节点在编辑距离 d 下的状态。
最后存 allR[i][d] = Rd。

注意：插入 I 不需要遍历后继，因为插入不消耗参考字符，只消耗 read 字符。
而 D、S、M 都需要考虑后继，所以放在循环里。

步骤 6：回溯（Traceback）

<editDist, CIGARstr> traceback(allR, subgraph, query-read)

所有节点计算完后，从 allR 中回溯，找到最优比对路径，输出编辑距离和 CIGAR 字符串。

---

五、关键优化 1：只存 R[d] 而不是所有中间向量

论文原文：

To perform GenASM-like traceback, BitAlign stores (3(k + 1)) bitvectors per graph edge ... Since the number of edges in the graph can only be bounded very loosely, the potential memory footprint increases significantly ... We solve this problem by storing only (k + 1) bitvectors per node (i.e., R[d] bitvectors), from which the (3(k + 1)) bitvectors per edge can be regenerated on-demand during traceback.

翻译：
GenASM 做 traceback 时，每条边要存 (3(k+1)) 个位向量。
但图中的边数很难精确限制，内存会爆炸。
BitAlign 改为每个节点只存 (k+1) 个位向量（即 R[d]），
traceback 时再按需重新生成那 (3(k+1)) 个中间向量。

效果：内存减少至少 3 倍。
因为 alignment 硬件的主要面积和功耗来自内存，这个优化非常关键。

---

六、关键优化 2：分治（Divide-and-Conquer）

论文原文：

Similar to GenASM, BitAlign also follows the divide-and-conquer approach, where we divide the linearized subgraph and the query read into overlapping windows and execute BitAlign for each window. After all windows' traceback outputs are found, we merge them to find the final traceback output.

翻译：
BitAlign 采用分治策略：
把线性化子图和 query read 分成有重叠的窗口，对每个窗口分别执行 BitAlign。
所有窗口的 traceback 结果出来后，再合并成最终结果。

为什么？
长 read 和长子图会让 allR 表非常大，内存放不下。
分窗口后，每次只处理一小段，内存占用小，复杂度低。
窗口重叠是为了避免边界处的比对被切断。

---

七、BitAlign 与 GenASM 的对比

维度	GenASM	BitAlign
适用问题	S2S 对齐	S2G 对齐
参考结构	线性序列	图（含 hop）
依赖	只看相邻字符	看所有后继（含 hop）
存储	每条边存 (3(k+1)) 个位向量	每个节点只存 (k+1) 个位向量
Traceback	直接使用存储的中间向量	按需重新生成中间向量
内存	较大	减少至少 3 倍
分治	有	有，且窗口重叠

---

八、总结：第 7 节的核心逻辑

1. BitAlign 基于 GenASM：用 bitvector 表示 DP 状态，位运算加速。
2. 核心挑战是 hop：S2G 必须处理非相邻节点的边，所以算法要遍历所有后继。
3. 拓扑排序：预处理时对图排序，保证从后往前计算时依赖已就绪。
4. 算法流程：
   • 生成本模式位掩码；
   • 从后往前遍历节点；
   • d=0 时计算精确匹配；
   • d>0 时计算插入、删除、替换、匹配，并遍历后继处理 hop；
   • 存储 allR；
   • traceback 得到最优比对。
5. 存储优化：只存 R[d] per node，内存减少 3 倍。
6. 分治策略：窗口重叠，降低内存和复杂度。

一句话：
BitAlign 是一个专门为图结构设计的 bitvector 比对算法。它用拓扑排序和遍历后继来处理 hop，用位运算加速编辑距离计算，通过只存 R[d] 和分治窗口大幅降低内存，从而在硬件上高效完成 S2G 的 alignment。