Skip to main content

2.4.1 Chain model

论文中的 Chain 算法用于长读测序中的锚点链化（anchoring chaining）。它把两个长读之间共享的种子锚点（anchors）连接成共线的重叠区域。其数学模型是一个一维动态规划，核心是计算每个锚点的最优得分，并记录最佳前驱。论文给出了两种形式：(ii) Anchor dependency（原始依赖） 和 (iii) Reordered anchor dependency（重排序依赖）。下面详细解释。

1. Chain 的基本概念​

  • 锚点（Anchor）：一个种子匹配对，表示 read A 的位置 xx 和 read B 的位置 yy 匹配。通常还带有一个权重 ww，表示匹配长度或质量。
  • 共线性（Collinearity）：如果锚点 ii 在锚点 jj 之前，则它们在两条序列上的位置也应保持顺序，即 xi<xjx_i < x_j 且 yi<yjy_i < y_j。
  • 目标：找一组共线锚点，使总得分最大。得分 = 锚点权重之和 − 连接 gap 惩罚。

2. 原始 Chain 数学模型：(ii) Anchor dependency​

图片中的公式有笔误，正确形式应为：

score(i)=max⁡{wi, max⁡1≤j<i(score(j)+weight(j,i))}score(i) = \max\left\{ w_i,\ \max_{1 \le j < i} \left( score(j) + weight(j, i) \right) \right\}

其中：

  • score(i)score(i)：以第 ii 个锚点结尾的最优链得分。
  • wiw_i：锚点 ii 自身的权重。表示如果从锚点 ii 重新开始一条链，得分为 wiw_i。
  • weight(j,i)weight(j, i)：从锚点 jj 连接到锚点 ii 的转移得分。通常考虑两个锚点之间的 gap 惩罚，例如： weight(j,i)=min⁡(yi−yj, xi−xj)−gap penaltyweight(j, i) = \min(y_i - y_j,\ x_i - x_j) - \text{gap penalty} 论文未给出具体公式，但本质是衡量两个锚点共线程度的得分。
  • 内层 max⁡1≤j<i\max_{1 \le j < i}：遍历所有在 ii 之前的锚点 jj，但实际实现中只检查前 NN 个锚点（默认 N=25N=25），即 j∈[i−N,i−1]j \in [i-N, i-1]。

计算顺序：必须按锚点顺序 i=1,2,…,Mi=1,2,\ldots,M 依次计算。因为 score(i)score(i) 依赖所有 j<ij < i 的 score(j)score(j)，所以是串行的。对于长读测序，锚点数量可达数万，串行计算成为瓶颈。

3. 重排序 Chain 数学模型：(iii) Reordered anchor dependency​

为了并行化，重排序版本反转依赖方向：每个锚点 ii 计算完自己的得分后，主动去更新它后面的 NN 个锚点 jj。公式为：

for i<j≤i+N,score(j)=max⁡(score(j), score(i)+weight(i,j))\text{for } i < j \le i + N,\quad score(j) = \max\left( score(j),\ score(i) + weight(i, j) \right)

初始时，每个锚点的得分为其自身权重：

score(j)=wjscore(j) = w_j

然后按顺序计算 i=1,2,…,Mi=1,2,\ldots,M，对于每个 ii，并行地更新 j=i+1,…,i+Nj = i+1, \ldots, i+N。

关键点：

  • score(j)score(j) 是一个累加器，可以被多个 ii 更新。每次更新取最大值。
  • 当 ii 的得分确定后，它的贡献 score(i)+weight(i,j)score(i) + weight(i,j) 被推送给后续锚点 jj。
  • 虽然 ii 仍然需要顺序计算（因为 score(i)score(i) 依赖更早的锚点），但推送和更新操作可以流水线化，不需要等待 jj 的最终结果。
  • 最终 score(j)score(j) 会收敛到与原始公式相同的结果（如果 NN 足够大且权重函数对称）。

并行性：在硬件上，可以设计成 systolic 流水线：每个周期处理一个 ii，它的得分沿着 PE 阵列向后传播，后面的 PE 依次更新自己的 score(j)score(j)。这正是 GenDP 的 1D DP 表映射方式：多个 PE 组成大阵列，FIFO 传递依赖数据。

4. 权重函数 weight(i,j)weight(i, j) 的含义​

虽然论文未展开，但典型 Chain 算法中，weight(i,j)weight(i,j) 通常定义为：

weight(i,j)=min⁡(yj−yi, xj−xi)−gap penaltyweight(i, j) = \min(y_j - y_i,\ x_j - x_i) - \text{gap penalty}

或类似形式，用于奖励两个锚点之间的一致距离，并惩罚过大的 gap。具体取决于实现（如 Minimap2）。在重排序中，为了并行性，NN 从默认的 25 增加到 64，导致计算量增加。论文指出实际计算了约 3.72×3.72\times 更多的单元格，但换来了高度并行。

5. 重排序的代价与精度​

  • 计算量增加：原始 N=25N=25，重排序 N=64N=64，理论比较次数比 64/25=2.5664/25 = 2.56，加上填充、同步等开销，实际为 3.72×3.72\times。论文在评估时将 GPU 和 GenDP 的吞吐率除以 3.723.72 进行归一化。
  • 精度：论文 Table 6 显示，重排序 Chain（N=64N=64）与原始 Minimap2 的映射失败率和 Phred 质量分数几乎相同，精度损失可忽略。

6. 在 GenDP 中的实现​

GenDP 的 DPAx 架构将 1D DP 表映射到大型 PE 阵列（最多 64 个 PE）。工作方式：

  1. 锚点按顺序映射到 PE。
  2. 当锚点 ii 的得分计算完成，它被加载到 FIFO。
  3. FIFO 将得分依次传递给后面的 PE。
  4. 每个 PE 用 score(i)+weight(i,j)score(i) + weight(i,j) 更新自己的 score(j)score(j)。
  5. 数据在 PE 之间向前流动，形成 systolic 流水线。

这样，虽然 ii 的顺序计算仍是串行的，但推送和更新完全流水线化，PE 阵列持续工作，达到高吞吐。论文 Table 11 显示 Chain 的 VLIW 利用率约 38.3%，Table 15 显示 GenDP 在 Chain 上相对 CPU 加速 63.7×，相对 GPU 加速 281.4×（已按 3.72× 归一化）。

7. 一句话总结​

Chain 的数学模型是一个一维 DP：

  • 原始：score(i)=max⁡{wi, max⁡j<i(score(j)+weight(j,i))}score(i) = \max\{ w_i,\ \max_{j < i} (score(j) + weight(j,i)) \}，串行依赖前 NN 个锚点。
  • 重排序：反转方向，score(j)=max⁡(score(j), score(i)+weight(i,j))score(j) = \max(score(j),\ score(i) + weight(i,j))，每个 ii 主动更新后续 NN 个锚点，实现流水线并行。
  • 重排序增加了计算量（NN 从 25 到 64，约 3.72×），但精度相当，且非常适合 GenDP 的 PE 阵列和 FIFO 架构。