A Grammar Based Methodology for Structural Motif Finding in ncRNA Database Search

Daniel Quest*, William Tapprich, Hesham Ali

College of Information Science and Technology, University of Nebraska at Omaha, Omaha, NE 68182-0694, USA. djquest@unmc.edu

Proc LSS Comput Syst Bioinform Conf. August, 2007. Vol. 6, p. 215-225. Full-Text PDF

*To whom correspondence should be addressed.

In recent years, sequence database searching has been conducted through local alignment heuristics, patternmatching, 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.