GPU and FPGA-accelerated Bioinformatics Algorithms

Many researchers are starting to look into hardware acceleration to speed up their bioinformatics analysis. For example, please check this seqanswers thread, where davispeter asked about GPU-accelerated genome assembly programs.

Our next few commentaries will cover various hardware-accelerated approaches. We will start from very basics before exploring more complex topics. Following our typical style, we will stay away from describing how to download, install and run specific programs and instead focus on explaining how the technologies work and discussing programming approach and algorithms. We will also try to explain, where the main cost savings come from. Be aware the topic of cost savings is directly related to ease of programming, but ‘ease of programming’ is often very subjective. My grandma finds it very difficult to program her microwave clock.

Please feel free to suggest any algorithm of your interest in the comment section. We are collecting a list of references and will append to this post, as soon as it is ready.

————————-

GPU Algorithms

1. Short Read Alignment

CUSHAW – fast short read alignment for CUDA-enabled GPUs

Yongchao Liu, Bertil Schmidt, and Douglas L. Maskell: ” CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform”. Bioinformatics, 2012, 28(14): 1830-1837.

Yongchao Liu and Bertil Schmidt: “Long read alignment based on maximal exact match seeds”. Bioinformatics, 2012, 28(18): i318-324.

Exact and complete short read alignment to microbial genomes using GPU programming – Jochen Blom et al.

2. Effi cient Hash Tables on the GPU

PhD Thesis – UC Davis

Dan Alcantara’s Website

3. Assembly

Yongchao Liu, Bertil Schmidt, and Douglas L. Maskell: “Parallelized short read assembly of large genomes using de Bruijn graphs”. BMC Bioinformatics 2011, 12:354.

4. Error Correction

Yongchao Liu, Bertil Schmidt, and Douglas L. Maskell: “DecGPU: distributed error correction on massively parallel graphics processing units using CUDA and MPI”. BMC Bioinformatics (impact factor 3.43), 2011, 12:85.

5. Phylogeny

Efficient Implementation of MrBayes on multi-GPU – Jie Bao, Hongju Xia, Jianfu Zhou, Xiaoguang Liu and Gang Wang.

MrBayes on a graphics processing unit – Zhou J, Liu X, Stones DS, Xie Q, Wang G.

6. BLAST

GPU-BLAST: using graphics processors to accelerate protein sequence alignment

Panagiotis D. Vouzis and Nikolaos V. Sahinidis.

8. Other Implemented Programs

NVIDIA’s GPU page.

————————

FPGA Algorithms

1. Short Read Alignment

Shepard: A Fast Exact Match Short Read Aligner

An FPGA Acceleration of Short Read Human Genome Mapping – Corey Bruce Olson

A hybrid short read mapping accelerator – Yupeng Chen, Bertil Schmidt and Douglas L Maskell.

Accelerating Phylogeny-Aware Short DNA Read Alignment with FPGAs- Nikolaos Alachiotis, Simon Berger, Alexandros Stamatakis

2. BLAST

RC-BLAST: Towards a Portable, Cost-Effective Open Source Hardware

Implementation – Krishna Muriki et al.

Single Pass, BLAST-Like, Approximate String Matching on FPGAs – Martin C. Herbordt Josh Model Yongfeng Gu Bharat Sukhwani Tom VanCourt.

A Systolic Array-Based FPGA Parallel Architecture for the BLAST Algorithm – Xinyu Guo, HongWang, and Vijay Devabhaktuni.

——————

MPI, Multicore

1. BLAST

The Design, Implementation, and Evaluation of mpiBLAST

2. Burrows Wheeler

Optimizing Burrows-Wheeler Transform-Based Sequence Alignment on Multicore Architectures – Jing Zhang et al.