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

• 作者: 张涛涛 王晓凯 邹权 郭茂祖
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 多序列比对 星比对 关键字树 Aho-Corasick算法 生物信息学
• 年，卷（期）: 2009,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 1746-1750
• 页数: 5页
• 分类号: TP301
• 字数: 5629字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2009.08.021

摘要

在构建进化树、比较单体型序列等生物信息学研究中,需要比对多个相似程度很高的DNA序列.对于数量多、序列长的多序列比对问题,通常使用时间复杂度较低的星比对算法.然而在处理大规模数据时,星比对的平方时间复杂度依然不能满足需要.因此,在星比对思想的基础上,本文结合关键字树理论,先找出完全匹配的区域,然后比对剩余区域,以达到降低期望时间复杂度的目的.两组实验证明了本文算法的有效性,在取得相同比对效果的情况下,本文算法运行时间小于其他方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭茂祖	哈尔滨工业大学计算机科学与技术学院	77	1227	20.0	33.0
2	邹权	哈尔滨工业大学计算机科学与技术学院	7	125	4.0	7.0
3	张涛涛	哈尔滨工业大学计算机科学与技术学院	3	77	3.0	3.0
4	王晓凯	哈尔滨工业大学计算机科学与技术学院	1	17	1.0	1.0