Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm

doi:10.1360/02yf0362

	Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm
	Zhang, F ; Qiao, XZ ; Liu, ZY
	2004-04-01
发表期刊	SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES
ISSN	1009-2757
卷号	47 期号:2 页码:221-231
摘要	Tools for pair-wise bio-sequence alignment have for long played a central role in computation biology. Several algorithms for bio-sequence alignment have been developed. The Smith-Waterman algorithm, based on dynamic programming, is considered the most fundamental alignment algorithm in bioinformatics. However the existing parallel Smith-Waterman algorithm needs large memory space, and this disadvantage limits the size of a sequence to be handled. As the data of biological sequences expand rapidly, the memory requirement of the existing parallel SmithWaterman algorithm has become a critical problem. For solving this problem, we develop a new parallel bio-sequence alignment algorithm, using the strategy of divide and conquer, named PSW-DC algorithm. In our algorithm, first, we partition the query sequence into several subsequences and distribute them to every processor respectively, then compare each subsequence with the whole subject sequence in parallel, using the Smith-Waterman algorithm, and get an interim result, finally obtain the optimal alignment between the query sequence and subject sequence, through the special combination and extension method. Memory space required in our algorithm is reduced significantly in comparison with existing ones. We also develop a key technique of combination and extension, named the C&E method, to manipulate the interim results and obtain the final sequences alignment. We implement the new parallel bio-sequences alignment algorithm, the PSW-DC, in a cluster parallel system.
关键词	biological sequence alignment dynamic programming divide and conquer parallel
DOI	10.1360/02yf0362
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000221118000007
出版者	SCIENCE CHINA PRESS
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13839
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, F
作者单位	1.Chinese Acad Sci, Comp Technol Inst, Beijing 100080, Peoples R China 2.Natl Nat Sci Fdn China, Beijing 100083, Peoples R China
推荐引用方式 GB/T 7714	Zhang, F,Qiao, XZ,Liu, ZY. Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm[J]. SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES,2004,47(2):221-231.
APA	Zhang, F,Qiao, XZ,&Liu, ZY.(2004).Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm.SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES,47(2),221-231.
MLA	Zhang, F,et al."Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm".SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES 47.2(2004):221-231.