Optimizing Performance, Cost, and Sensitivity in Pairwise Sequence Search on a Cluster of PlayStations

Abstract—The Smith-Waterman algorithm is a dynamic programming method for determining optimal local alignments between nucleotide or protein sequences. However, it suffers from quadratic time and space complexity. As a result, many al-gorithmic and architectural enhancements have been proposed to solve this problem, but at the cost of reduced sensitivity in the algorithms or significant expense in hardware, respectively. This paper presents a highly efficient parallelization of the Smith-Waterman algorithm on the Cell Broadband Engine platform, a novel hybrid multicore architecture that drives the low-cost PlayStation 3 (PS3) game consoles as well as the IBM BladeCenter Q22, which currently powers the fastest super-computer in the world, Roadrunner at Los Alamos National Laboratory. Through an innovative mapping of the optimal Smith-Waterman algorithm onto a cluster of PlayStation 3 nodes, our implementation delivers 21 to 55-fold speed-up over a high-end multicore architecture and up to 449-fold speed-up over the PowerPC processor in the PS3. Next, we evaluate the trade-offs between our Smith-Waterman implementation on the Cell with existing software and hardware implementations and show that our solution achieves the best performance-to-price ratio, when aligning realistic sequences sizes and generating the actual alignment. Finally, we show that our low-cost solution on a PS3 cluster approaches the speed of BLAST while achieving ideal sensitiv-ity. To quantify the relationship between the two algorithms in terms of speed and sensitivity, we formally define and quantify the sensitivity of homology search methods so that trade-offs between sequence-search solutions can be evaluated in a quantitative manner. I