Han, Hillary Siwei3; Li, Thomas Jiaxian3; reidys, Christian3
1 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU2 Mathematics, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU3 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
In this paper we study canonical $\gamma$-structures, a class of RNA pseudoknot structures that plays a key role in the context of polynomial time folding of RNA pseudoknot structures. A $\gamma$-structure is composed by specific building blocks, that have topological genus less than or equal to $\gamma$, where composition means concatenation and nesting of such blocks. Our main result is the derivation of the generating function of $\gamma$-structures via symbolic enumeration. $\gamma$-structures are constructed via $\gamma$-matchings. We compute an algebraic equation for the generating function of these matchings and prove that it is the unique solution. For $\gamma=1$ and $\gamma=2$ we compute the Puiseux-expansion of this power series at its unique, dominant singularity. This allows us to derive simple asymptotic formulas for the number of 1-structures and 2-structures.
Journal of Computational Biology, 2014, Vol 21, Issue 8, p. 591-608