存储约束条件下的序列联配算法

• 作者: 李昭 杨琪 祝明发
• 来源期刊: 微电子学与计算机
• 关键词: 生物信息处理 序列联配 Hirschberg算法 动态规划算法 线性空间
• 年，卷（期）: 2002,（6）
• 所属期刊栏目: 软件与算法
• 页码范围: 1-5
• 页数: 5页
• 分类号: TP3
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7180.2002.06.001

摘要

序列联配算法是生物信息处理中非常重要的一类算法,最基本的序列联配算法是动态规划算法,其时间和空间复杂度都为O(m×n),(其中m和n为两序列的长度).实际应用中,该算法的空间复杂度是限制问题规模的瓶颈.Hirschberg在1975年提出的算法减少了序列联配问题的空间需求,其空间复杂度为O(m+n),但是Hirschberg算法的时间需求是基本动态规划算法的两倍.文章提出一种新的序列联配算法Fast Alignment(FA),FA算法的时间复杂度和空间复杂度介于基本动态规划算法和Hirschberg算法之间,通过对算法参数k的调节,可以获得在不同存储条件下最小序列联配问题解决时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	祝明发	中国科学院计算技术研究所	21	422	8.0	20.0
2	杨琪	中国科学院计算技术研究所	7	17	1.0	4.0
3	李昭	中国科学院计算技术研究所	5	17	2.0	4.0