Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
3
pubmed:dateCreated
2007-5-21
pubmed:abstractText
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.
pubmed:grant
pubmed:commentsCorrections
http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-10024243, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-10926490, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-11125083, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-11700055, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-11713323, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-11752288, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12029131, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12095421, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12140321, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12624257, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12654723, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-12844358, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-14499004, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-14704338, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-15262817, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-15507142, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-15608160, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-15731213, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-15780137, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-16267089, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-16373490, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-16381856, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-16873520, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-17044173, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-17151342, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-2051488, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-7549879, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-7800507, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-8029015, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-8390686, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-8902360, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-9023104, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-9254694, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-9399864, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-9773344, http://linkedlifedata.com/resource/pubmed/commentcorrection/17397253-9927713
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:chemical
pubmed:status
MEDLINE
pubmed:month
Mar
pubmed:issn
1553-7358
pubmed:author
pubmed:issnType
Electronic
pubmed:day
30
pubmed:volume
3
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
e56
pubmed:dateRevised
2009-11-18
pubmed:meshHeading
pubmed:year
2007
pubmed:articleTitle
Query-dependent banding (QDB) for faster RNA similarity searches.
pubmed:affiliation
Howard Hughes Medical Institute, Janelia Farm Research Campus, Ashburn, Virginia, United States of America.
pubmed:publicationType
Journal Article, Research Support, Non-U.S. Gov't, Evaluation Studies, Research Support, N.I.H., Extramural