近日，中国农业科学院深圳农业基因组研究所农业基因组学技术研发与应用创新团队提出DNA比对新算法，并研发出DNA比对软件“BSAlign”。相比同类并行算法，新算法能够更快生成最优比对结果，且准确度更高。相关研究成果发表在《基因组蛋白质组与生物信息学报（Genomics, Proteomics & Bioinformatics）》上。
经典的动态规划算法，如史密斯-沃特曼算法和尼德曼-翁施算法，常用于处理序列比对，但由于其时间复杂度呈二次函数式增长，当序列长度增加时，算法的处理时间也随之变长，导致其在处理大规模序列比对时效率低下，严重阻碍了其应用。
为此，研究人员提出了一种新的DNA序列对比算法——条纹移动法，该算法能够在带宽环境下实现高效运算。经测试，与现有并行算法相比，BSAlign算法的速度提升了2倍，在长序列比对方面，其效率较基于编辑距离的比对算法提高了1.5到4倍，在带宽环境下实现了高效运算。此外，研究人员还进一步提出了主动F循环法，解决了条纹数据在长插入或删除情况下的多次查询问题，进一步提高了处理速度和准确性。
该研究得到了国家重点研发计划、国家自然科学基金、中国农业科学院科技创新工程等项目的资助。（通讯员 马昕怡）
原文链接：https://academic.oup.com/gpb/advance-article/doi/10.1093/gpbjnl/qzae025/7628627
