Query-Dependent Banding (QDB) for Faster RNA Similarity Searches

By Eric P. Nawrocki, Sean R. Eddy. PLoS Comput. Biol., 2007

315 citations recorded by the source corpus.

When searching sequence databases for RNAs, it is desirable to score both primary sequence and RNA secondary structure similarity. Covariance models (CMs) are probabilistic models well-suited for RNA similarity search applications. However, the computational complexity of CM dynamic programming alignment algorithms has limited their practical application. Here we describe an acceleration method called query-dependent banding (QDB), which uses the probabilistic query CM to precalculate regions of the dynamic programming lattice that have negligible probability, independently of the target database. We have implemented QDB in the freely available Infernal software package. QDB reduces the average case time complexity of CM alignment from LN 2.4 to LN 1.3 for a query RNA of N residues and a target database of L residues, resulting in a 4-fold speedup for typical RNA queries. Combined with other improvements to Infernal, including informative mixture Dirichlet priors on model parameters, benchmarks also show increased sensitivity and specificity resulting from improved parameterization.

Subfields: Molecular Biology

View Paper: https://www.semanticscholar.org/paper/d54700c1e8ecd9e2e6f02038e1e715d502ba2087

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

Infernal 1.0: inference of RNA alignments (2009, methodology): “Each of the 51 query alignments was used to build a CM and search the pseudogenome, a single list of all hits for all families described in Nawrocki and Eddy (2007), producing the ROC curves in Figure 1.”
A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation (2008, result): “For example, our preliminary results indicate that local alignment scores for profile stochastic-context free grammars (SCFGs; models of RNA structure and sequence) obey the same conjectures for both CYK and Inside scores (analogous to local Viterbi and Forward scores) (DL Kolbe and SRE, unpublished”
Comparison of two next-generation sequencing technologies for resolving highly complex microbiota composition using tandem variable 16S rRNA gene regions (2010, unknown): “Pyrosequencing reads were aligned using Infernal (32) and associated covariance models obtained from the Ribosomal Database Project Group.”
Comparative Analysis of Pyrosequencing and a Phylogenetic Microarray for Exploring Microbial Community Structures in the Human Distal Intestine (2009, unknown): “Pyrosequencing reads were aligned using Infernal [61] and associated covariance models obtained from the Ribosomal Database Project Group.”
Rfam: updates to the RNA families database (2008, methodology): “This so-called SEED alignment is used to build a covariance model (CM) with the Infernal software (1).”
454 Pyrosequencing reveals bacterial diversity of activated sludge from 14 sewage treatment plants (2011, methodology): “The normalized sequence set of each AS sample was also individually aligned by Infernal (Nawrocki and Eddy, 2007) using the bacteria-alignment model in Align module of the RDP.”
Bacterial Communities in Women with Bacterial Vaginosis: High Resolution Phylogenetic Analyses Reveal Relationships of Microbiota to Clinical Criteria (2012, methodology): “2 [28] according to a 16S rRNA alignment profile provided by the RDP [29].”
nhmmer: DNA homology search with profile HMMs (2013, unknown): “For more details on construction of the benchmark, see Nawrocki and Eddy (2007).”