Parallel divide and conquer bio-sequence comparison based on Smith-Waterman algorithm
文献类型：期刊论文
| 作者 | Zhang, F; Qiao, XZ; Liu, ZY |
| 刊名 | SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES
 |
| 出版日期 | 2004-04-01 |
| 卷号 | 47期号:2页码:221-231 |
| 关键词 | biological sequence alignment dynamic programming divide and conquer parallel |
| ISSN号 | 1009-2757 |
| DOI | 10.1360/02yf0362 |
| 英文摘要 | 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. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000221118000007 |
| 出版者 | SCIENCE CHINA PRESS |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/13838]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。