2.3.1 POA model

这个公式是 Partial Order Alignment（POA） 的核心动态规划递推式。它描述了：当把一条新序列（Read）比对到一个偏序图（Partial Order Graph）上时，如何计算每个单元格的最优得分。

与标准 Smith-Waterman 不同，POA 的“参考”不是一条线性序列，而是一个有向无环图。因此，它的递推公式需要考虑图中的前驱节点，而不仅仅是上一行或上一列。

1. 公式整体含义

H(i,j) = \max \{ H(p(i), q(j)) + S(X(i), Y(j)),\ H(p(i), j) + g(j),\ H(i, q(j)) + g(i) \}

$H(i,j)$ ：表示将偏序图中的节点 $i$ 与新序列（Read）的第 $j$ 个碱基进行比对时，所能得到的最优得分。
$\max$ ：和 BSW 一样，我们要在所有可能的编辑操作中，选择得分最高的那一种。
公式中有三个候选，分别对应三种操作：匹配/错配、删除、插入。

2. 符号详细解释

2.1 图与序列

$i$ ：偏序图中的节点索引。每个节点代表一个碱基（A/C/G/T）。
$j$ ：新序列（Read）中的碱基位置， $1 \le j \le n$ 。
$X(i)$ ：图中节点 $i$ 对应的碱基。
$Y(j)$ ：新序列第 $j$ 个碱基。

2.2 前驱节点

$p(i)$ ：节点 $i$ 的前驱节点（predecessor）。在偏序图中，一个节点可能有多个前驱，因为图可以分叉。实际计算时， $H(p(i), q(j))$ 应该对所有 $p(i) \in \text{predecessors}(i)$ 取最大值。公式中为了简洁，只写了一个 $p(i)$ 。
$q(j)$ ：序列位置 $j$ 的前驱位置。因为序列是线性的，所以通常 $q(j) = j-1$ 。

2.3 得分与罚分

$S(X(i), Y(j))$ ：节点 $i$ 的碱基 $X(i)$ 与序列碱基 $Y(j)$ 之间的相似性得分。相同则加分，不同则减分或给低分。
$g(j)$ ：在序列方向上的 gap 罚分。当图前进但序列不动时使用。
$g(i)$ ：在图方向上的 gap 罚分。当序列前进但图不动时使用。

3. 三个候选的物理意义

3.1 对角线：匹配或错配

H(p(i), q(j)) + S(X(i), Y(j))

操作：将图中的节点 $i$ 与序列的第 $j$ 个碱基对齐。
前驱状态：图退到前驱节点 $p(i)$ ，序列退到前一个位置 $q(j)=j-1$ 。
得分：前驱状态得分 $H(p(i), q(j))$ 加上当前碱基的匹配/错配得分 $S(X(i), Y(j))$ 。
直观理解：这是最自然的比对方式，消耗图的一个节点和序列的一个碱基。

3.2 上方：图前进，序列不动（删除）

H(p(i), j) + g(j)

操作：图从 $p(i)$ 前进到 $i$ ，但序列位置 $j$ 不变。
含义：图中的节点 $i$ 在序列中没有对应的碱基，相当于在序列中插入了一个 gap（即序列相对于图发生了缺失）。
前驱状态： $H(p(i), j)$ ，即图退到前驱，序列位置不变。
罚分：加上 gap 罚分 $g(j)$ 。
直观理解：图中的这个碱基是“多余”的，没有匹配到序列上。

3.3 左方：序列前进，图不动（插入）

H(i, q(j)) + g(i)

操作：序列从 $q(j)$ 前进到 $j$ ，但图节点 $i$ 不变。
含义：序列中的碱基 $Y(j)$ 在图中没有对应的节点，相当于在图/参考中插入了一个 gap（即序列相对于图发生了插入）。
前驱状态： $H(i, q(j))$ ，即图节点不变，序列退到前一个位置。
罚分：加上 gap 罚分 $g(i)$ 。
直观理解：序列多出了一个碱基，图中没有对应的节点。

4. 为什么取最大值？

与 BSW 一样，动态规划的核心是最优子结构。在 $(i,j)$ 处，我们不知道哪种操作会带来最高分。可能匹配得分高，也可能插入/删除避免了大的错配罚分。因此，必须计算所有可能的操作，然后取最大值。

这个 $\max$ 保证了 $H(i,j)$ 记录的是到达该状态的最优得分。

5. 与 BSW 公式的对比

特性	BSW	POA
参考结构	线性序列	偏序图
对角线前驱	$i-1, j-1$	$p(i), q(j)$ ，其中 $p(i)$ 是图的前驱，可能不是 $i-1$
上方前驱	$i-1, j$	$p(i), j$
左方前驱	$i, j-1$	$i, q(j)$ ，通常 $q(j)=j-1$
依赖范围	固定：前一行和当前行	可变：可能依赖图中任意前驱节点，产生长距离依赖
精度	整数	整数（论文中为 32-bit）

关键区别在于 $p(i)$ ：在 BSW 中， $p(i) = i-1$ ，依赖是规则的；在 POA 中， $p(i)$ 可以是图中任意一个前驱节点，可能离当前节点很远。这就是论文中提到的 long-range dependency。

6. 举例说明

假设偏序图如下：

    B —— D
  /       \
A          F
  \       /
    C —— E

节点 F 有两个前驱：D 和 E。当计算 $H(F, j)$ 时，对角线候选为：

H(p(F), q(j)) + S(X(F), Y(j))

这里 $p(F)$ 可以是 D 或 E。因此，实际计算时需要对所有前驱取最大值：

\max_{p \in \{D, E\}} H(p, q(j)) + S(X(F), Y(j))

这导致 F 的得分可能依赖 D 行或 E 行的结果，而 D 和 E 在图中可能相隔很远，对应 DP 表中的行号差距很大，形成长距离依赖。

7. GenDP 如何支持这个模型？

论文中 GenDP 的 DPAx 架构通过以下机制支持 POA：

Scratchpad Memory (SPM)：每个 PE 内部有 SPM，用于存储长距离依赖的候选单元格结果。因为 $p(i)$ 可能不是上一行，而是更早的行，需要把这些结果保存下来。
解耦控制与计算：POA 的依赖模式由图结构决定，需要分支指令控制数据移动。DPAx 将控制线程和计算线程分开，控制线程管理 SPM 和相邻 PE 的数据流。
DPMap 映射目标函数：DPMap 将 POA 的目标函数数据流图划分成子图，映射到 PE 内的 ALU 阵列。POA 的目标函数与 BSW 类似，但依赖复杂，DPMap 需要满足计算单元的结构约束。
长距离依赖限制：GenDP 支持每行最多 128 个单元格距离的长距离依赖。超过 128 的超长依赖（占 2.4% 工作负载）在主机 CPU 上执行。

8. 一句话总结

POA 的数学模型是一个图结构上的动态规划：

$H(i,j)$ 表示图节点 $i$ 与序列位置 $j$ 比对的最优得分；
三个候选分别对应匹配/错配、删除、插入；
与 BSW 最大的不同是 $p(i)$ 是图中任意前驱，导致依赖不固定、存在长距离依赖；
取最大值保证最优路径；
GenDP 通过 SPM、解耦控制和 DPMap 映射来高效支持这种不规则依赖。

1. 公式整体含义​

2. 符号详细解释​

2.1 图与序列​

2.2 前驱节点​

2.3 得分与罚分​

3. 三个候选的物理意义​

3.1 对角线：匹配或错配​

3.2 上方：图前进，序列不动（删除）​

3.3 左方：序列前进，图不动（插入）​

4. 为什么取最大值？​

5. 与 BSW 公式的对比​

6. 举例说明​

7. GenDP 如何支持这个模型？​

8. 一句话总结​