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

多序列比对是生物信息学中十分常用的序列分析方法，主要用于分析分子进化关系、基因组分析、找出DNA序列之间的共同结构特征，从而准确判断序列结构和功能之间的具体联系。现今广泛使用的多序列比对方法主要分为渐进式比对和迭代式比对两种方式，但这两种方式在进行多序列比对时的时间开销相对较大，且比对结果准确性和复杂度受限于待比对序列的质量和相似度。相对来说，星比对算法的时间复杂度更低，常用于高相似度序列之间的比对。但对低相似度序列进行比对时，其结果精度还有待提高。针对星比对算法在低相似度序列中精度较差问题，文章提出了利用偏序图生成的共识序列对星比对算法进行了优化，结合SIMD并行策略加快共识序列的产生，从而扩大了算法的应用范围，提高了比对结果准确度，该研究最后通过实验证明了算法优化的有效性。