Skip to main content

WFAA wavefront

在 TALCO-WFAA 中，每个 tile 内参与计算的 read sequence 和 reference sequence 片段长度通常不相等，也不是按序列等长切分的。

原因在于 TALCO 的 tiling 不是把两条序列简单切成同样长的片段，而是沿着 WFA-Adapt 的三角矩阵波前推进。每个 tile 覆盖的是 DP 矩阵中的一部分，具体消耗多少 read 和 reference 碱基，取决于该 tile 内对角线 kk 的范围和 offset。

1. WFA-Adapt 的坐标关系​

  • 对角线定义：k=i−jk = i - j，其中 ii 是 reference 的位置，jj 是 read 的位置。
  • 某个 cell 的 offset 就是 ii，而 j=i−kj = i - k。
  • 所以同一个 tile 内，不同对角线上的 cell 对应的 ii 和 jj 范围不同。

在一个 tile 中，对角线 kk 的范围是 [kmin⁡,kmax⁡][k_{\min}, k_{\max}]。对于每条对角线，最远到达的 ii 由 offset 决定，对应的 j=i−kj = i - k。

因此：

  • reference 消耗的碱基数大约由 ii 的范围决定；
  • read 消耗的碱基数大约由 jj 的范围决定；
  • 由于 kk 通常不为 0，ii 和 jj 的范围一般不同，所以两个片段长度不相等。

2. 全局比对中 read 和 reference 长度本身就不同​

TALCO-WFAA 默认执行全局比对，从 (0,0)(0,0) 到 (m,n)(m,n)。其中：

  • mm 是 reference 长度；
  • nn 是 read 长度。

论文实验中，read 长度是 10–100 Kbp，reference 是对应的参考区域，长度与 read 大致相当但不完全相等。所以整体上两条序列长度就不同。

在 tiling 后，每个 tile 只是这个全局比对的一小段，read 和 reference 片段长度自然也不相等。

3. 硬件中序列片段的存储​

TALCO-WFAA 的每个 extend 和 compute 模块都有一对 SRAM 存储 query（read）和 reference 序列。由于访问模式不规则，这些 SRAM 中存的是当前 tile 所需的序列片段，而不是整条长序列。

论文给出的 SRAM 配置是 16x(32KB + 16x2KB + 1KB)，其中 32KB 用于存储序列片段。这个容量足够容纳一个 tile 内所需的 read 和 reference 碱基，但 read 和 reference 片段长度不一定相同，硬件会根据实际需要读取相应数量的碱基。

4. 总结​

  • 不一定一样长。
  • TALCO-WFAA 的 tile 是按 DP 矩阵的波前推进划分的，不是按序列等长切分。
  • 每个 tile 内，read 和 reference 消耗的碱基数由对角线 kk 和 offset 决定，通常不相等。
  • 整体上，read 和 reference 长度也可能不同，全局比对的目标就是从 (0,0)(0,0) 到 (m,n)(m,n)，所以每个 tile 处理的片段长度自然不同。

下面从三个角度回答你的问题：序列长度、静态存储位置、比对范围。

1. 参考序列和读段序列的长度​

论文实验设置（Section V）：

  • 读段（read / query）：使用 PBSIM2 模拟长读段，长度分别为 10 Kbp、20 Kbp、50 Kbp、100 Kbp，错误率 1%–30%。
  • 参考序列（reference）：从人类基因组 GRCh38 的 1–22、X、Y 染色体中，由 PBSIM2 提供与每个读段对齐的对应子区域。因此参考序列长度与读段长度大致相当，可能略长或略短（因为读段可能有插入/删除），但量级相同，也是 10–100 Kbp 级别。

在硬件加速器中，由于 TALCO 采用 tiling，片上内存只保留当前 tile 所需的序列片段，所以序列总长度不影响片上内存，只影响 tile 数量和总计算时间。

2. 哪些是静态存在于 PE 中的？​

TALCO-XDrop​

图 7 的 systolic PE 阵列中：

  • PE 阵列沿**查询序列（read）**的维度展开，每个 PE 固定负责查询序列的一个碱基（或一小段）。
  • 查询序列的碱基以 3 bits/碱基的形式存在每个 PE 的局部寄存器/SRAM 中，可以看作静态绑定在 PE 上。
  • 参考序列则通过 FIFO / 广播路径流式输入，依次经过各个 PE。
  • 图 7b 显示“Query blocking”：查询序列被分成块，每块对应一组 PE，所以并不是整个读段静态存在，而是当前 tile 对应的查询片段静态在 PE 中。

TALCO-WFAA​

图 8 的架构中：

  • 由于 WFA-Adapt 的访问模式不规则，每个 extend 模块和 compute 模块都配有一对 SRAM，分别存储查询序列和参考序列的片段。
  • 序列不是静态绑定在 PE 内部，而是存在每个模块的 SRAM 中，按需读取。
  • 同样，片上只保留当前 tile 所需的序列片段，整个长读段会被分块处理。

总结：

  • TALCO-XDrop：查询序列片段静态在 PE 中，参考序列流式通过。
  • TALCO-WFAA：查询和参考序列都存储在模块的 SRAM 中，不是静态在 PE 寄存器里。
  • 两者都只保留当前 tile 的序列片段，不是整条长序列。

3. 两者是从起点对比到参考序列的终点吗？​

TALCO-WFAA​

  • 底层算法是 WFA-Adapt，默认执行全局比对：从起点 (0,0)(0,0) 到终点 (m,n)(m,n)，其中 mm 是参考序列长度，nn 是查询序列长度。
  • 所以 TALCO-WFAA 是从起点比对到参考序列的终点（同时也是查询序列的终点）。

TALCO-XDrop​

  • 底层算法是 X-Drop，X-Drop 本身可以用于全局、半全局或局部比对，取决于具体实现和终止条件。
  • 论文中 TALCO-XDrop 与 Libgaba 比较，Libgaba 执行的是 semi-global alignment with X-Drop termination：
    • 通常从查询序列的一端开始，到查询序列的另一端结束；
    • 参考序列可以有多余的未比对部分（即不需要到达参考序列的终点）。
  • 因此 TALCO-XDrop 在论文中不一定比对到参考序列的终点，而是到查询序列的终点，具体取决于底层 X-Drop 的配置。
  • 但 TALCO 算法本身通过 Clast 支持全局和局部：
    • 全局比对：Clast = (m,n)；
    • 局部比对：Clast 为最大分格子。
    • 所以 TALCO-XDrop 可以根据底层算法选择是否比对到参考终点。

总结：

  • TALCO-WFAA：全局比对，从起点到参考序列终点。
  • TALCO-XDrop：semi-global（论文中），从起点到查询序列终点，参考序列不一定到终点；也可配置为全局或局部。