Stacks in canonical RNA pseudoknot structures

Abstract

In this paper we study the distribution of stacks in $k$-noncrossing, $\tau$-canonical RNA pseudoknot structures ($<k,\tau >$-structures). An RNA structure is called $k$-noncrossing if it has no more than $k-1$ mutually crossing arcs and $\tau$-canonical if each arc is contained in a stack of length at least $\tau$. Based on the ordinary generating function of $<k,\tau >$-structures \cite{Reidys:08ma} we derive the bivariate generating function ${\mathbf{T}}_{k,\tau }(x,u)={\sum }_{n\ge 0}{\sum }_{0\le t\le \frac{n}{2}}{\mathsf{T}}_{k,\tau }^{}(n,t)u^t{x}^n$, where ${\mathsf{T}}_{k,\tau }(n,t)$ is the number of $<k,\tau >$-structures having exactly $t$ stacks and study its singularities. We show that for a certain parametrization of the variable $u$, ${\mathbf{T}}_{k,\tau }(x,u)$ has a unique, dominant singularity. The particular shift of this singularity parametrized by $u$ implies a central limit theorem for the distribution of stack-numbers. Our results are of importance for understanding the ``language'' of minimum-free energy RNA pseudoknot structures, generated by computer folding algorithms.

19pages, 4 figures

References in corpus (3)

• RNA-LEGO: Combinatorial Design of Pseudoknot RNA
• Asymptotic analysis of $k$-noncrossing matchings
• Canonical RNA pseudoknot structures