BFAST: An Alignment Tool for Large Scale Genome Resequencing

By Nils Homer, Barry Merriman, Stanley F. Nelson. PLoS ONE, 2009

586 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Genetics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/116abc90ecbe8cac7dc7c52a26d20e37081cae32

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Genetics

In Molecular Biology

Citations in the corpus

Ten simple rules for responsible big data research (2017, background): “Even data about groups—“aggregate statistics”—can have serious implications if they reveal that certain communities, for example, suffer from stigmatized diseases or social behavior much more than others [27].”
From RNA-seq reads to differential expression results (2010, methodology): “Current aligners enable fast heuristic matching by using either hash tables [19-22] or the Burrows Wheeler transform (BWT) [23-25].”
The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote (2013, background): “The extension step usually involves backtracking (3,5), Smith–Waterman dynamic programming (4–6 , 8) or Needleman– Wunsch A recent trend to avoid problems with the choice of seed is to try multiple spaced seeds (8,9,13,15–18).”
Comparative analysis of RNA-Seq alignment algorithms and the RNA-Seq unified mapper (RUM) (2011, methodology): “…algorithms, we developed an RNA-Seq simulator that produces paired-end sequence reads with configurable rates for substitutions, indels, novel splice forms, intron signal and random error, including a decrease of the quality in the tails of the reads, as is typically observed in Illumina data.”
MapSplice: Accurate mapping of RNA-seq reads for splice junction discovery (2010, methodology): “Exonic alignment of segments can be performed using fast approximate aligners such as Bowtie (23), and BWA (24), or aligners with more general error tolerance models such as SOAP2 (25), BFAST (26) and MAQ (27).”
A survey of sequence alignment algorithms for next-generation sequencing (2010, background): “[25] proposed a two-level indexing scheme for any large q.”
Computational methods for transcriptome annotation and quantification using RNA-seq (2011, background): “Seed methods 31–38 such as mapping and assembly with quality (MAQ) 33 and Stampy 35 find matches for short subsequences, termed ‘seeds’, assuming that at least each approach and their application to RNA-seq analysis.”
Sequence-specific error profile of Illumina sequencers (2011, unknown): “Bacillus subtilis 270 168 78 58 (10) 574 Mycobacterium bovis 6001 409 1306 931 (11) 8647 Staphylococcus aureus 488 9 35 150 (22) 682 Bordetella pertussis 4141 62 603 531 (10) 5422 e90 Nucleic Acids Research, 2011, Vol.”
Tools for mapping high-throughput sequencing data (2012, background): “Received on May 2, 2012; revised on October 4, 2012; accepted on October 8, 2012”
An international effort towards developing standards for best practices in analysis, interpretation and reporting of clinical genome sequencing results in the CLARITY Challenge (2014, methodology): “Reported aligners used for SOLiD data included the LifeScope aligner, BFAST [25], BWA [26-28], Novocraft ’ s novoalignCS (Selangor, Malaysia) and the Genomatix aligner (Munich, Germany), with some teams utilizing multiple tools for comparison.”
Fast Identification and Removal of Sequence Contamination from Genomic and Metagenomic Datasets (2011, background): “For example, many short-read alignment programs were designed for reads v100 bp [23–27].”
Next generation sequencing and bioinformatic bottlenecks: the current state of metagenomic data analysis. (2012, unknown): “Mapping/alignment BWA [48] Bowtie [49] Novoalign [50] SOAP [51] MrFAST [52] CloudBurst [53] BFAST [54] MUMer [26] MOSAIK http://bioinformatics.”