We show the expected order of RNA saturated secondary structures of size $n$ is $log_4n(1+O(frac{log_2n}{n}))$, if we select the saturated secondary structure uniformly at random. Furthermore, the order of saturated secondary structures is sharply co
ncentrated around its mean. As a consequence saturated structures and structures in the traditional model behave the same with respect to the expected order. Thus we may conclude that the traditional model has already drawn the right picture and conclusions inferred from it with respect to the order (the overall shape) of a structure remain valid even if enforcing saturation (at least in expectation).
The random reversal graph offers new perspectives, allowing to study the connectivity of genomes as well as their most likely distance as a function of the reversal rate. Our main result shows that the structure of the random reversal graph changes d
ramatically at $lambda_n=1/binom{n+1}{2}$. For $lambda_n=(1-epsilon)/binom{n+1}{2}$, the random graph consists of components of size at most $O(nln(n))$ a.s. and for $(1+epsilon)/binom{n+1}{2}$, there emerges a unique largest component of size $sim wp(epsilon) cdot 2^ncdot n$!$ a.s.. This giant component is furthermore dense in the reversal graph.
In this paper we study $k$-noncrossing matchings. A $k$-noncrossing matching is a labeled graph with vertex set ${1,...,2n}$ arranged in increasing order in a horizontal line and vertex-degree 1. The $n$ arcs are drawn in the upper halfplane subject
to the condition that there exist no $k$ arcs that mutually intersect. We derive: (a) for arbitrary $k$, an asymptotic approximation of the exponential generating function of $k$-noncrossing matchings $F_k(z)$. (b) the asymptotic formula for the number of $k$-noncrossing matchings $f_{k}(n) sim c_k n^{-((k-1)^2+(k-1)/2)} (2(k-1))^{2n}$ for some $c_k>0$.
In this paper we enumerate $k$-noncrossing RNA pseudoknot structures with given minimum arc- and stack-length. That is, we study the numbers of RNA pseudoknot structures with arc-length $ge 3$, stack-length $ge sigma$ and in which there are at most $
k-1$ mutually crossing bonds, denoted by ${sf T}_{k,sigma}^{[3]}(n)$. In particular we prove that the numbers of 3, 4 and 5-noncrossing RNA structures with arc-length $ge 3$ and stack-length $ge 2$ satisfy ${sf T}_{3,2}^{[3]}(n)^{}sim K_3 n^{-5} 2.5723^n$, ${sf T}^{[3]}_{4,2}(n)sim K_4 n^{-{21/2}} 3.0306^n$, and ${sf T}^{[3]}_{5,2}(n)sim K_5 n^{-18} 3.4092^n$, respectively, where $K_3,K_4,K_5$ are constants. Our results are of importance for prediction algorithms for RNA pseudoknot structures.
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)...(n-4)}2.5881^n$ and $1.217cdot 10^{7} n^{-{21/2}} 3.0382^n$, respectively. We furthermore show that for $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.
