A grammar based methodology for structural motif finding in ncRNA database search.

Daniel Quest, William Tapprich, Hesham Ali

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)215-225
Number of pages11
JournalComputational systems bioinformatics / Life Sciences Society. Computational Systems Bioinformatics Conference
StatePublished - 2007

ASJC Scopus subject areas

  • Medicine(all)


Dive into the research topics of 'A grammar based methodology for structural motif finding in ncRNA database search.'. Together they form a unique fingerprint.

Cite this