基于Smith-Waterman算法的并行分而治之生物序列比对算法

	基于Smith-Waterman算法的并行分而治之生物序列比对算法
	乔香珍 1; 刘志勇 2; 张法 1
	2004
发表期刊	中国科学：E辑
ISSN	1006-9275
卷号	34.0 期号:002 页码:190
摘要	生物序列比对是生物信息学中最常见的问题之一，基于动态规划思想的Smith-Waterman算法是序列比对中最基本的算法．然而现有的并行Smith—Waterman算法都需要庞大的内存，且无法处理大规模的数据串，随着生物数据的急剧增长，这些并行算法对内存空间的需求已成为需要迫切解决的问题．由此提出一种并行生物序列比对算法，PSW—DC算法，该算法采用分而治之的方法把query序列划分为若干片段，并分配给相应的各个处理器，而后并行地按Smith-Waterman算法与目标(subject)序列进行比对，再通过按一定规则的扩展过程求取序列的优化匹配．与其他并行算法相比，该算法有效地降低了内存空间的需求，并实现了对大规模数据串的并行处理．为实现该算法，给出了一种称作C&E的拓展规则及实现方法．且该方法已经在实际系统中得到实现．
关键词	Smith-Waterman算法生物序列比对动态规划分而治之并行处理内存空间
语种	英语
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/36608
专题	中国科学院计算技术研究所期刊论文_中文
作者单位	1.中国科学院计算技术研究所 2.国家自然科学基金委员会
第一作者单位	中国科学院计算技术研究所
推荐引用方式 GB/T 7714	乔香珍,刘志勇,张法. 基于Smith-Waterman算法的并行分而治之生物序列比对算法[J]. 中国科学：E辑,2004,34.0(002):190.
APA	乔香珍,刘志勇,&张法.(2004).基于Smith-Waterman算法的并行分而治之生物序列比对算法.中国科学：E辑,34.0(002),190.
MLA	乔香珍,et al."基于Smith-Waterman算法的并行分而治之生物序列比对算法".中国科学：E辑 34.0.002(2004):190.