Faster and More Accurate Sequence Alignment with SNAP
Title | Faster and More Accurate Sequence Alignment with SNAP |
Publication Type | Miscellaneous |
Year of Publication | 2011 |
Authors | Zaharia, M., Bolosky W. J., Curtis K., Fox A., Patterson D., Shenker S. J., Stoica I., Karp R. M., & Sittler T. |
Other Numbers | 3256 |
Abstract | 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 10100faster than state-of-the-art tools such as BWA. Unlike recentaligners based on the Burrows-Wheeler transform, SNAP usesa simple hash index of short seed sequences from the genome,similar to BLASTs. However, SNAP greatly reduces the numberand cost of local alignment checks performed through severalmeasures: it uses longer seeds to reduce the false positivelocations considered, leverages larger memory capacitiesto speed index lookup, and excludes most candidate locationswithout fully computing their edit distance to the read. The resultis an algorithm that scales well for reads from one hundredto thousands of bases long and provides a rich error model thatcan match classes of mutations (e.g., longer indels) that todaysfast aligners ignore. We calculate that SNAP can align a datasetwith 30 coverage of a human genome in less than an hour fora cost of $2 on Amazon EC2, with higher accuracy than BWA.Finally, we describe ongoing work to further improve SNAP. |
Acknowledgment | We would like to thank Matthew Meyerson for providingmotivation and encouragement for this work, and forhis feedback on its utility in cancer and pathogen discovery.This research is supported in part by gifts fromthe following Berkeley AMP Lab sponsors: Google,SAP, Amazon Web Services, Cloudera, Ericsson, GeneralElectric, Huawei, IBM, Intel, Mark Logic, Microsoft,NEC Labs, Network Appliance, Oracle, QuantaComputer, Splunk and VMware, and by DARPA (contract#FA8650-11-C-7136). |
URL | http://www.icsi.berkeley.edu/pubs/networking/ICSI_fasterandmoreaccurate11.pdf |
Bibliographic Notes | arXiv.org under arXiv:1111.5572v1 |
Abbreviated Authors | M. Zaharia, W. J. Bolosky, K. Curtis, A. Fox, D. Patterson, S. Shenker, I. Stoica, R. M. Karp, and T. Sittler |
ICSI Research Group | Algorithms |
ICSI Publication Type | None |