title: A grammar based methodology for structural motif finding in ncRNA database search.
abstract: 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.
authors.affiliation: College of Information Science and Technology, University of Nebraska at Omaha, Omaha, NE 68182-0694, USA. djquest@unmc.edu
authors.forename: Daniel
authors.initials: D
authors.lastname: Quest
authors.forename: William
authors.initials: W
authors.lastname: Tapprich
authors.forename: Hesham
authors.initials: H
authors.lastname: Ali
mesh_terms: 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*
chemical_list: D022661:RNA, Untranslated