BFAST: an alignment tool for large scale genome resequencing.

Homer N, Merriman B, Nelson SF. · 2009

Read BFAST: an alignment tool for large scale genome resequencing. by Homer N, Merriman B, Nelson SF. (2009) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc2770639.txt.

Introduction

Homer, Merriman, and Nelson introduced in 2009 BFAST, a tool for aligning billions of short DNA reads to a reference genome. New sequencing machines made whole-genome resequencing practical, but they produce short reads, twenty-five to one hundred bases, laced with errors and true variants. Aligning them fast without losing accuracy, especially around insertions and deletions, was the bottleneck.

BFAST builds flexible whole-genome indexes to map reads to candidate spots, allowing several indexes for robustness against errors. A Smith-Waterman step then aligns locally with gaps, catching small indels. Against BLAT, MAQ, SHRiMP, and SOAP on simulated and real data, it gained clear sensitivity while keeping adequate speed and cutting false mappings. It aligned a billion reads, a full human resequencing run, in under a day on a modest cluster.

Catalog record

CREATORHomer N, Merriman B, Nelson SF.
YEAR2009
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC2770639

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BFAST: An Alignment Tool for Large Scale Genome Resequencing By Nils Homer, Barry Merriman, Stanley F Nelson, Chad Creighton Published in: PLoS ONE DOI: 10.1371/journal.pone.0007767 ABSTRACT Abstract Background The new generation of massively parallel DNA sequencers, combined with the challenge of whole human genome resequencing, result in the need for rapid and accurate alignment of billions of short DNA sequence reads to a large reference genome. Speed is obviously of great importance, but equally important is maintaining alignment accuracy of short reads, in the 25–100 base range, in the presence of errors and true biological variation. Methodology We introduce a new algorithm specifically optimized for this task, as well as a freely available implementation, BFAST, which can align data produced by any of current sequencing platforms, allows for user-customizable levels of speed and accuracy, supports paired end data, and provides for efficient parallel and multi-threaded computation on a computer cluster. The new method is based on creating flexible, efficient whole genome indexes to rapidly map reads to candidate alignment locations, with arbitrary multiple independent indexes allowed to achieve robustness against read errors and sequence variants. The final local alignment uses a Smith-Waterman method, with gaps to support the detection of small indels. Conclusions We compare BFAST to a selection of large-scale alignment tools - BLAT, MAQ, SHRiMP, and SOAP - in terms of both speed and accuracy, using simulated and real-world datasets. We show BFAST can achieve substantially greater sensitivity of alignment in the context of errors and true variants, especially insertions and deletions, and minimize false mappings, while maintaining adequate speed compared to other current methods. We show BFAST can align the amount of data needed to fully resequence a human genome, one billion reads, with high sensitivity and accuracy, on a modest computer cluster in less than 24 hours. BFAST is available at http://bfast.sourceforge.net. INTRODUCTION Recently developed massively parallel “next-generation” sequencing technologies have begun to replace the previously dominant Sanger sequencing technology [1]–[3] for large-scale sequencing projects. Technologies like Illumina's Genome Analyzer [4], Roche's 454 [5], [6], and ABI's SOLiD [6] are able to generate billions of bases of total sequence in a matter of days. These technologies generate relatively short reads, typically from a few tens to a few hundred bases in length, with a general inverse relation between the total number of reads and the read length. In the context of whole human genome resequencing, on the order of a billion short reads are required to accurately resequence an individual genome, and this creates an unprecedented alignment problem of aligning this many reads to the reference human genome on a practical timescale of days. Using established dynamic programming algorithms [7] to align reads to the entire human genome is grossly impractical, since the computational cost is proportional to the target size. To reduce the cost resulting from a large alignment target, many algorithms have been developed that rapidly reduce the size of the search target for aligning a given read. This is typically performed by passing it through an index of the reference genome [8]–[14], or by indexing the reads and searching the reference genome [15], [16]. Using an indexing approach, all the algorithms reduce the time complexity by trading off accuracy and completeness of the search for candidate alignment locations (CALs) to which local alignment is performed. In aggregate, these algorithms are either limited in performance time or accuracy, and can lead to the inability to detect the biologically relevant variants (predominantly single base mismatches, and insertions or deletions of 3 bases or greater), and with some algorithms imposing a limit on the length of the read that can be considered (see Supplemental Materials S1). To address the general speed and accuracy limitations, especially in the context of short reads with potential errors, single base variants and insertion/deletions, of the currently described alignment tools, we developed a new algorithm and associated software tool called BFAST (for BLAT-like Fast Accurate Search Tool). BFAST can align giga-scale short read sets with comparable or better speed compared to existing methods, while maintaining higher sensitivity and accuracy for deletions/insertions. While our algorithm is meant to facilitate practical human whole-genome resequencing, it is not restricted to this task and should prove useful for many problems that involve aligning massive numbers of short reads to a reference genome. Here we describe the basic approach and demonstrate BFAST robustness to detect an insertion or deletion, relative to other methods in the real world context of sequence errors and polymorphisms. BFAST also has the ability to be customized for given time or sensitivity requirements, since we are able to a priori measure the theoretical sensitivity against mismatches and variants before performing alignment based on the underlying choice of genomic indexes. RESULTS General Design of BFAST BFAST is a powerful and complete means to perform billions of short sequence alignments within the context of large genomes in a highly sensitive and tunable manner. BFAST performs alignment in two steps. First, using multiple indexes of the reference genome, BFAST identifies candidate alignment locations (CALs) for each read. Next, the reads at each CAL are further aligned using gapped local alignment to identify the best match. These processes are supported for direct sequence reads (the typical output of platforms based on sequencing-by-synthesis, such as the Illumina, 454 or Helico sequencers) as well as reads in two base color encoded form, which is the primary output of the ligation-based ABI SOLiD platform. The first step can be substantially tuned for various levels of sensitivity, accuracy, and speed based on the users goals and the error properties of the data. The second step allows for full completion of alignment - i.e. considers all possibilities including SNPs, insertions, deletions, as well as color errors (the latter is relevant for ABI SOLiD data) [7], [17]. Gapped local alignment is considerably more computationally expensive than ungapped alignment, especially for ABI SOLiD color space data, but improves our ability to find SNPs, insertions, deletions, and compensate for color errors simultaneously. In addition, allowing for fully gapped local alignment makes BFAST suitable for data that contains indels as a common error mode (for example, in the 454 or Helicos platforms). Additionally, these indexes are expensive to store in main memory (RAM), and therefore should be fully utilized by generating as many lookups per read as possible, providing sensitivity to errors and variants. What makes BFAST unique is that prior methods neglect one of followings areas that are inherent and key to the highly sensitive and relatively fast lookup process enabled within the design principles of BFAST: 1) use of multiple indexes, 2) full use of indexes when loaded into RAM, or 3) perform fully gapped local alignment (see Supplemental Materials S1). The novel contribution of BFAST is the CAL search step, where we tabulate a list of CALs for each read with the goal to include the true (or correct) location within the CALs. BFAST uses multiple indexes of the reference to increase sensitivity of alignment. Each index is a space-efficient suffix array of the reference genome (see Figure 1). An index is defined by a spaced seed (or mask), a string of 0s and 1s that start and end with a 1,

Read the complete text