In practice, pruning strategies such as double indexing6 and bidirectional Burrows-Wheeler transform (BWT)7 facilitate very efficient ungapped alignment of short reads. Although this search space is large, many portions of it can be skipped (pruned) without loss of sensitivity. Index-assisted aligners work by searching for all ways of mutating the read string into a string that occurs in the reference, subject to an alignment policy limiting the number of differences. The full-text minute index5 is a fast and memory-efficient index that has been used in recent aligners610. Many aligners use a genome index to rapidly narrow the list of candidate alignment locations. This is because for each read the aligner must solve a difficult computational problem: determining the reads likely point of origin with respect to a reference genome4. In many cases, the alignment step is the slowest.
Bowtie 2 combines the strengths of the full-text minute index with the exibility and speed of hardware-accelerated dynamic programming algorithms to achieve a combination of high speed, sensitivity and accuracy.Īligning sequencing reads to a reference genome is the first step in many comparative genomics pipelines, including pipelines for variant calling1, isoform quantitation2 and differential gene expression3. The full-text minute index is often used to make alignment very fast and memory-efcient, but the approach is ill-suited to nding longer, gapped alignments. All rights reserved.Īs the rate of sequencing increases, greater throughput is demanded from read aligners.