| 基于关键字树的DNA多序列星比对算法 |
| |
| 引用本文： | 邹权,郭茂祖,王晓凯,张涛涛. 基于关键字树的DNA多序列星比对算法[J]. 电子学报, 2009, 37(8): 1746-1750 |
| |
| 作者姓名： | 邹权 郭茂祖 王晓凯 张涛涛 |
| |
| 作者单位： | 哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨,150001 |
| |
| 基金项目： | 国家自然科学基金(No.60671011,No.60741001,No.60871092);;黑龙江省杰出青年科学基金(No.JC200611);;黑龙江省自然科学重点项目基金(No.ZJG0705) |
| |
| 摘 要： | 在构建进化树、比较单体型序列等生物信息学研究中,需要比对多个相似程度很高的DNA序列.对于数量多、序列长的多序列比对问题,通常使用时间复杂度较低的星比对算法.然而在处理大规模数据时,星比对的平方时间复杂度依然不能满足需要.因此,在星比对思想的基础上,本文结合关键字树理论,先找出完全匹配的区域,然后比对剩余区域,以达到降低期望时间复杂度的目的.两组实验证明了本文算法的有效性,在取得相同比对效果的情况下,本文算法运行时间小于其他方法.
|
| 关 键 词： | 多序列比对 星比对 关键字树 Aho-Corasick算法 生物信息学 |
| 收稿时间： | 2007-07-09 |
An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree |
| |
| ZOU Quan,GUO Mao-zu,WANG Xiao-kai,ZHANG Tao-tao. An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree[J]. Acta Electronica Sinica, 2009, 37(8): 1746-1750 |
| |
| Authors: | ZOU Quan GUO Mao-zu WANG Xiao-kai ZHANG Tao-tao |
| |
| Affiliation: | School of Computer Science and Technology;Harbin Institute of Technology;Harbin;Heilongjiang 150001;China |
| |
| Abstract: | 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... |
| |
| Keywords: | multiple sequence alignment center star method keyword tree Aho-Corasick algorilhm bioinformatics |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载免费的PDF全文 |
|
