Parallel and Scalable Short-Read Alignment on Multi-Core Clusters Using UPC+

PLoS One. 2016 Jan 5;11(1):e0145490. doi: 10.1371/journal.pone.0145490. eCollection 2016.

Abstract

The growth of next-generation sequencing (NGS) datasets poses a challenge to the alignment of reads to reference genomes in terms of alignment quality and execution speed. Some available aligners have been shown to obtain high quality mappings at the expense of long execution times. Finding fast yet accurate software solutions is of high importance to research, since availability and size of NGS datasets continue to increase. In this work we present an efficient parallelization approach for NGS short-read alignment on multi-core clusters. Our approach takes advantage of a distributed shared memory programming model based on the new UPC++ language. Experimental results using the CUSHAW3 aligner show that our implementation based on dynamic scheduling obtains good scalability on multi-core clusters. Through our evaluation, we are able to complete the single-end and paired-end alignments of 246 million reads of length 150 base-pairs in 11.54 and 16.64 minutes, respectively, using 32 nodes with four AMD Opteron 6272 16-core CPUs per node. In contrast, the multi-threaded original tool needs 2.77 and 5.54 hours to perform the same alignments on the 64 cores of one node. The source code of our parallel implementation is publicly available at the CUSHAW3 homepage (http://cushaw3.sourceforge.net).

MeSH terms

  • Algorithms
  • Computational Biology / methods*
  • Genome, Human / genetics
  • High-Throughput Nucleotide Sequencing / methods*
  • Humans
  • Internet
  • Programming Languages*
  • Reproducibility of Results
  • Sequence Alignment / methods*

Grants and funding

The authors have no support or funding to report.