Modeling RNA Secondary Structures Using Tree Grammars

Takashi YOKOMORI (

Department of Computer Science and Information Mathematics
The University of Electro-Communications
1-5-1, Chofugaoka, Chofu, Tokyo 182, Japan


This paper proposes a grammatical tool, called tree adjunct grammar with tag for RNA ( denoted by TAG^2_{RNA} ), for representing secondary structures of RNAs, and shows some example TAG^2_{RNA} grammars for fairly complicated RNA secondary structures. We then demonstrate the appropriateness of the grammars for modeling RNA secondary structures by discussing its formal language and/or graph theoretic properties, including closure properties of TAG^2_{RNA} and graph planarity of secondary structures generated by TAG^2_{RNA}, the latter of which would provide a biologically reasonable constraint.