Format

Send to

Choose Destination
J Comput Biol. 2014 Aug;21(8):591-608. doi: 10.1089/cmb.2013.0128. Epub 2014 Apr 1.

Combinatorics of γ-structures.

Author information

1
Department of Mathematics and Computer Science, University of Southern Denmark , Odense, Denmark .

Abstract

In this article we study canonical γ-structures, a class of RNA pseudoknot structures that plays a key role in the context of polynomial time folding of RNA pseudoknot structures. A γ-structure is composed of specific building blocks that have topological genus less than or equal to γ, where composition means concatenation and nesting of such blocks. Our main result is the derivation of the generating function of γ-structures via symbolic enumeration using so called irreducible shadows. We furthermore recursively compute the generating polynomials of irreducible shadows of genus ≤ γ. The γ-structures are constructed via γ-matchings. For 1 ≤ γ ≤ 10, we compute Puiseux expansions at the unique, dominant singularities, allowing us to derive simple asymptotic formulas for the number of γ-structures.

KEYWORDS:

generating function; irreducible shadow; shape; γ-structure

PMID:
24689708
PMCID:
PMC4116093
DOI:
10.1089/cmb.2013.0128
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for Atypon Icon for PubMed Central
Loading ...
Support Center