基于关键字树的DNA多序列星比对算法  

An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree

作　　者：邹权[1] 郭茂祖[1] 王晓凯[1] 张涛涛[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《电子学报》2009年第8期1746-1750,共5页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60671011;No.60741001;No.60871092);黑龙江省杰出青年科学基金(No.JC200611);黑龙江省自然科学重点项目基金(No.ZJG0705)

摘　　要：在构建进化树、比较单体型序列等生物信息学研究中,需要比对多个相似程度很高的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.

关 键 词：多序列比对 星比对 关键字树 AHO-CORASICK算法 生物信息学 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]