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

李昭; 杨琪; 祝明发

首页> 中文期刊> 《微电子学与计算机》 >存储约束条件下的序列联配算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《微电子学与计算机》 |2002年第6期|1-5|共5页
作者
李昭; 杨琪; 祝明发;
展开▼
作者单位

中国科学院计算技术研究所;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;生物信息论;
关键词
存储约束条件; 序列联配算法; 生物信息处理; Hirschberg算法; 动态规划算法; 线性空间; 计算机;

相似文献

中文文献
外文文献
专利

1. 针对图像序列的快速低存储开销配准算法 [J] . 吴明军 ,周桢 ,赵亮亮 . 强激光与粒子束 . 2012,第005期
2. 一种实现偏序约束条件下的序列模式挖掘算法 [J] . 任家东 ,宗俊省 ,李志国 . 计算机工程与科学 . 2007,第005期
3. 新型粒子群优化算法在多序列联配中的应用 [J] . 胡桂武 . 生物信息学 . 2008,第001期
4. 基于免疫粒子群优化算法集成的多序列联配 [J] . 陈蔼详 ,张昕 ,胡桂武 . 湖南税务高等专科学校学报 . 2008,第002期
5. 一种基于极值思想的多序列联配求精算法 [J] . 邓伟林 ,胡桂武 ,郑启伦 . 计算机工程 . 2006,第002期
6. 生物序列局部联配中的马赛克问题的一种解决方法 [C] . 黄均才 ,佘堃 ,周明天 . 2003中国计算机大会 . 2003
7. 序列及序列二级结构联配问题的若干算法研究 [A] . 张西洋 . 2015

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

摘要

著录项

相似文献

相关主题

期刊订阅