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

@article{citeulike:1320731, abstract = {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 LN2.4 to LN1.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.}, author = {Nawrocki, Eric P. and Eddy, Sean R. }, citeulike-article-id = {1320731}, doi = {http://dx.doi.org/10.1371/journal.pcbi.0030056}, journal = {PLoS Computational Biology}, keywords = {covariance, rna}, month = {March}, number = {3}, pages = {e56+}, posted-at = {2007-05-23 09:42:12}, priority = {2}, title = {Query-Dependent Banding (QDB) for Faster RNA Similarity Searches}, url = {http://dx.doi.org/10.1371/journal.pcbi.0030056}, volume = {3}, year = {2007} }

TY - JOUR ID - citeulike:1320731 L3 - citeulike-article-id:1320731 TI - Query-Dependent Banding (QDB) for Faster RNA Similarity Searches JF - PLoS Computational Biology VL - 3 IS - 3 SP - e56 N2 - 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 LN2.4 to LN1.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. KW - covariance KW - rna AU - Nawrocki, Eric AU - Eddy, Sean PY - 2007/03/01/ UR - http://dx.doi.org/10.1371/journal.pcbi.0030056 ER -