TY - JOUR
T1 - A grammar based methodology for structural motif finding in ncRNA database search.
AU - Quest, Daniel
AU - Tapprich, William
AU - Ali, Hesham
PY - 2007
Y1 - 2007
N2 - In recent years, sequence database searching has been conducted through local alignment heuristics, pattern-matching, and comparison of short statistically significant patterns. While these approaches have unlocked many clues as to sequence relationships, they are limited in that they do not provide context-sensitive searching capabilities (e.g. considering pseudoknots, protein binding positions, and complementary base pairs). Stochastic grammars (hidden Markov models HMMs and stochastic context-free grammars SCFG) do allow for flexibility in terms of local context, but the context comes at the cost of increased computational complexity. In this paper we introduce a new grammar based method for searching for RNA motifs that exist within a conserved RNA structure. Our method constrains computational complexity by using a chain of topology elements. Through the use of a case study we present the algorithmic approach and benchmark our approach against traditional methods.
AB - In recent years, sequence database searching has been conducted through local alignment heuristics, pattern-matching, and comparison of short statistically significant patterns. While these approaches have unlocked many clues as to sequence relationships, they are limited in that they do not provide context-sensitive searching capabilities (e.g. considering pseudoknots, protein binding positions, and complementary base pairs). Stochastic grammars (hidden Markov models HMMs and stochastic context-free grammars SCFG) do allow for flexibility in terms of local context, but the context comes at the cost of increased computational complexity. In this paper we introduce a new grammar based method for searching for RNA motifs that exist within a conserved RNA structure. Our method constrains computational complexity by using a chain of topology elements. Through the use of a case study we present the algorithmic approach and benchmark our approach against traditional methods.
UR - http://www.scopus.com/inward/record.url?scp=38449097515&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38449097515&partnerID=8YFLogxK
U2 - 10.1142/9781860948732_0024
DO - 10.1142/9781860948732_0024
M3 - Article
C2 - 17951826
AN - SCOPUS:38449097515
SN - 1752-7791
VL - 6
SP - 215
EP - 225
JO - Computational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference
JF - Computational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference
ER -