Optimizing performance, cost, and sensitivity in pairwise sequence search on a cluster of PlayStations
Ashwin M. Aji, Wu-chun Feng · 2008
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 algorithmic 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.