Fast and accurate read alignment for resequencing

Abstract

Motivation: Next-generation sequence analysis has become an important task both in laboratory and clinical settings. A key stage in the majority sequence analysis workflows, such as resequencing, is the alignment of genomic reads to a reference genome. The accurate alignment of reads with large indels is a computationally challenging task for researchers.

Results: We introduce SeqAlto as a new algorithm for read alignment. For reads longer than or equal to 100 bp, SeqAlto is up to 10 × faster than existing algorithms, while retaining high accuracy and the ability to align reads with large (up to 50 bp) indels. This improvement in efficiency is particularly important in the analysis of future sequencing data where the number of reads approaches many billions. Furthermore, SeqAlto uses less than 8 GB of memory to align against the human genome. SeqAlto is benchmarked against several existing tools with both real and simulated data.

Availability: Linux and Mac OS X binaries free for academic use are available at http://www.stanford.edu/group/wonglab/seqalto

Contact: whwong@stanford.edu.

Fig. 1.

100-bp single-end reads with deletion in random location. Reported results are for MAPQ ≥ value in parentheses. Data points with < 30% of the reads aligned correctly were removed due to erratic behavior of the percent correct value, (a) percent of reads aligned (b) percent of aligned reads correct.

Fig. 2.

100-bp single-end reads with insertion in random location. Reported results are for MAPQ ≥ value in parentheses. Data points with < 30% of the reads aligned correctly were removed due to erratic behavior of the percent correct value, (a) percent of reads aligned (b) percent of aligned reads correct.