Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2009 Jun 1;25(11):1363-9.
doi: 10.1093/bioinformatics/btp236. Epub 2009 Apr 8.

CloudBurst: highly sensitive read mapping with MapReduce

Michael C Schatz  1
Affiliations

CloudBurst: highly sensitive read mapping with MapReduce

Michael C Schatz. Bioinformatics. .

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/).

PubMed Disclaimer

Figures

Fig. 1.
Fig. 1.
Schematic overview of MapReduce. The input file(s) are automatically partitioned into chunks depending on their size and the desired number of mappers. Each mapper (shown here as m1 and m2) executes a user-defined function on a chunk of the input and emits key–value pairs. The shuffle phase creates a list of values associated with each key (shown here as k1, k2 and kn). The reducers (shown here as r1 and r2) evaluate a user-defined function for their subset of the keys and associated list of values, to create the set of output files.
Fig. 2.
Fig. 2.
Overview of the CloudBurst algorithm. The map phase emits k-mers as keys for every k-mer in the reference, and for all non-overlapping k-mers in the reads. The shufle phase groups together the k-mers shared between the reads and the reference. The reduce phase extends the seeds into end-to-end alignments allowing for a fixed number of mismatches or indels. Here, two grey reference seeds are compared with a single read creating one alignment with two errors and one alignment with zero errors, while the black shared seed is extended to an alignment with three errors.
Fig. 3.
Fig. 3.
Evaluation of CloudBurst running time while scaling the number of reads and sensitive for mapping to the (A) full human genome; (B) chromosomes 1; and (C) 22 on the local cluster with 24 cores. Tinted lines indicate timings allowing 0 (fastest) through four (slowest) mismatches between a read and the reference. As the number of reads increases, the running time increases linearly. As the number of allowed mismatches increases, the running time increases superlinearly from the exponential increase in seed instances. The four mismatch computation against the full human genome failed to complete due to lack of available disk space after reporting ∼25 billion end-to-end alignments.
Fig. 4.
Fig. 4.
CloudBurst running time compared with RMAP for 7M reads, showing the speedup of CloudBurst running on 24 cores compared with RMAP running on 1 core. As the number of allowed mismatches increases, the relative overhead decreases allowing CloudBurst to meet and exceed 24× linear speedup.
Fig. 5.
Fig. 5.
Comparison of CloudBurst running time (in seconds) while scaling size of the cluster for mapping 7M reads to human chromosome 22 with at most four mismatches on the EC2 Cluster. The 96-core cluster is 3.5× faster than the 24-core cluster.
See this image and copyright information in PMC

Similar articles

See all similar articles

Cited by

See all "Cited by" articles

References

    1. Altschul SF, et al. Basic local alignment search tool. J. Mol. Biol. 1990;215:403–410. - PubMed
    1. Baeza-yates RA, et al. Proceedings of the Combinatorial Pattern Matching, Third Annual Symposium. Tucson, AZ: 1992. Fast and practical approximate string matching; pp. 185–192.
    1. Bentley DR, et al. Accurate whole human genome sequencing using reversible terminator chemistry. Nature. 2008;456:53–59. - PMC - PubMed
    1. Ghemawat S, et al. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles. Bolton Landing, NY, USA: ACM; 2003. The Google file system; pp. 29–43.
    1. Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. England: Cambridge University Press; 1997.

Publication types

-