SCALABLE PARALLEL SMITH-WATERMAN ALGORITHMS
Pair-wise bio-sequence alignment is one of the most important tasks in computa-tional biology. The dynamic programming baaed Smith-Waterman algorithm is regarded as one of the most fundamental algorithms. Most of the existing parallel Smith-Waterman algorithm needs to hold the whole DP matrix, which is beyond the memory capacity of computers available when the length of sequences con-cerned is too long. Zhang et al. presented the PSW-DC algorithm, which can run with 1/p of the memory. However, the sensitivity of the PSW-DC algorithm decreases when the number of processors increases. In this paper, we presented an-other method to parallel the Smith-Waterman, the grid method. With this method, both the two sequences are portioned into pieces and mapped into the processors. Each processor runs the Smith-Waterman algorithm simultaneously and obtains interim optimal and suboptimal alignments. Then these interim results were used to generate the final results. The grid method achieves better sensitivity with the same number of processors or uses more processors with almost the same sensitiv-ity. The algorithm was implemented and experiments were designed. The results show that the grid method brings good sensitivity and speedup.
biological sequence alignment dynamic programming data partition
YU-GANG LI ZHI-YONG LIU
Beijing Institute of Technology, Beijing, China, 100081 Institute of Computing Technology, Chinese A Department of Information Sciences National Natural Science Foundation of China, Beijing, China, 100
国际会议
The Joint Conference of ICCP6 and CCP2003(第6届国际计算伦理会议)
北京
英文
338-342
2004-05-23（万方平台首次上网日期，不代表论文的发表时间）