Shapes of topological RNA structures.
A topological RNA structure is derived by fattening the edges of a contact structure into ribbons. The shape of a topological RNA structure is obtained by collapsing the stacks of the structure into single arcs and by removing any arcs of length one, as well as isolated vertices. A shape contains the key topological information of the molecular conformation and for fixed topological genus there exist only finitely many such shapes. In this paper we compute the generating polynomial of shapes of fixed topological genus g. We furthermore derive an algorithm having O(glog g) time complexity uniformly generating shapes of genus g and discuss some applications in the context of databases of RNA pseudoknot structures.
Virginia Bioinformatics Institute, 1015 Life Sciences Circle, Blacksburg, VA, USA. Electronic address: fenixprotoss@gmail.com.
Fenix W D
FW
Huang
Virginia Bioinformatics Institute, 1015 Life Sciences Circle, Blacksburg, VA, USA. Electronic address: duck@santafe.edu.
Christian M
CM
Reidys
D000465:Algorithms; D030561:Databases, Nucleic Acid; D055641:Mathematical Concepts; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
D012313:RNA
Generating function; Genus; RNA shape; Tree; Uniform generation