Canonical RNA Pseudoknot Structures with Arc Length $\geq 4$

In this paper, we compute the generating function of the arguably most important target class of folding algorithms into RNA pseudoknot structures. This class consists of $k$-noncrossing, canonical RNA structures having minimum arc length four and generalizes directly the canonical secondary structures, studied by Schuster {\it et al.} \cite{Schuster:98}. The combinatorics of this class is important since, in analogy to the case of secondary structures, generic properties of genotype phenotype maps into RNA pseudoknot structures, like shape space covering \cite{Schuster:94} and neutral networks \cite{Reidys:97a} are a result of the combinatorics and not of the particulars of energy parameters. Let ${\sf Q}_k(n)$ denote the number of these structures over $n$ vertices. We derive exact enumeration results as well as the asymptotic formula ${\sf Q}_k(n)\sim c_k n^{-(k-1)^2-\frac{k-1}{2}}(\gamma_{\theta,k})^{-n}$ for $k=3, ..., 9$ and derive a new proof of Schuster's result, ${\sf Q}_2(n)\sim 1.4848\, n^{-3/2}\,1.8489^{-n}$. Our results imply generic properties of folding maps into RNA pseudoknot structures, most notably the existence of exponentially large neutral networks of RNA pseudoknot structures.