High-throughput sequence alignment using Graphics Processing Units

By Michael C. Schatz, Cole Trapnell, Arthur L. Delcher, Amitabh Varshney. BMC Bioinformatics, 2007

347 citations recorded by the source corpus.

BackgroundThe recent availability of new, less expensive high-throughput DNA sequencing technologies has yielded a dramatic increase in the volume of sequence data that must be analyzed. These data are being generated for several purposes, including genotyping, genome resequencing, metagenomics, and de novo genome assembly projects. Sequence alignment programs such as MUMmer have proven essential for analysis of these data, but researchers will need ever faster, high-throughput alignment tools running on inexpensive hardware to keep up with new sequence technologies.ResultsThis paper describes MUMmerGPU, an open-source high-throughput parallel pairwise local sequence alignment program that runs on commodity Graphics Processing Units (GPUs) in common workstations. MUMmerGPU uses the new Compute Unified Device Architecture (CUDA) from nVidia to align multiple query sequences against a single reference sequence stored as a suffix tree. By processing the queries in parallel on the highly parallel graphics card, MUMmerGPU achieves more than a 10-fold speedup over a serial CPU version of the sequence alignment kernel, and outperforms the exact alignment component of MUMmer on a high end CPU by 3.5-fold in total application time when aligning reads from recent sequencing projects using Solexa/Illumina, 454, and Sanger sequencing technologies.ConclusionMUMmerGPU is a low cost, ultra-fast sequence alignment program designed to handle the increasing volume of data produced by new, high-throughput sequencing technologies. MUMmerGPU demonstrates that even memory-intensive applications can run significantly faster on the relatively low-cost GPU than on the CPU.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/e9adf1146dfb6c38bf36dcc8af116db6363076f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

A performance study of general-purpose applications on graphics processors using CUDA (2008, methodology): “Some important database operations have also been implemented on the GPU by using pixel engines [7], and a variety of other applications, such as sequence alignment [24] and AES encryption [30] have been successfully implemented on GPUs.”
Analyzing CUDA workloads using a detailed GPU simulator (2009, methodology): “We observed that with more concurrent CTAs, AES and MUM experience increased contention in the memory system resulting in 8.6 × and 5.4 × worse average memory latency, respectively comparing 200% resources vs. 50%.”
A characterization of the Rodinia benchmark suite with comparison to contemporary CMP workloads (2010, neutral): “Schatz et al. [ 28 ], is an high-throughput, parallel, pairwise, local-sequence alignment program.”
Large-Scale Transportation Network Congestion Evolution Prediction Using Deep Learning Theory (2015, background): “GPU is designed on a parallel throughput architecture that can execute multiple tasks concurrently [25].”
Computational solutions to large-scale data management and analysis (2010, methodology): “A GPU version of the sequence alignment program MUMmer was developed and achieved a roughly three- to fourfold speed increase over the serial-CPU versio”