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

邹 权; 郭茂祖; 王晓凯; 张涛涛

您当前的位置：

首页 >

文章列表页 >

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

论文 | 更新时间：2025-07-16

- 基于关键字树的DNA多序列星比对算法
- An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree
- 电子学报 2009年37卷第8期页码：1746-1750
- 作者机构：
  
  哈尔滨工业大学计算机科学与技术学院,黑龙江,哈尔滨,150001
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.60671011,No.60741001,No.60871092);黑龙江省杰出青年科学基金 (No.JC200611);黑龙江省自然科学重点项目基金 (No.ZJG0705)
- DOI：
  中图分类号： TP301
- 纸质出版：2009
- 稿件说明：
移动端阅览
邹权, 郭茂祖, 王晓凯, 等. 基于关键字树的DNA多序列星比对算法[J]. 电子学报, 2009,37(8):1746-1750.

ZOU Quan, GUO Mao-zu, WANG Xiao-kai, et al. An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree[J]. Acta Electronica Sinica, 2009, 37(8): 1746-1750.
邹权, 郭茂祖, 王晓凯, 等. 基于关键字树的DNA多序列星比对算法[J]. 电子学报, 2009,37(8):1746-1750. DOI：

ZOU Quan, GUO Mao-zu, WANG Xiao-kai, et al. An Algorithm for DNA Multiple Sequence Alignment Based on Center Star Method and Keyword Tree[J]. Acta Electronica Sinica, 2009, 37(8): 1746-1750. DOI：

摘要

在构建进化树、比较单体型序列等生物信息学研究中

需要比对多个相似程度很高的DNA序列.对于数量多、序列长的多序列比对问题

通常使用时间复杂度较低的星比对算法.然而在处理大规模数据时

星比对的平方时间复杂度依然不能满足需要.因此

在星比对思想的基础上

本文结合关键字树理论

先找出完全匹配的区域

然后比对剩余区域

以达到降低期望时间复杂度的目的.两组实验证明了本文算法的有效性

在取得相同比对效果的情况下

本文算法运行时间小于其他方法.

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 method runs faster than the initial center star method and clustalx.

关键词

Keywords

references

浏览量

1138

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

Analog-Cell:一种新的电子细胞图形模型

基于生物信息学特征的DNA序列数据压缩算法

基于随机复杂度约束的高维特征自动选择算法

DNA计算的研究进展

基于多Agent的生物信息数据整合系统-BioAgent1