Recent methods for rna modeling using stochastic context-free grammars

Yasubumi Sakakibara, Michael Brown, Richard Hughey, Saira Mian, Kimmen Sjölander, Rebecca C. Underwood, David Haussler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)


Stochastic context-free grammars (SC, FGs) Call be applied to the problems of folding, aligning and modeling families of homologous RNA sequences. SCFGs capture tile sequences’ common primary and secondary structure and generalize the hidden Markov models (HMMs) used in related work on protein and DNA. This paper discusses our new algorithm, Tree-Grammar EM, for deducing SCFG parameters automatically from unaligned, unfolded training sequences. Tree-Grammar EM, a generalization of tile HMM forward-backward algorithm, is based on tree grammars and is faster than tile previously proposed inside-outside SCFG training algorithm. Independently, Scan Eddy and Richard Durbin have introduced a trainable “covariance model” (CM) to perform similar tasks. We compare and contrast our methods with theirs.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings
EditorsMaxime Crochemore, Dan Gusfield
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783540580942
Publication statusPublished - 1994
Externally publishedYes
Event5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994 - Asilomar, United States
Duration: 1994 Jun 51994 Jun 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Recent methods for rna modeling using stochastic context-free grammars'. Together they form a unique fingerprint.

Cite this