RNA-LEGO: Combinatorial Design of Pseudoknot RNA

In this paper we enumerate $k$-noncrossing RNA pseudoknot structures with given minimum stack-length. We show that the numbers of $k$-noncrossing structures without isolated base pairs are significantly smaller than the number of all $k$-noncrossing structures. In particular we prove that the number of 3- and 4-noncrossing RNA structures with stack-length $\ge 2$ is for large $n$ given by $311.2470\frac{4!}{n(n-1)\mathrm{.}\mathrm{.}\mathrm{.}(n-4)}{2.5881}^n$ and $1.217\cdot 10^{7} n^{-{21/2}} 3.0382^n$,respectively\mathrm{.}Wefurthermoreshowthatfor$k$-noncrossing RNA structures the drop in exponential growth rates between the number of all structures and the number of all structures with stack-size $\ge 2$ increases significantly. Our results are of importance for prediction algorithms for pseudoknot-RNA and provide evidence that there exist neutral networks of RNA pseudoknot structures.