Database indexing for production MegaBLAST searches

By Aleksandr Morgulis, George F. Coulouris, Yan Raytselis, Thomas L. Madden, Richa Agarwala, Alejandro A. Schäffer. Bioinform., 2008

1,247 citations recorded by the source corpus.

Motivation: The BLAST software package for sequence comparison speeds up homology search by preprocessing a query sequence into a lookup table. Numerous research studies have suggested that preprocessing the database instead would give better performance. However, production usage of sequence comparison methods that preprocess the database has been limited to programs such as BLAT and SSAHA that are designed to find matches when query and database subsequences are highly similar. Results: We developed a new version of the MegaBLAST module of BLAST that does the initial phase of finding short seeds for matches by searching a database index. We also developed a program makembindex that preprocesses the database into a data structure for rapid seed searching. We show that the new ‘indexed MegaBLAST’ is faster than the ‘non-indexed’ version for most practical uses. We show that indexed MegaBLAST is faster than miBLAST, another implementation of BLAST nucleotide searching with a preprocessed database, for most of the 200 queries we tested. To deploy indexed MegaBLAST as part of NCBI'sWeb BLAST service, the storage of databases and the queueing mechanism were modified, so that some machines are now dedicated to serving queries for a specific database. The response time for such Web queries is now faster than it was when each computer handled queries for multiple databases. Availability: The code for indexed MegaBLAST is part of the blastn program in the NCBI C++ toolkit. The preprocessor program makembindex is also in the toolkit. Indexed MegaBLAST has been used in production on NCBI's Web BLAST service to search one version of the human and mouse genomes since October 2007. The Linux command-line executables for blastn and makembindex, documentation, and some query sets used to carry out the tests described below are available in the directory: ftp://ftp.ncbi.nlm.nih.gov/pub/agarwala/indexed_megablast Contact: schaffer@helix.nih.gov Supplementary information: Supplementary data are available at Bioinformatics online.

Subfields: Molecular Biology

View Paper: https://www.semanticscholar.org/paper/6348c3490aa17188229decfd09b67e5169ce1cfc

How researchers see this paper

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

In Molecular Biology

Citations in the corpus

Bracken: estimating species abundance in metagenomics data (2016, neutral): “…first published in 2014, the Kraken metagenomics classifier represented a major enhancement in the speed with which large metagenomics sequence data could be processed (Wood & Salzberg, 2014), running over 900 times faster than MegaBlast (Morgulis et al., 2008), the closest competitor at the time.”
BLAST+: architecture and applications (2009, methodology): “Morgulis et al. [23] also allow users to apply soft-masking to their database.”
Capturing single-copy nuclear genes, organellar genomes, and nuclear ribosomal DNA from deep genome skimming data for plant phylogenetics: A case study in Vitaceae (2021, methodology): “2) in Geneious Prime (Kearse et al., 2012), with the parameters settings in the Megablast program (Morgulis et al., 2008) as a maximum of 60 hits, a maximum E-value of 1 × 10−10, a linear gap cost, a word size of 28, and scores of 1 for match and −2 for mismatch in alignments.”
CRISPRTarget (2013, background): “55,56 The discovery of new spacer targets would be facilitated by tools that allow flexibility in these areas and enable searches of recent metagenomic data sets.”
Discovery and functional characterization of diverse Class 2 CRISPR-Cas systems (2015, methodology): “The spacer sequences were searched against the NCBI nucleotide NR and WGS databases using MEGABLAST (Morgulis et al., 2008) with default parameters except that the word size was set at 20.”
Fast Identification and Removal of Sequence Contamination from Genomic and Metagenomic Datasets (2011, methodology): “were designed to align DNA and protein sequences and to search through large databases to find homologous sequences. MegaBLAST was developed to speed up the alignment for query sequences that are highly similar to the reference sequences and was used to align large-scale sequencing data. Later, impr”
Adaptive seeds tame genomic sequence comparison. (2011, result): “However, we also report direct comparisons with BLASTN (Altschul et al. 1997) and LASTZ (Harris 2007) and also BLASTP and MEGABLAST (Morgulis et al. 2008) in the Supplemental material (Supplemental Figs.”
High speed BLASTN: an accelerated MegaBLAST search tool (2015, neutral): “See (27,19,14) for more details.”