基于优化BWT索引技术的序列比对算法研究  

Research on Sequence Alignment Algorithm Based on Optimized BWT Indexing Technique

作　　者：胡春玲 赵俊杰[2] 姚梦媛 高欢欢 朱艺杭 汪少鸿 Hu Chunling;Zhao Junjie;Yao Mengyuan;Gao Huanhuan;Zhu Yihang;Wang Shaohong(School of Artificial Intelligence and Big Data,Hefei University,Hefei 230031,China;School of Computer Science and Artificial Intelligence,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]合肥大学人工智能与大数据学院,安徽合肥230031 [2]郑州大学计算机与人工智能学院,河南郑州450001

出　　处：《南京师范大学学报（工程技术版）》2024年第4期37-45,共9页Journal of Nanjing Normal University(Engineering and Technology Edition)

基　　金：国家自然科学基金青年项目(62306100);安徽省教学研究重大项目(2023jyxm0558).

摘　　要：生物信息学中,大规模的生物基因序列比对是最重要的基础问题.针对主流的BWT(burrows-wheeler transform)索引技术的研究,提出一种新的多阶混合BWT索引方法MD-BWT(multi difference cover mod3 burrows-wheeler transform),根据待比对序列的长度,动态选取适合的多位索引查找.实验结果表明,改进后的方法可以有效减少序列比对算法中的比对次数和计算次数,降低序列比对算法中索引算法的时间复杂度,明显提高序列比对的效率.在构造BWT(S)字符串过程中,通过DC3(difference cover mod 3)算法来构造后缀数组,实验表明DC3算法构造后缀数组比倍增算法的时间复杂度更低,时间性能更优.Large-scale gene sequence alignment is the most important fundamental problem in bioinformatics.Based on the mainstream research of BWT index technology,the paper proposes a new multi-order mixed BWT index method,which dynamically selects the appropiate multi-bit indexing according to the length of the sequence to be compared.The experimental results show that the improved method can effectively reduce the number of comparison and calculation times,reduce the time complexity of the index algorithm,and significantly improve the efficiency of sequence comparison.In the process of constructing BWT(S)string,this paper uses DC3(difference cover mod 3)algorithm to construct the suffix array.Experiments show that DC3 algorithm has better time performance compared to Binary Lifting.

关 键 词：长序列比对 BWT索引 DC3 后缀数组 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]