Han, Hillary Siwei^{3}; Li, Thomas Jiaxian^{3}; reidys, Christian^{3}

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} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU

DOI:

10.1089/cmb.2013.0128

Abstract:

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.

Type:

Journal article

Language:

English

Published in:

Journal of Computational Biology, 2014, Vol 21, Issue 8, p. 591-608