Combinatorics of \gamma-structures

MaRDI QIDQ6229767zbMATH OpenFDO

Authors Hillary S. W. Han, Thomas J. X. Li, Christian M. Reidys

Publication date 18 December 2011

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

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 using so called irreducible shadows. We furthermore recursively compute the generating polynomials of irreducible shadows of genus $legamma$. $gamma$-structures are constructed via $gamma$-matchings. For $1legammale10$, we compute Puiseux-expansions at the unique, dominant singularities, allowing us to derive simple asymptotic formulas for the number of $gamma$-structures.

This page was built for publication: Combinatorics of $\gamma$-structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6229767)