Streaming Algorithms for Biological Sequence Alignment on GPUs
- 13 August 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 18 (9), 1270-1281
- https://doi.org/10.1109/tpds.2007.1069
Abstract
Sequence alignment is a common and often repeated task in molecular biology. Typical alignment operations consist of finding similarities between a pair of sequences (pairwise sequence alignment) or a family of sequences (multiple sequence alignment). The need for speeding up this treatment comes from the rapid growth rate of biological sequence databases: every year their size increases by a factor of 1.5 to 2. In this paper, we present a new approach to high-performance biological sequence alignment based on commodity PC graphics hardware. Using modern graphics processing units (GPUs) for high-performance computing is facilitated by their enhanced programmability and motivated by their attractive price/performance ratio and incredible growth in speed. To derive an efficient mapping onto this type of architecture, we have reformulated dynamic-programming-based alignment algorithms as streaming algorithms in terms of computer graphics primitives. Our experimental results show that the GPU-based approach allows speedups of more than one order of magnitude with respect to optimized CPU implementations.Keywords
This publication has 27 references indexed in Scilit:
- Parallel Pattern-Based Systems for Computational Biology: A Case StudyIEEE Transactions on Parallel and Distributed Systems, 2006
- The UCSC Kestrel parallel processorIEEE Transactions on Parallel and Distributed Systems, 2005
- Space and time optimal parallel sequence alignmentsIEEE Transactions on Parallel and Distributed Systems, 2004
- Computational biology and high-performance computingCommunications of the ACM, 2004
- Brook for GPUsPublished by Association for Computing Machinery (ACM) ,2004
- CgACM Transactions on Graphics, 2003
- ParAlign: a parallel sequence alignment algorithm for rapid and sensitive database searchesNucleic Acids Research, 2001
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choiceNucleic Acids Research, 1994
- [5] Rapid and sensitive sequence comparison with FASTP and FASTAMethods in enzymology, 1990
- Progressive sequence alignment as a prerequisitetto correct phylogenetic treesJournal of Molecular Evolution, 1987