Andersen, Joergen Ellegard^{3}; Penner, Robert C.^{3}; Reidys, Christian^{5}; Waterman, Michael S.^{4}

Affiliations:

^{1} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{2} Mathematics, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{3} Aarhus Universitet^{4} University of Southern California^{5} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU

Abstract:

To an RNA pseudoknot structure is naturally associated a topological surface, which has its associated genus, and structures can thus be classified by genus. Based on earlier work of Harer-Zagier, we compute the generating function ${\bf D}_{g,\sigma}(z)=\sum_{n}{\bf d}_{g,\sigma}(n)z^n$ for the number ${\bf d}_{g,\sigma}(n)$ of those structures of fixed genus $g$ and minimum stack size $\sigma$ with $n$ nucleotides so that no two consecutive nucleotides are basepaired and show that ${\bf D}_{g,\sigma}(z)$ is algebraic. In particular, we prove that ${\bf d}_{g,2}(n)\sim k_g\,n^{3(g-\frac{1}{2})} \gamma_2^n$, where $\gamma_2\approx 1.9685$. Thus, for stack size at least two, the genus only enters through the sub-exponential factor, and the slow growth rate compared to the number of RNA molecules implies the existence of neutral networks of distinct molecules with the same structure of any genus. Certain RNA structures called shapes are shown to be in natural one-to-one correspondence with the cells in the Penner-Strebel decomposition of Riemann's moduli space of a surface of genus $g$ with one boundary component, thus providing a link between RNA enumerative problems and the geometry of Riemann's moduli space.