序列比对算法BWA的优化  

Optimization of sequence alignment algorithm BWA

作　　者：胡爽 陈长波[1,3] Hu Shuang;Chen Changbo(Chongqing Key Laboratory of Secure Computing for Biology,Chongqing Institute of Green&Intelligent Technology,Chinese Academy of Sciences,Chongqing 400714,China;School of Computer Science&Technology,Chongqing University of Posts&Telecommunications,Chongqing 400065,China;Chongqing School,University of Chinese Academy of Sciences,Chongqing 400714,China)

机构地区：[1]中国科学院重庆绿色智能技术研究院生物计算安全重庆市重点实验院,重庆400714 [2]重庆邮电大学计算机科学与技术学院,重庆400065 [3]中国科学院大学重庆学院,重庆400714

出　　处：《计算机应用研究》2024年第12期3777-3785,共9页Application Research of Computers

基　　金：国家重点研发计划资助项目(2020YFA0712300);重庆英才计划青年拔尖项目(2021000263);重庆市院士牵头科技创新引导专项资助项目(cstc2021yszx-jcyjX0004,2022YSZX-JCX0011CSTB,CSTB2023YSZX-JCX0008)。

摘　　要：序列比对是基因组数据分析的关键一环,提高其比对效率对推动测序技术在医学、古生物学等领域的应用具有重要意义。针对BWA算法两大步骤之一的SAMSE存在冗余读取索引导致效率欠佳的问题,提出了新的算法BWA^(*)。其通过运用流程优化消除了SAMSE中参考序列及其索引的冗余读取,在此基础上叠加运用关键参数值调整和多线程优化等技术,进一步提高了计算效率。公开数据库中的真实序列测试表明,BWA^(*)的SAMSE步骤的性能是BWA中SAMSE性能的7.11~8.61倍,平均为7.84倍,BWA^(*)的整体性能是BWA的1.25~1.70倍,平均1.47倍。针对实际应用中的古代DNA序列比对,实验表明和另一常用工具BWA-MEM相比,优化后的BWA^(*)在继承原有BWA高精度特性的同时,实现了对BWA-MEM速度的超越。Sequence alignment is a critical component of genomic data analysis,and improving its efficiency is vital for advancing sequencing technology applications in medicine,paleobiology,and other fields.This paper addressed the inefficiency in the SAMSE step of the BWA algorithm,caused by redundant index reads,by proposing a new algorithm called BWA^(*).Through process optimization,BWA^(*)eliminated redundant reads of reference sequences and their indices in the SAMSE step.Additionally,the algorithm incorporated key parameter adjustments and multithreading optimizations to further enhance computational efficiency.Tests on real sequences from public databases show that the performance of BWA^(*)in the SAMSE step is 7.11 to 8.61 times that of BWA,with an average of 7.84 times.Overall,BWA^(*)achieves 1.25 to 1.70 times the perfor-mance of BWA,with an average of 1.47 times.In practical applications of ancient DNA sequence alignment,experiments demonstrate that the optimized BWA^(*)surpasses the speed of BWA-MEM while maintaining the high accuracy characteristic of the original BWA.

关 键 词：序列比对 罗伯斯-惠勒变换 第二代测序 BWA 古代DNA 

分 类 号：R857.3[医药卫生—航空、航天与航海医学]