CloudBurst: highly sensitive read mapping with MapReduce

By Michael C. Schatz. Bioinform., 2009

695 citations recorded by the source corpus.

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: mschatz@umiacs.umd.edu

Subfields: Artificial Intelligence, Information Systems and Management, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/540a803d3d99f3b7814f37652c056718c701b5c5

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 Information Systems and Management

In Molecular Biology

Citations in the corpus

The impact of next-generation sequencing on genomics (2011, methodology): “CloudBurst is another new parallel read-mapping cloud algorithm optimized for mapping NGS data to a human reference genome, SNP discovery, genotyping and personal genomics (Schatz, 2009).”
Fractal MapReduce decomposition of sequence alignment (2012, methodology): “Accordingly, the use the MapReduce functional pattern now underlie many of the leading genomic analysis packages such as GATK [12] and CloudBurst [13] and is the key cloud computing abstraction for large scale data management and analysis [11,14].”
From RNA-seq reads to differential expression results (2010, methodology): “Mapping General aligner GMAP/GSNAP [91] BFAST [20] BOWTIE [25] CloudBurst [92] GNUmap [93] MAQ/BWA [23] PerM [19] RazerS [94] Mrfast/mrsfast [22] SOAP/SOAP2 [24,95] SHRiMP [21] De novo annotator QPALMA/GenomeMapper/PALMapper [37] SpliceMap [96] SOAPals [95] G-Mo.”
Cloud-scale RNA-sequencing differential expression analysis with Myrna (2010, background): “Recent studies and commentaries [13-17] propose cloud computing as a paradigm that counteracts this disparity by tapping into the economies of scale afforded by commercial and institutional computing centers.”
Searching for SNPs with cloud computing (2009, methodology): “The CloudBurst project [16] explored the benefits of using Hadoop as a platform for alignment of short reads.”
SkewTune: mitigating skew in mapreduce applications (2012, background): “Categories and Subject Descriptors H.2.4 [Database Management]: Systems—Distributed databases, Parallel databases, Query processing General Terms Design, Performance”
Parallel data processing with MapReduce: a survey (2012, background): “quencing data to a reference genome for genotyping in parallel [78].”
Assembly Algorithms for Next-Generation Sequencing Data (2010, neutral): “Published software includes SOAP [68,69], MAQ [70], Bowtie [71], RMAP [72], CloudBurst [73], SHRiMP [74], RazerS [75], PerM [76], segemehl [77], GenomeMapper [78], and BOAT [79].”
An overview of the Hadoop/MapReduce/HBase framework and its current applications in bioinformatics (2010, background): “Schatz’s Cloudburst paper [42], published in May 2009, put Hadoop “on the map” in bioinformatics.”
Computational solutions to large-scale data management and analysis (2010, background): “and aligning raw sequencing reads to reference genome”
Airavat: Security and Privacy for MapReduce (2010, result): “As a case study, one of the authors of this paper ported CloudBurst, a genome mapping algorithm written for MapReduce [47], to Airavat.”
Next generation sequencing and bioinformatic bottlenecks: the current state of metagenomic data analysis. (2012, neutral): “Mapping/alignment BWA [48] Bowtie [49] Novoalign [50] SOAP [51] MrFAST [52] CloudBurst [53] BFAST [54] MUMer [26] MOSAIK http://bioinformatics.”
'Big data', Hadoop and cloud computing in genomics (2013, neutral): “[76] when working at the University of Maryland.”