Faster and More Accurate Sequence Alignment with SNAP
By Matei A. Zaharia, William J. Bolosky, Kristal Curtis, Armando Fox, David A. Patterson, Scott Shenker, Ion Stoica, Richard M. Karp, T. Sittler. arXiv.org, 2011
303 citations recorded by the source corpus.
We present the Scalable Nucleotide Alignment Program (SNAP), a new short and long read aligner that is both more accurate (i.e., aligns more reads with fewer errors) and 10-100x faster than state-of-the-art tools such as BWA. Unlike recent aligners based on the Burrows-Wheeler transform, SNAP uses a simple hash index of short seed sequences from the genome, similar to BLAST's. However, SNAP greatly reduces the number and cost of local alignment checks performed through several measures: it uses longer seeds to reduce the false positive locations considered, leverages larger memory capacities to speed index lookup, and excludes most candidate locations without fully computing their edit distance to the read. The result is an algorithm that scales well for reads from one hundred to thousands of bases long and provides a rich error model that can match classes of mutations (e.g., longer indels) that today's fast aligners ignore. We calculate that SNAP can align a dataset with 30x coverage of a human genome in less than an hour for a cost of $2 on Amazon EC2, with higher accuracy than BWA. Finally, we describe ongoing work to further improve SNAP.
Subfields: Artificial Intelligence, Molecular Biology, Plant Science
View Paper: https://www.semanticscholar.org/paper/eaa398d58b7712a9bbc25b177a93624a7029ed29
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
- Matei A. Zaharia
- C. Wilks
- Valentin Antonescu
- Ben Langmead
- Rone Charles
- Heng Li
- Steven L. Salzberg
- Omar Khattab
In Molecular Biology
- C. Wilks
- Valentin Antonescu
- Rone Charles
- Ben Langmead
- C. Chiu
- Steve Miller
- Heng Li
- Steven L. Salzberg
Citations in the corpus
- Scaling read aligners to hundreds of threads on general-purpose processors (2017, background): “It can also exceed available memory for aligners with larger data structures, such as GEM [20] and SNAP [21], as shown previously [6].”
- A cloud-compatible bioinformatics pipeline for ultrarapid pathogen identification from next-generation sequencing of clinical samples (2014, methodology): “SNAP is a new, hash-based nucleotide aligner developed for mapping of NGS data to reference genomes across a wide range of read lengths (50–10,000 bp) (Zaharia et al. 2011).”