基因组所阮珏、邵浩靖团队开发高效率DNA比对算法BSAlign

经典的动态规划算法，如史密斯-沃特曼算法和尼德曼-翁施算法，常用于处理序列比对，但由于其时间复杂度呈二次函数式增长，当序列长度增加时，算法的处理时间也随之变长，导致其在处理大规模序列比对时效率低下，严重阻碍了其在大规模序列比对中的应用。目前并行加速比对的最优算法有三种方法：通过增加数据并行度获得加速的条纹法；通过减少计算单元的字节数从而增加并行度的差分法；通过减少整体计算量获得加速的带宽法。然而，目前并没有任何方法可以高效地结合这三种方法，获得更快速的比对算法。

为此，研究人员提出了条纹移动法，该算法在带宽环境下实现了高效运算，并开发了主动F循环法，解决了条纹数据在长插入或删除情况下的多次查询问题。这一创新显著提高了比对速度。与现有并行算法相比，BSAlign比对算法的速度提升了2倍，在长序列比对方面，其效率较基于编辑距离的比对算法提高了1.5到4倍。

这种新方法不仅克服了传统方法的局限性，还在处理大规模数据时展示了卓越的性能。条纹移动法结合了数据并行度、计算单元优化和整体计算量减少的优点，显著提升了计算效率。主动F循环法则通过智能判断并计算条纹数据，进一步提高了处理速度和准确性。通过这些创新，BSAlign算法在多个实际应用中表现出色，包括基因组序列比对和其他需要高效大规模比对的领域，其显著的性能提升，使其成为大规模序列比对中的一种优越选择。

条纹移动算法原理

当两条DNA序列进行比对时，动态规划算法会构建一个比对矩阵，如图1a中的整个方形框。带宽法只计算与最优路径相关的单元，如图1a中的带颜色的单元，其余白色区域不计算。常规数据结构是把连续的数据整齐地放进寄存器（图1b），而条纹数据结构是把等间隔的数据整齐地放进寄存器（图1c）。对比常规数据结构，条纹数据结构在矩阵的迭代中保持很高的数据复用性，如图1c的（3，7，11，15）在4次迭代中均保持同样结构。因此本研究提出的条纹移动法大大减少了计算的复杂性。

图1 | 条纹移动算法

主动F循环算法原理

在条纹数据结构下，数据存在依赖关系，增加了计算的复杂性。例如第一个寄存器（0,4,8,12）里的8，精确的8单元的值是需要先计算4，5，6，7单元的值，而精确的4单元的值是需要先计算1，2，3单元的值。以前的解决方案是使用被动F循环，即通过多次循环，多次矫正以确保数据的准确性（图2a）。该研究提出主动F循环，即通过提前计算所有可能需要矫正的单元格，提前得出精确的初始值，实现只需要两次循环即可保证所有数据的准确性（图2b），再次减少计算的复杂性。

图2 | 主动F循环算法

BSAlign与其它序列比对算法的性能比较

本研究测试了真实数据和模拟数据，BSAlign在所有数据集均保持100%的准确率。在无带宽算法中，BSAlign比同类算法快1.5倍以上。在编辑距离的比对算法中，BSAlign比同类算法快2.1倍以上。在长插入或删除的长带宽比较中，BSAlign也优于同类算法。通过多种数据和多种方式的比较，均展示了BSAlign的优越性能，该研究达到此领域领先水平（表1）。

表1 | 各种比对算法的运算时间和准确性比较

中国农业科学院农业基因组研究所阮珏研究员为该论文通讯作者和共同第一作者，邵浩靖副研究员为该论文共同第一作者。

本研究得到了国家重点研发计划、国家自然科学基金、深圳市科技创新委员会和中国农业科学院科技创新工程的资助与支持。

原文链接：https://academic.oup.com/gpb/advance-article/doi/10.1093/gpbjnl/qzae025/7628627

BSAlign软件免费开发使用：https://github.com/ruanjue/bsalign