A grammar based methodology for structural motif finding in ncRNA database search.
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.
Quest
Daniel
D
College of Information Science and Technology, University of Nebraska at Omaha, Omaha, NE 68182-0694, USA. djquest@unmc.edu
Tapprich
William
W
Ali
Hesham
H
D001483:Base Sequence; D003198:Computer Simulation; D030561:Databases, Nucleic Acid; D008956:Models, Chemical; D008957:Models, Genetic; D008969:Molecular Sequence Data; D022661:RNA, Untranslated / Q000737:chemistry* / Q000235:genetics*; D012660:Semantics; D016415:Sequence Alignment / Q000379:methods; D017423:Sequence Analysis, RNA / Q000379:methods*
D022661:RNA, Untranslated