SCALABLE PARALLEL SMITH-WATERMAN ALGORITHMS

摘要

Pair-wise bio-sequence alignment is one of the most important tasks in computational biology. The dynamic programming based 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 concerned 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 another 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 sensitivity. The algorithm was implemented and experiments were designed. The results show that the grid method brings good sensitivity and speedup.