Go to the content. | Move to the navigation | Go to the site search | Go to the menu | Contacts | Accessibility

| Create Account

Manavski, Svetlin A and Valle, Giorgio (2008) CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. [Online journal papers]

Full text disponibile come:

[img]
Preview
Documento PDF
720Kb

Per gentile concessione di: http://www.biomedcentral.com/1471-2105/9/S2/S10

Abstract (english)

Background

Searching for similarities in protein and DNA databases has become a routine procedure in Molecular Biology. The Smith-Waterman algorithm has been available for more than 25 years. It is based on a dynamic programming approach that explores all the possible alignments between two sequences; as a result it returns the optimal local alignment. Unfortunately, the computational cost is very high, requiring a number of operations proportional to the product of the length of two sequences. Furthermore, the exponential growth of protein and DNA databases makes the Smith-Waterman algorithm unrealistic for searching similarities in large sets of sequences. For these reasons heuristic approaches such as those implemented in FASTA and BLAST tend to be preferred, allowing faster execution times at the cost of reduced sensitivity. The main motivation of our work is to exploit the huge computational power of commonly available graphic cards, to develop high performance solutions for sequence alignment.

Results

In this paper we present what we believe is the fastest solution of the exact Smith-Waterman algorithm running on commodity hardware. It is implemented in the recently released CUDA programming environment by NVidia. CUDA allows direct access to the hardware primitives of the last-generation Graphics Processing Units (GPU) G80. Speeds of more than 3.5 GCUPS (Giga Cell Updates Per Second) are achieved on a workstation running two GeForce 8800 GTX. Exhaustive tests have been done to compare our implementation to SSEARCH and BLAST, running on a 3 GHz Intel Pentium IV processor. Our solution was also compared to a recently published GPU implementation and to a Single Instruction Multiple Data (SIMD) solution. These tests show that our implementation performs from 2 to 30 times faster than any other previous attempt available on commodity hardware.

Conclusions

The results show that graphic cards are now sufficiently advanced to be used as efficient hardware accelerators for sequence alignment. Their performance is better than any alternative available on commodity hardware platforms. The solution presented in this paper allows large scale alignments to be performed at low cost, using the exact Smith-Waterman algorithm instead of the largely adopted heuristic approaches.


Statistiche Download
EPrint type:Online journal papers
Anno di Pubblicazione:2008
Key Words:CUDA, Molecular Biology, bioinformatics
Settori scientifico-disciplinari MIUR:Area 05 - Scienze biologiche > BIO/13 Biologia applicata
Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura di riferimento:Dipartimenti > Dipartimento di Biologia
Codice ID:1166
Depositato il:09 Dec 2008
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record