Combinatorics of $γ$-structures

Details Combinatorics of $γ$-structures Combinatorics of $γ$-structures

2011-12-18

arxiv.org/abs/1112.4151v1

Mathematics

Combinatorics

17 pages 6 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Combinatorics of $γ$-structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorics of $γ$-structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorics of $γ$-structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25938