title: Topological language for RNA.
abstract: In this paper we introduce a novel, context-free grammar, RNAFeatures*, capable of generating any RNA structure including pseudoknot structures (pk-structure). We represent pk-structures as orientable fatgraphs, which naturally leads to a filtration by their topological genus. Within this framework, RNA secondary structures correspond to pk-structures of genus zero. RNAFeatures*acts on formal, arc-labeled RNA secondary structures, called λ-structures. λ-structures correspond one-to-one to pk-structures together with some additional information. This information consists of the specific rearrangement of the backbone, by which a pk-structure can be made cross-free. RNAFeatures*is an extension of the grammar for secondary structures and employs an enhancement by labelings of the symbols as well as the production rules. We discuss how to use RNAFeatures*to obtain a stochastic context-free grammar for pk-structures, using data of RNA sequences and structures. The induced grammar facilitates fast Boltzmann sampling and statistical analysis. As a first application, we present an O(nlog (n)) runtime algorithm which samples pk-structures based on ninety tRNA sequences and structures from the Nucleic Acid Database (NDB).
  
  
  
  the source code for simulation results is available at http://staff.vbi.vt.edu/fenixh/TPstructure.zip. The code is written in C and compiled by Xcode.
authors: Biocomplexity Institute of Virginia Tech, Virginia Tech, United States. Electronic address: fenixprotoss@gmail.com.
authors: Fenix W D
authors: FW
authors: Huang
authors: Biocomplexity Institute of Virginia Tech, Virginia Tech, United States. Electronic address: duck@santafe.edu.
authors: Christian M
authors: CM
authors: Reidys
mesh_terms: D008962:Models, Theoretical; D012313:RNA / Q000737:chemistry*
chemical_list: D012313:RNA
keywords: Context-free grammar; Fatgraph; RNA pseudoknot structure; Stochastic context-free grammar; Topological RNA structure