CloudBurst: highly sensitive read mapping with MapReduce

TLDR

Next‑generation DNA sequencing generates massive amounts of data, challenging traditional single‑processor read‑mapping algorithms. CloudBurst aims to provide a highly sensitive, parallel read‑mapping algorithm for next‑generation sequencing data, enabling SNP discovery, genotyping, and personal genomics. It extends the RMAP approach to report all or best alignments with any mismatches, and leverages Hadoop MapReduce to parallelize across multiple compute nodes. CloudBurst scales linearly with read count and processor number, achieving up to 30‑fold speedup on 24 cores and >100‑fold on 96 cores, reducing mapping time from hours to minutes for millions of reads. CloudBurst is open‑source and available at http://cloudburst‑bio.sourceforge.net/ (contact [e-mail]).

Abstract

Abstract Motivation: Next-generation DNA sequencing machines are generating an enormous amount of sequence data, placing unprecedented demands on traditional single-processor read-mapping algorithms. CloudBurst is a new parallel read-mapping algorithm optimized for mapping next-generation sequence data to the human genome and other reference genomes, for use in a variety of biological analyses including SNP discovery, genotyping and personal genomics. It is modeled after the short read-mapping program RMAP, and reports either all alignments or the unambiguous best alignment for each read with any number of mismatches or differences. This level of sensitivity could be prohibitively time consuming, but CloudBurst uses the open-source Hadoop implementation of MapReduce to parallelize execution using multiple compute nodes. Results: CloudBurst's running time scales linearly with the number of reads mapped, and with near linear speedup as the number of processors increases. In a 24-processor core configuration, CloudBurst is up to 30 times faster than RMAP executing on a single core, while computing an identical set of alignments. Using a larger remote compute cloud with 96 cores, CloudBurst improved performance by >100-fold, reducing the running time from hours to mere minutes for typical jobs involving mapping of millions of short reads to the human genome. Availability: CloudBurst is available open-source as a model for parallelizing algorithms with MapReduce at http://cloudburst-bio.sourceforge.net/. Contact: [e-mail]