Satoshi KOBAYASHI (satoshi@cs.uec.ac.jp)
Takashi YOKOMORI (yokomori@cs.uec.ac.jp)
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.