摘要
在构建进化树、比较单体型序列等生物信息学研究中,需要比对多个相似程度很高的DNA序列.对于数量多、序列长的多序列比对问题,通常使用时间复杂度较低的星比对算法.然而在处理大规模数据时,星比对的平方时间复杂度依然不能满足需要.因此,在星比对思想的基础上,本文结合关键字树理论,先找出完全匹配的区域,然后比对剩余区域,以达到降低期望时间复杂度的目的.两组实验证明了本文算法的有效性,在取得相同比对效果的情况下,本文算法运行时间小于其他方法.
Multiple sequence alignment is necessary and important for reconstructing evolutionary trees and comparing haplotype sequences. Center star method is always used to deal with lots of long sequences. However, square time complexity is a bottleneck for large data. In this paper, we propose a novel keyword tree based algorithm for improving the center star method. Aho-Corasick algorithm is employed to match a set of substrings and the rest regions are aligned by dynamic programming. Experiments show that the improved method rims faster than the initial center star method and clustalx.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2009年第8期1746-1750,共5页
Acta Electronica Sinica
基金
国家自然科学基金(No.60671011
No.60741001
No.60871092)
黑龙江省杰出青年科学基金(No.JC200611)
黑龙江省自然科学重点项目基金(No.ZJG0705)
