基于偏序图生成共识序列的改进星比对算法  

An Improved Star Alignment Algorithm for Generating Consistent Sequences Based on Partial Order Graphs

作　　者：胡振铎 刘宇暄 朱晓 HU Zhenduo;LIU yuxuan;ZHU Xiao(School of Computer Science and Information Engineering,Harbin Normal University,Harbin Heilongjiang 150500,China)

机构地区：[1]哈尔滨师范大学计算机科学与信息工程学院,黑龙江哈尔滨150500

出　　处：《长江信息通信》2023年第1期1-4,共4页Changjiang Information & Communications

基　　金：国家自然科学基金资助项目(61902094);黑龙江省自然科学基金项目(QC2018082);黑龙江省普通本科高等学校青年创新人才培养计划项目(UNPYSCT-2018183)。

摘　　要：多序列比对是生物信息学中十分常用的序列分析方法,主要用于分析分子进化关系、基因组分析、找出DNA序列之间的共同结构特征,从而准确判断序列结构和功能之间的具体联系。现今广泛使用的多序列比对方法主要分为渐进式比对和迭代式比对两种方式,但这两种方式在进行多序列比对时的时间开销相对较大,且比对结果准确性和复杂度受限于待比对序列的质量和相似度。相对来说,星比对算法的时间复杂度更低,常用于高相似度序列之间的比对。但对低相似度序列进行比对时,其结果精度还有待提高。针对星比对算法在低相似度序列中精度较差问题,文章提出了利用偏序图生成的共识序列对星比对算法进行了优化,结合SIMD并行策略加快共识序列的产生,从而扩大了算法的应用范围,提高了比对结果准确度,该研究最后通过实验证明了算法优化的有效性。Multi sequence alignment is a very common sequence analysis method in bioinformatics,which is mainly used to analyze the molecular evolutionary relationship,genome analysis,find out the common structural characteristics between DNA sequences,and accurately judge the specific relationship between sequence structure and function.The multiple sequence alignment methods widely used today are mainly divided into progressive alignment and iterative alignment.However,the time cost of these two methods in multiple sequence alignment is relatively large,and the accuracy and complexity of the alignment results are limited by the quality and similarity of the sequences to be compared.Relatively speaking,the time complexity of star alignment algorithm is lower,and it is often used for alignment between high similarity sequences.However,the accuracy of the results of low similarity sequence alignment needs to be improved.To solve the problem of poor accuracy of star alignment algorithm in low similarity sequences,the paper proposes to optimize the star alignment algorithm by using consensus sequences generated by partial sequence diagrams,and speed up the generation of consensus sequences by combining SIMD parallel strategy,thus expanding the application scope of the algorithm and improving the accuracy of the alignment results.Finally,the research proves the effectiveness of algorithm optimization through experiments.

关 键 词：多序列比对 星比对算法 偏序图 共识序列 SIMD 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]