Tree adjoining grammars for RNA structure prediction

Yasuo Uemura*, Aki Hasegawa, Satoshi Kobayashi, Takashi Yokomori

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

134 Citations (Scopus)


In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm.

Original languageEnglish
Pages (from-to)277-303
Number of pages27
JournalTheoretical Computer Science
Issue number2
Publication statusPublished - 1999 Jan 17
Externally publishedYes


  • Parsing algorithms
  • RNA secondary structures
  • RNA structure prediction
  • Tree adjoining grammars

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Tree adjoining grammars for RNA structure prediction'. Together they form a unique fingerprint.

Cite this