Fine-grained parallel implementations for SWAMP+ Smith-Waterman alignment

摘要

More sensitive than heuristic methods for searching biological databases, the Smith-Waterman algorithm is widely used but has the drawback of a high quadratic running time. The faster approach extends Smith-Waterman using Associative Massive Parallelism (SWAMP+) for three different parallel architectures: Associative Computing (ASC), the ClearSpeed coprocessor, and the Convey Computer FPGA coprocessor. We show that parallel versions of Smith-Waterman can be successfully modified to produce multiple BLAST-like sub-alignments while maintaining the original precision. SWAMP+ combines parallelism and the novel extension producing multiple sub-alignments for pairwise comparisons. Two parallel SWAMP+ implementations for the ASC model and the ClearSpeed CSX-620 use a wavefront approach. Both perform a full traceback in parallel memory, returning multiple sub-alignments. Results show a linear speedup for the 96 processing elements (PEs) on a single ClearSpeed chip. The third SWAMP+ adaptation uses the non-associative Convey Computer FPGA coprocessor. The hybrid system has a Smith-Waterman algorithm suite designed to produce high-speed, high-throughput alignments, optimized for large databases. The Convey Computer Smith-Waterman algorithm suite was extended to produce the additional SWAMP+ sub-alignments efficiently. The parallel sequence alignment algorithms were designed for three different computer systems, all of which contain extensions to produce multiple, additional sub-alignments. This work creates a speedup while providing a deeper exploration of the matched query sequences previously unavailable.