Shapes of topological RNA structures

• RNA shapes classified by topological genus.
• For fixed genus there are finitely many shapes.
• Uniform sampling algorithm for shapes of genus g ≥ 0 in O(g log g) time complexity.
• Coefficients of shape polynomial in an explicit form.
• Some applications in the context of data bases of RNA pseudoknot 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.