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.
