With its highest performance settings, Bowtie may fail to align a small number of reads with valid alignments, if those reads have multiple mismatches. If one or more exact matches exist for a read, then Bowtie is guaranteed to report one, but if the best match is an inexact one then Bowtie is not guaranteed in all cases to find the highest quality alignment. We have used Bowtie to align 14.3× coverage worth of human Illumina reads from the 1,000 Genomes project in about 14 hours on a single desktop computer with four processor cores.īowtie makes a number of compromises to achieve this speed, but these trade-offs are reasonable within the context of mammalian re-sequencing projects. Multiple processor cores can be used simultaneously to achieve even greater alignment speed. The index is small enough to be distributed over the internet and to be stored on disk and re-used. The small footprint allows Bowtie to run on a typical desktop computer with 2 GB of RAM.
Bowtie employs a Burrows-Wheeler index based on the full-text minute-space (FM) index, which has a memory footprint of only about 1.3 gigabytes (GB) for the human genome. In our experiments using reads from the 1,000 Genomes project, Bowtie aligns 35-base pair (bp) reads at a rate of more than 25 million reads per CPU-hour, which is more than 35 times faster than Maq and 300 times faster than SOAP under the same conditions (see Tables 1 and 2). Eland is a commercial alignment program available from Illumina that uses a hash-based algorithm to align reads.īowtie uses a different and novel indexing strategy to create an ultrafast, memory-efficient short read aligner geared toward mammalian re-sequencing. SHRiMP employs a combination of spaced seeds and the Smith-Waterman algorithm to align reads with high sensitivity at the expense of speed. Spaced seeds have been shown to yield higher sensitivity than contiguous seeds of the same length. For example, ZOOM uses 'spaced seeds' to significantly outperform RMAP, which is based on a simpler algorithm developed by Baeza-Yaetes and Perleberg. Some employ recent theoretical advances to align reads quickly without sacrificing sensitivity. Each tool builds a hash table of short oligomers present in either the reads (SHRiMP, Maq, RMAP, and ZOOM) or the reference (SOAP).
Maq and SOAP take the same basic algorithmic approach as other recent read mapping tools such as RMAP, ZOOM, and SHRiMP. Although using Maq or SOAP for this purpose has been shown to be feasible by using multiple CPUs, there is a clear need for new tools that consume less time and computational resources. For example, extrapolating from the results presented here in Tables 1 and 2, one can see that Maq would require more than 5 central processing unit (CPU)-months and SOAP more than 3 CPU-years to align the 140 billion bases from the study by Ley and coworkers. With existing methods, the computational cost of aligning many short reads to a mammalian genome is very large. In addition to these projects, the 1,000 Genomes project is in the process of using high-throughput sequencing instruments to sequence a total of about six trillion base pairs of human DNA. The third human re-sequencing study used the SOAP program to align more than 100 billion bases to the reference genome. For example, two of the studies used the short read alignment tool Maq to align more than 130 billion bases (about 45× coverage) of short Illumina reads to a human reference genome in order to detect genetic variations. Each of these studies required the alignment of large numbers of short DNA sequences ('short reads') onto the human genome.
The Illumina instrument was recently used to re-sequence three human genomes, one from a cancer patient and two from previously unsequenced ethnic groups. Technologies from Illumina (San Diego, CA, USA) and Applied Biosystems (Foster City, CA, USA) have been used to profile methylation patterns (MeDIP-Seq), to map DNA-protein interactions (ChIP-Seq), and to identify differentially expressed genes (RNA-Seq) in the human genome and other species. Improvements in the efficiency of DNA sequencing have both broadened the applications for sequencing and dramatically increased the size of sequencing datasets.
0 kommentar(er)
