基于Profile比对的改进星比对算法

Improved Center Star Alignment Algorithm Based on Profile Alignment

多序列比对在序列分析研究中起着重要的作用,包括功能重要位点的识别和系统发育分析等问题。目前大多数比对软件都使用渐进比对或迭代比对的策略,但两种策略都具有较高的时间复杂度,因此难以处理长序列和大规模序列的比对问题。而星比对虽然具有很低的时间复杂度,但精度并不理想,目前只适用于相似度非常高的序列。针对此问题,引进了渐进比对中的profile比对来改进星比对算法的精度,同时避免大幅度地增加星比对的时间复杂度。最后,通过实验证明了改进的星比对算法可以有效地提高比对的精度。

Multiple sequence alignment plays an important role in sequence analysis,including identification of functionally important sites and phylogenetic analysis.At present,most alignment software uses the strategy of progressive alignment or iterative alignment,but both strategies have high time complexity,so it is difficult to deal with the alignment problem of long sequence and large datasets.Although star alignment has a very low time complexity,the accuracy of star alignment is not ideal,so it only applies to sequences with very high similarity.To solve this problem,we introduce profile alignment in progressive alignment to improve the accuracy of star alignment algorithm and avoid significantly increasing the time complexity of star alignment.Experiments show that the improved star alignment algorithm can effectively improve the accuracy of the alignment.