BACKGROUND
three decades ago, michael waterman pioneered the combinatorics and ab initio prediction of the at that time rather exotic ribunucleic acid  secondary structures  <cit> .
the motivation for this work was coming from a fundamental dichotomy represented by rna.
on one hand rna is described by its primary sequence, a linear string composed of the nucleotides a, g, u and c. the primary sequence embodies the genotypic legislative.
on the other hand, rna, being less structurally constrained than its chemical relative dna, does fold into 3d-structures, representing the phenotypic executive.
therefore one molecule stands for both: geno- and phenotype.
indeed, a vast variety of rna activities was found: the discovery of catalytic rnas, or ribozymes, in  <dig> proved that rna could catalyze reactions just as proteins.
rna can act also as a messenger between dna and protein in the form of transfer rna.
the realization that rna combines features of proteins with dna led to the "rna world" hypothesis for the origin of life.
the idea was that dna and the much more versatile proteins took over rna's functions in the transition from the "rna-world" to the "dna/protein-world".
let us have a closer look at rna phenotypes.
rna molecules form "helical" structures by folding, i.e.
pairing their nucleotides and thereby lowering their minimum free energy .
originally, these bonds were subject to strict combinatorial constraints, for instance "noncrossing" in rna secondary structures.
for the latter, dynamic programming  algorithms, predicting the minimum free energy configuration were given  <dig>  <cit> .
it is wellknown, however, that rna structures are far more complex than secondary structures.
one particularly prominent feature is the existence of cross-serial dependencies  <cit> , that is crossing arcs or pseudoknots, see figure  <dig>  where we display the natural utr-pseudoknot structure of the mouse hepatitis virus.
cross also folds into the natural structure given in figure  <dig>  in figure  <dig> we present another rna pseudoknot structure, the hdv-pseudoknot.
we present here the structure as folded by cross and also its natural structure  <cit> .
in fact, rna pseudoknots are "everywhere".
they occur in functional rna, like for instance rnasep  <cit>  as well as ribosomal rna  <cit> .
they are conserved in the catalytic core of group i introns, in plant viral rnas pseudoknots mimic trna structure and in in vitro rna evolution  <cit> , where experiments produced families of rna structures with pseudoknot motifs, when binding hiv- <dig> reverse transcripts.
important mechanisms like ribosomal frame shifting  <cit>  also involve pseudoknot interactions.
for prediction algorithms the implications of cross-serial dependencies are severe-they imply a higher level of formal language: context-sensitive.
in general, on this level of formal languages it is not clear whether or not polynomial time ab initio folding algorithms exist.
indeed, lyngsø et al.
<cit>  showed that "reasonable" classes of rna pseudoknots require exponential time algorithms.
there exist however, polynomial time folding algorithms, capable of the energy based prediction of certain pseudoknots: rivas et al.
<cit> , uemura et al.
<cit> , akutsu  <cit>  and lyngsø  <cit> .
the output of these algorithms, however, remains somewhat "mysterious"-it is not clear which types of pseudoknots can be generated.
in analogy to the case of rna secondary structures, the identification of key combinatorial properties of the output class offers deeper understanding.
the combinatorial properties of rna pseudoknot structures discussed in the following have indeed profound implications: first sequence-structure maps will generate exponentially many structures with neutral networks of exponential size.
second, the latter will come close to each other in sequence space, thereby allowing for efficient evolutionary search.
none of these findings depend on the particular choice of loop-energies or the partition function  <cit> .
furthermore, without combinatorial specification, as it is the case for the above mentioned dp based pseudoknot folding algorithms  <cit> , one arrives at an impossibly large configuration space.
for instance, the inductive generation of gap-matrices produces arbitrarily high number of mutually crossing arcs.
the results in  <cit>  prove, that the exponential growth rate of pseudoknot structures is linear in the crossing number.
accordingly, via gap-matrices, an uncontrollably large output class is being generated.
nevertheless, the dp-routine using pairs of gap-matrices cannot generate any 3-noncrossing nonplanar pseudoknot structure.
we will show that the notion of k-noncrossing diagrams  <cit>  allows us to specify a suitable output-class for pseudoknot folding algorithms.
recall that a diagram is a graph over the vertex set  = { <dig>  ..., n} with vertex degree less than or equal to one.
it is represented by drawing the vertices in a horizontal line and its arcs , where i <j, in the upper half-plane.
the vertices and arcs correspond to nucleotides and watson-crick  and  base pairs, respectively.
a diagram is k-noncrossing if it contains at most k -  <dig> mutually crossing arcs.
diagrams have the following three key parameters: the maximum number of mutually crossing arcs, k -  <dig>  the minimum arc-length, λ, and minimum stack-length, τ, the length of an arc  is j - i and a stack of length τ is a sequence of "parallel" arcs of the form
, , ..., , j - )),
see figure  <dig>  we call an arc of length λ a λ-arc.
biophysical constraints on the base pairings imply that in all rna structures λ is greater than or equal to four.
we call diagrams with a minimum stack-length τ, τ-canonical and if λ ≥  <dig> we refer to diagrams as structures.
to reiterate, in the simplest case we have 2-noncrossing rna structures, i.e.
the secondary structures in which no two arcs cross, see figure  <dig>  the noncrossing of arcs has far-reaching consequences.
it implies that rna secondary structures form a context free language and allow for the dp algorithms  <cit> , predicting the loop-based mfe-secondary structure in o-time and o-space.
let us now, having some background on rna structures return to the rna-world.
around  <dig> peter schuster and his coworkers initiated a paradigm shift.
they began to study evolutionary optimization and neutral evolution of rna via the relation between rna genotypes and phenotypes.
the particular mapping from rna sequences into rna secondary structures was obtained by the algorithm viennarna  <cit> , an implementation of the folding routine  <cit> , mentioned above.
two particularly prominent results of this line of work were the existence of neutral networks, i.e.
vast, extended networks, composed of sequences folding into a given secondary structure  <cit>  and the intersection theorem  <cit> .
the latter guarantees for any two secondary structures the existence of at least one sequence which simultaneously satisfies all constraints imposed by their watson-crick and g-u base pairs.
for the implication of the latter with respect to molecular switches, see  <cit> .
it became evident that the "statistical" properties of this mapping played a central role in the molecular evolution of rna.
but, there is more.
two discoveries suggested that rna might not just be a stepping stone towards a dna/protein world.
they show that rna plays an active role in vital cell processes.
a large number of very small rnas of about  <dig> nucleotides in length, called micrornas , were discovered.
they were found in organisms as diverse as the worm caenorhabditis organs and humans, and their particular relationship to certain intermediates in rna interference .
these findings have put rna-in particular noncoding rna-into the spotlight.
in addition, rna's conformational versatility and catalytic abilities have been identified in the context of protein synthesis and rna splicing.
more and more parallels between rna and protein are currently being revealed  <cit> .
let us next briefly overview what we know about the combinatorics of our phenotypes, ultimatively allowing for the computation of biophysically relevant pseudoknot structures  <cit> .
the key result comes from a seemingly unrelated field, the combinatorics of partitions.
chen et al.
proved in a seminal paper  <cit>  a bijection between walks in weyl chambers and k-noncrossing partitions.
this bijection has recently been generalized to tangled diagrams  <cit> .
now, a k-noncrossing diagram is a special type of k-noncrossing tangle and the relevance of chen's result lies in the fact that the walks in question can be enumerated via the reflection principle.
in fact, the reflection principle facilitated the computation of the generating function of k-noncrossing canonical pseudoknot rna  <cit> .
subsequent singularity analysis  <cit> , showed, that the exponential growth rates of canonical pseudoknot rna structures are surprisingly small, see table  <dig>   <cit> .
for instance, the number of 3-noncrossing, 3-canonical rna structures with arc-length greater than or equal to four is asymptotically given by
cn- <dig>  <dig> n,
where c is some  constant.
this exponential growth rate is very close to schuster et al.
's finding  <cit>  for 2-canonical rna secondary structures with arc-length greater than or equal to four
<dig>  n-3/ <dig>  <dig> n.
for the analysis presented here, we use the algorithm cross  <cit> , which produces a transparent output.
this algorithm does not follow the dp paradigm and generates the mfe-k-noncrossing τ-canonical structure via a combination of branch and bound, as well as dp techniques.
cross inductively constructs k-noncrossing, τ-canonical rna structures via motifs.
currently full loop-based energy models are derived an implemented for k =  <dig> and τ ≥  <dig>
therefore, cross finds the mfe-rna pseudoknot structure in which there are at most two mutually crossing arcs, which has minimum arc-length four and in which each stack has size at least three.
while cross is an exponential time algorithm it allows to fold sequences of length  <dig> with an average folding time of  <dig>  minutes.
methods
while it is beyond the scope of this paper to present the algorithm cross in detail, the objective of this section is first to sketch its key organization and second to discuss some basic properties of rna pseudoknot structures.
these combinatorial properties enable us to assign a unique, loop-based energy.
in the course of our analysis we show that an rna pseudoknot structure can be constructed via simpler substructures.
these serve as the building blocks via which cross derives the mfe-pseudoknot structure.
at present time we do not have an algorithm computing the partition function version of cross.
for rna secondary structures, the partition function was obtained  <dig>  <cit> , three decades after the first mfe-folding algorithms were derived  <cit> .
the partition function is based on a fixed sequence and contains vital statistical information on the probabilities of specific structural configurations of the latter.
for any inductively constructed structure class, it allows to compute the base pairing probabilities.
in analogy to similar studies in the case of rna secondary structures  <cit> , the partition function is for the type of analysis presented here not of key importance.
we shall derive statistical information on the sequence-structure relation by mfe-folding a large number of sequences instead of considering the ensemble of structural configurations of a single sequence.
cross
the algorithm cross has three distinct phases: the motif-, skeleton- and saturation-phase, see figure  <dig> for an overview.
we will here briefly discuss these three parts.
let ≺ denote the following partial order over arcs
≺  ⇔ i <dig> <i <dig> ∧ j <dig> <j <dig>
i.e.
an arc α <dig> is smaller then α <dig> if it is nested in it.
i motifs
let us begin by defining core-structures.
a k-noncrossing core  <cit>  is a k-noncrossing diagram in which all stacks have size one.
the core of a structure is obtained by identifying all its stacks by single arcs, keeping the unpaired nucleotides and finally relabeling, see figure  <dig>
a ⟨k, τ⟩-motif is a ⟨k, τ⟩-diagram over , having the following properties
it has a nonnesting core
all its arcs are contained in stacks of length exactly τ =  <dig> and length λ =  <dig>
a m-shadow is a k-noncrossing diagram obtained by successively increasing the stacks of m from top to bottom, see figure  <dig>
the key observation about motifs is that they can, despite the fact that they exhibit cross-serial dependencies, be generated inductively  <cit> .
ii skeleta
skeleta represent the non-inductive "frames" of pseudoknot rna, i.e.
skeleta entail exactly the cross-serial dependencies, that need to be considered exhaustively.
a skeleton, s, is a 3-noncrossing structure, whose core has a connected l-graph.
an l-graph is a diagram whose arcs are the vertices and two being adjacent if their corresponding arcs cross  <cit> .
an irreducible shadow, isi,j, over .
isi,j is a skeleton which has no nested arcs, see figure  <dig>  phase ii consists in the generation of all skeleta-trees, which are rooted in irreducible shadows.
iii saturation
given a skeleton, cross saturates or "fills" via context-sensitive dp routines the skeleton-intervals.
note that, while the inserted substructures cannot cross any arc of the skeleton, they will in general contain crossing arcs within themselves.
to summarize, first cross inductively constructs all roots of the skeleta-trees, second cross generates the skeleta-trees themselves and third it saturates the skeleta.
loops
we next discuss loops of 3-noncrossing rna structures.
loops are not only the basic building blocks for the mfe-evaluation but also of importance for the coarse grained notion of pseudoknot-shapes, discussed in subsection.
let α be an arc in the 3-noncrossing rna structure, s and denote by as the set of s-arcs that cross β. clearly, we have β ∈ as if and only if α ∈ as.
an arc α ∈ as is called a minimal, β-crossing arc if there exists no α' ∈ as such that α' ≺ α.
let the interval  denote the sequence
.
it is shown in  <cit>  that any 3-noncrossing rna structure can be uniquely decomposed into the following four loop-types:
a hairpin-loop is a pair
, )
where  is an arc.
an interior-loop is a sequence
, , , ),
where  is nested in .
a multi-loop, see figure  <dig>  is a sequence
,,sω1τ <dig> ,sω2τ <dig> ...)
where sωhτh denotes a pseudoknot structure over  ) and subject to the following condition: if all sωhτh = , i.e.
all substructures are simply arcs, for all h, then h =  <dig>
a pseudoknot, see figure  <dig>  consisting of the following data:
a set of arcs
p = {, , ..., },
where i <dig> = min{is} and jt = max{js}, such that
the diagram induced by the arc-set p is irreducible, i.e.
the line-graph of p is connected and
for each  ∈ p there exists some arc β  such that  is minimal β-crossing.
all vertices i <dig> <r <jt, not contained in hairpin, interior- or multi-loops.
decomposition
we now show that each 3-noncrossing rna structure can uniquely be constructed by simpler substructures  <cit> .
furthermore, each 3-noncrossing rna structure has a unique loop decomposition-the basis of our energy evaluation.
we remark that assertion  of the following result remains valid for arbitrary crossing number, k.
theorem.
suppose k ≥  <dig> τ ≥  <dig>
any k-noncrossing, t-canonical rna structure corresponds to an unique sequence of shadows.
any ⟨ <dig>  τ⟩-structure has an unique loop-decomposition.
in figure  <dig> we illustrate how these decompositions work.
RESULTS
our results are organized in two sections.
first we describe our findings with respect to the statistics of pseudoknot rna structures and second we present our data with respect to the particular organization of the sequences in neutral networks.
minimum free energy rna pseudoknot structures
in this section we present some key statistics on pseudoknotted rna structures.
in order to put our findings into context we consider two variants of cross: first, cross <dig>  which generates 3-noncrossing, 3-canonical mfe-structures and second, cross <dig>  which produces 3-noncrossing, 4-canonical mfe-structures.
the fraction of pseudoknots
we next compute the fraction of rna structures with pseudoknots within all structures for cross <dig> and cross <dig>  figure  <dig> displays the fraction of structures with pseudoknots as a function of sequence length.
it is evident that the fraction of pseudoknotted structures is monotone with respect to the sequence length.
our data are based on folding  <dig> random sequences via cross and suggest an linear relation.
in particular, for n =  <dig>  approximately 50% of the structures folded by both versions of cross contain pseudoknots.
pseudoknot-shapes
next we study the dominant pseudoknot-shapes as a function of sequence length.
our notion of pseudoknot-shape is based on k-noncrossing cores  <cit>  discussed in subsection.
the shape of a structure s, is a subset of the core-arcs, induced by all arcs either contained in pseudoknots or arcs contained in multi-loops which contain nested pseudoknots.
in other words, a pseudoknot-shape contains all pseudoknot-arcs and all arcs affecting the energy of pseudoknots, see figure  <dig>  in figure  <dig> we display for cross <dig> and cross <dig> the dominant types.
the shape data are obtained by folding  <dig> random sequences.
in figure  <dig> we display the fraction of sequences on which cross <dig> and cross <dig> coincide, based on folding  <dig> random sequences.
stack-statistics in pseudoknot rna
it is wellknown that large stacks contribute to a low mfe of a structure.
in this section we relate the distribution of stacks in random structures to the distribution of stacks in mfe-pseudoknot structures generated by cross.
this provides insight in what particular spectrum of pseudoknot structures cross produces.
let us first discuss the distribution of stacks in random pseudoknot structures.
the naive approach would be to generate a random structure and count the number of stacks.
however, it is at present time not known how to construct a random pseudoknot structure with uniform probability.
therefore we have to employ a different strategy in order to obtain this distribution for random structures.
the key idea  <cit>  is to consider the bivariate generating function
tk,τ=∑n≥0∑0≤t≤n2tk,τutxn
where tk, τ denotes the number of k-noncrossing, τ-canonical pseudoknot structures having exactly t stacks.
tk, τ can be computed using the cores introduced in section.
the stack-distribution is now given by
p=tk,τ/tk,τ
and via singularity analysis one can show that this distribution becomes asymptotically normal with mean μk, τ and variance σk,τ <dig> given by
μk,τ=−γ′k,τγk,τ
σk,τ2=γk,τ)2−γ″k,τγk,τ.
where γk,t  is the unique dominant singularity parameterized by u = es.
in table  <dig> we display the values μk, τ and σk,τ <dig> for k =  <dig>   <dig>   <dig> and τ =  <dig>  ...,  <dig>  accordingly the number of stacks scales linearly with sequence length and so does the number of loops, since each loop corresponds to a stack.
in figure  <dig> we present the stack distributions of  <dig> structures of random sequences folded by cross <dig> and the normal distribution obtained from table  <dig> .
analogously we present the stack distributions of  <dig> structures of random sequences folded by cross <dig> and the normal distribution obtained from table  <dig> .
neutrality and local connectivity
the mapping from sequence to structures plays an important role for evolution  <cit> .
one of its key roles is to facilitate the search of a sequence-population for better adapted shapes.
in tis context, table  <dig> contains some nontrivial information about the mapping from rna sequences into their pseudoknot structures.
to be precise, table  <dig>  in combination with central limit theorems for the number of arcs in k-noncrossing rna structures  <cit>  allows us to conclude that there exist exponentially many k-noncrossing canonical structures with exponentially large preimages.
indeed, according to table  <dig> the exponential growth rate of the number of k-noncrossing canonical structures,  <dig> = k =  <dig> is strictly smaller than four-the growth rate of the space of all sequences over the natural alphabet.
the central limit theorems for the number of arcs of k-noncrossing, canonical pseudoknot structures  <cit>  exhibit a mean of  <dig>  n and a variance of  <dig>  n. we conclude from this that sequence to structure maps in pseudoknot rna structures cannot be trivial, since the preimages of particular structures have exponential growth rates strictly smaller than four.
as a result the number of canonical pseudoknot structures grows exponentially.
accordingly, a sequence to structure map in pseudoknot rna necessarily generates exponentially many canonical structures.
in light of this, the interesting question then becomes how the set of sequences folding into a given structure is "organized" in sequence space.
the analysis presented in this section is analogous to the investigations for rna secondary structures  <cit>  and can be viewed as a basic protocol for the local statistics of a genotype-phenotype map.
the only exception is subsection, which elaborates on the novel concept of local connectivity  <cit> .
it is only possible to derive local statistics, since, for instance, exhaustive computations of the set of all sequences over the natural alphabet with fixed pseudoknot structure for n >  <dig> is at present time impossible.
neutral walks
let us consider a fixed rna structure, s. let furthermore c denote the set of s-compatible sequences, consisting of all sequences that have at any two paired positions one of the  <dig> nucleotide pairs
, , , , , .
the structure s motivates to consider a new adjacency relation within c .
indeed, we may reorganize a sequence  into the pair
,),
where the uj denote the unpaired nucleotides and the pj =  all base pairs, respectively, see figure  <dig>  we can then view vu =  and vp =  as elements of the formal cubes q4nu and q6np, implying the new adjacency relation for elements of c .
accordingly, there are two types of compatible neighbors in sequence space: u- and p-neighbors: a u-neighbor has hamming distance one and differs exactly by a point mutation at an unpaired position.
analogously a p-neighbor differs by a compatible base pair-mutation, see figure  <dig>  note however, that a p-neighbor has either hamming distance one  ↦ )) or hamming distance two  ↦ )).
we call a u- or a p-neighbor, y, a compatible neighbor.
if y is contained in the neutral network we refer to y as a neutral neighbor.
this gives rise to consider the compatible- and neutral distance, denoted by c and n. these are the minimum length of a c-path and path in the neutral network between v and v', respectively.
our basic experiment is as follows: we select a  sequence, v and fold it into the structure s. we then proceed inductively: assume vi is constructed.
we randomly select some neutral  neighbor of vi, denoted by vi+ <dig>  subject to the condition dh > dh, where dh denotes the hamming distance.
if no such neighbor exists we choose some vi+ <dig> ≠ vi with the property dh = dh.
if all neutral vi-neighbors satisfy dh <dh we stop and output the integer dh.
in figure  <dig> we study  <dig> neutral walks for the following four structures: first an h-pseudoknot loop structure , second a hairpin-loop structure , third an interior-loop structure  and finally the phenylalanine trna structure , see figure  <dig>  our findings are in accordance with those for rna secondary structures.
one can easily neutrally traverse sequence space, suggesting the picture of vast, connected networks composed by neutral sequences.
neutral neighbors
complementing the analysis of neutral walks, we study now the distribution of neutral neighbors.
recall that a neutral neighbor of a sequence v with respect to the structure s = s is a u- or a p-neighbor, y, contained in the neutral network of s. it has hamming distance one or two, depending on whether it is induced by a point or base pair mutation, see figure  <dig>  the distribution of neutral neighbors provides relevant information about the mutational robustness of the structure s. the data presented here, are obtained in the course of the neutral walk experiments, displayed in figure  <dig>  they are given in figure  <dig>  in order to put things into context we also present in figure  <dig> the distribution of neutral neighbors for  <dig> random sequences folded by cross <dig>
local connectivity
connectivity of a subgraph, Γn, of an n-cube alone does not imply that a small hamming distance implies a small distance in Γn.
for neutral sequences this means that two neutral sequences with hamming distance less than four, are possibly connected via a neutral path of much greater length.
evidently, for molecular evolution it is therefore not connectivity but the existence of these short paths what matters.
local connectivity is a property which guarantees the existence of these short paths.
if Γn is locally connected then a small hamming distance does imply a Γn-distance scaled by at most a factor of Δ >  <dig>  we shall begin by studying local connectivity for random induced subgraphs of n-cubes, i.e.
where we select sequences with independent probability λn.
then we transfer the derived concepts to neutral networks of rna pseudoknot structures.
we call Γn is locally connected if and only if almost surely
∃Δ>0;dΓn≤Δdq2n,
provided v, v' are in Γn.
we immediately observe that, trivially, for any finite n such Δ exists.
however, the key point is that  employs the notion "almost surely", i.e.
it holds for arbitrary n.
random graph theory  <cit>  shows that on the one hand, for λn smaller than nδ/n, where δ >  <dig> is arbitrarily small, there exists a.s. no finite Δ satisfying .
on the other hand, for λn larger than or equal to nδ/n, there exists a.s. some finite Δ satisfying .
in other words, there exists a threshold value for local connectivity.
since random subgraphs of n-cubes have giant components for λn = /n, where ε >  <dig>  <cit>  we can conclude that local connectivity emerges distinctly later in the evolution of random subgraphs of n-cubes.
suppose we are given a structure s and sequence v, contained in its neutral network.
by construction, local connectivity refers to the two n-cubes q4nu and q6np induced by s, see figure  <dig>  let
c <dig> = |{v'| c = 2}|
be the cardinality of the set of sequences in compatible distance two.
then the degree of local connectivity of s at v is given by
ds=|{v′|c= <dig> n=4}|c2− <dig>
in other words, ds is the fraction of locally connected vertices of the compatible distance two neighbors of v, that can be obtained via a neutral path of length at most four.
we perform the following experiment: we consider neutral walks for the utr-pseudoknot structure of the mouse hepatitis virus displayed in figure  <dig>  see subsection.
along these walks we compute the locality degree ds and the total number of locally connected sequences.
our findings are presented in figure  <dig>  we can report that the degree of local connectivity is, as suggested by random graph theory, almost 100%.
CONCLUSIONS
rna pseudoknot structures-in particular their statistical properties-are a fascinating and new territory.
to our knowledge the only statistical data beyond rna secondary structures were derived for bi-secondary structures in  <cit> .
the structural concept of k-noncrossing canonical rna structures and the resulting sequence to structure map employed for our experiments is new and represents a natural generalization of rna secondary and bi-secondary structures.
to be precise, bi-secondary structures are exactly planar 3-noncrossing rna structures  <cit> .
it is clear, that for sequence-length less than or equal to  <dig> we only encounter pseudoknots of limited complexity.
our findings presented in figure  <dig> provide a transparent picture of which pseudoknot-shapes dominate for given sequence length.
these results, in combination with the data on the fractions of pseudoknotted structures over sequence length show, that for n =  <dig> we have approximately 35% structures with nontrivial pseudoknots.
in addition it is striking that basically all folded structures are irreducible, i.e.
only a very small fraction can be decomposed into several independent substructures.
this is of interest since decomposable structures can be folded much faster.
it is known,  <cit>  that dyck-paths, i.e.
path starting at the origin, having only up , or down  steps which end on the x-axis, decompose on average into three irreducible parts.
this is of relevance, since a slight generalization of dyck-path, the motzkin-paths, having additional horizontal steps, correspond to secondary structures.
our findings suggest, that while secondary structures, decompose nontrivially, higher and higher crossing numbers change the picture.
this complicates the computation of mfe-pseudoknot rna due to their imminent irreducibility.
both versions of cross produce analogous findings, confirming the generality of our results.
the vast majority of pseudoknot-shapes is of a single type.
as expected, cross <dig> exhibits more structural variety due to the fact that its minimum stack-length is only three.
the ratio of pseudoknot structures shifts significantly from n =  <dig> to n =  <dig> to approximately 50%.
we can conclude from this that pseudoknots cannot be ignored, they evidently become the dominant structure class for n greater than or equal to  <dig>  figure  <dig> shows that the fraction of sequences for which cross <dig> and cross <dig> coincide, decreases linearly as a function of sequence length.
this indicates that larger and larger sequences will exhibit more subtle structural elements whose emergence is facilitated by stabilizing large stacks.
furthermore, the mfe-pseudoknot structures generated by cross are far from being random.
the central limit theorems for random k-noncrossing canonical rna structures, given in table  <dig> imply, that stacks and consequently loops scale linearly with the sequence length.
figure  <dig> clearly shows that the mfe-structures, generated by cross <dig> and cross <dig>  have for n =  <dig> two stacks less than random 3-noncrossing structures with minimum stack-length greater than four and five, respectively.
this deviation is significant and indicates that mfe-pseudoknot structures are far from "typical" random structures.
we remark that, while it is straightforward to generate random rna secondary structures, it is nontrivial to obtain random pseudoknot structures.
in particular, at present time, no polynomial time algorithm is known which generates a random 3-noncrossing rna structure with uniform probability.
the organization of the sequences contained in neutral networks of rna pseudoknot structures seems to be very analogous to the neutral networks of rna secondary structures  <cit> .
figure  <dig> shows that neutral walks can effectively traverse sequence space and the fractions of neutral neighbors, presented in figure  <dig> and figure  <dig> suggest a high degree of neutrality.
we discussed in subsection local connectivity, a property of neutral networks which implies the existence of short, neutral paths.
it is apparent that local connectivity is of central importance for molecular evolution and any type of evolutionary optimization.
it has been shown in  <cit>  that local connectivity is a prerequisite for preserving any type of sequence specific information.
having a random graph threshold value localized at 1/n, local connectivity appears much later than connectivity, being localized at 1/n.
however, the high neutrality degrees of rna pseudoknot structures of figure  <dig> and figure  <dig> imply locally connected neutral networks.
our findings for the utr-pseudoknot structure of the mouse hepatitis virus of length  <dig>  given in figure  <dig>  confirm the local connectivity of neutral networks of particular pseudoknot rna structures.
at all steps of the neutral walks almost all sequences are locally connected.
list of abbreviations used
utr: untranslated region; hdv: hepatitis delta virus; dp:dynamic program; lhs: left hand side; rhs: right hand side.
competing interests
the authors declare that they have no competing interests.
authors' contributions
all authors contributed equally to this paper.

 three decades ago, michael waterman pioneered the combinatorics and ab initio prediction of the at that time rather exotic ribunucleic acid secondary structures. the motivation for this work was coming from a fundamental dichotomy represented by rna. on one hand rna is described by its primary sequence, a linear string composed of the nucleotides a, g, u and c. the primary sequence embodies the genotypic legislative. on the other hand, rna, being less structurally constrained than its chemical relative dna, does fold into 3d-structures, representing the phenotypic executive. therefore one molecule stands for both: geno- and phenotype. indeed, a vast variety of rna activities was found: the discovery of catalytic rnas, or ribozymes, in proved that rna could catalyze reactions just as proteins. rna can act also as a messenger between dna and protein in the form of transfer rna. the realization that rna combines features of proteins with dna led to the "rna world" hypothesis for the origin of life. the idea was that dna and the much more versatile proteins took over rna's functions in the transition from the "rna-world" to the "dna/protein-world". let us have a closer look at rna phenotypes. rna molecules form "helical" structures by folding, i.e. pairing their nucleotides and thereby lowering their minimum free energy. originally, these bonds were subject to strict combinatorial constraints, for instance "noncrossing" in rna secondary structures. for the latter, dynamic programming algorithms, predicting the minimum free energy configuration were given. it is wellknown, however, that rna structures are far more complex than secondary structures. one particularly prominent feature is the existence of cross-serial dependencies, that is crossing arcs or pseudoknots, see figure where we display the natural utr-pseudoknot structure of the mouse hepatitis virus. cross also folds into the natural structure given in figure in figure we present another rna pseudoknot structure, the hdv-pseudoknot. we present here the structure as folded by cross and also its natural structure. in fact, rna pseudoknots are "everywhere". they occur in functional rna, like for instance rnasep as well as ribosomal rna. they are conserved in the catalytic core of group i introns, in plant viral rnas pseudoknots mimic trna structure and in in vitro rna evolution, where experiments produced families of rna structures with pseudoknot motifs, when binding hiv- reverse transcripts. important mechanisms like ribosomal frame shifting also involve pseudoknot interactions. for prediction algorithms the implications of cross-serial dependencies are severe-they imply a higher level of formal language: context-sensitive. in general, on this level of formal languages it is not clear whether or not polynomial time ab initio folding algorithms exist. indeed, lyngsø et al. showed that "reasonable" classes of rna pseudoknots require exponential time algorithms. there exist however, polynomial time folding algorithms, capable of the energy based prediction of certain pseudoknots: rivas et al., uemura et al., akutsu and lyngsø. the output of these algorithms, however, remains somewhat "mysterious"-it is not clear which types of pseudoknots can be generated. in analogy to the case of rna secondary structures, the identification of key combinatorial properties of the output class offers deeper understanding. the combinatorial properties of rna pseudoknot structures discussed in the following have indeed profound implications: first sequence-structure maps will generate exponentially many structures with neutral networks of exponential size. second, the latter will come close to each other in sequence space, thereby allowing for efficient evolutionary search. none of these findings depend on the particular choice of loop-energies or the partition function. furthermore, without combinatorial specification, as it is the case for the above mentioned dp based pseudoknot folding algorithms, one arrives at an impossibly large configuration space. for instance, the inductive generation of gap-matrices produces arbitrarily high number of mutually crossing arcs. the results in prove, that the exponential growth rate of pseudoknot structures is linear in the crossing number. accordingly, via gap-matrices, an uncontrollably large output class is being generated. nevertheless, the dp-routine using pairs of gap-matrices cannot generate any 3-noncrossing nonplanar pseudoknot structure. we will show that the notion of k-noncrossing diagrams allows us to specify a suitable output-class for pseudoknot folding algorithms. recall that a diagram is a graph over the vertex set = {..., n} with vertex degree less than or equal to one. it is represented by drawing the vertices in a horizontal line and its arcs, where i <j, in the upper half-plane. the vertices and arcs correspond to nucleotides and watson-crick and base pairs, respectively. a diagram is k-noncrossing if it contains at most k - mutually crossing arcs. diagrams have the following three key parameters: the maximum number of mutually crossing arcs, k - the minimum arc-length, λ, and minimum stack-length, τ, the length of an arc is j - i and a stack of length τ is a sequence of "parallel" arcs of the form,,...,, j - )), see figure we call an arc of length λ a λ-arc. biophysical constraints on the base pairings imply that in all rna structures λ is greater than or equal to four. we call diagrams with a minimum stack-length τ, τ-canonical and if λ ≥ we refer to diagrams as structures. to reiterate, in the simplest case we have 2-noncrossing rna structures, i.e. the secondary structures in which no two arcs cross, see figure the noncrossing of arcs has far-reaching consequences. it implies that rna secondary structures form a context free language and allow for the dp algorithms, predicting the loop-based mfe-secondary structure in o-time and o-space. let us now, having some background on rna structures return to the rna-world. around peter schuster and his coworkers initiated a paradigm shift. they began to study evolutionary optimization and neutral evolution of rna via the relation between rna genotypes and phenotypes. the particular mapping from rna sequences into rna secondary structures was obtained by the algorithm viennarna, an implementation of the folding routine, mentioned above. two particularly prominent results of this line of work were the existence of neutral networks, i.e. vast, extended networks, composed of sequences folding into a given secondary structure and the intersection theorem. the latter guarantees for any two secondary structures the existence of at least one sequence which simultaneously satisfies all constraints imposed by their watson-crick and g-u base pairs. for the implication of the latter with respect to molecular switches, see. it became evident that the "statistical" properties of this mapping played a central role in the molecular evolution of rna. but, there is more. two discoveries suggested that rna might not just be a stepping stone towards a dna/protein world. they show that rna plays an active role in vital cell processes. a large number of very small rnas of about nucleotides in length, called micrornas, were discovered. they were found in organisms as diverse as the worm caenorhabditis organs and humans, and their particular relationship to certain intermediates in rna interference. these findings have put rna-in particular noncoding rna-into the spotlight. in addition, rna's conformational versatility and catalytic abilities have been identified in the context of protein synthesis and rna splicing. more and more parallels between rna and protein are currently being revealed. let us next briefly overview what we know about the combinatorics of our phenotypes, ultimatively allowing for the computation of biophysically relevant pseudoknot structures. the key result comes from a seemingly unrelated field, the combinatorics of partitions. chen et al. proved in a seminal paper a bijection between walks in weyl chambers and k-noncrossing partitions. this bijection has recently been generalized to tangled diagrams. now, a k-noncrossing diagram is a special type of k-noncrossing tangle and the relevance of chen's result lies in the fact that the walks in question can be enumerated via the reflection principle. in fact, the reflection principle facilitated the computation of the generating function of k-noncrossing canonical pseudoknot rna. subsequent singularity analysis, showed, that the exponential growth rates of canonical pseudoknot rna structures are surprisingly small, see table. for instance, the number of 3-noncrossing, 3-canonical rna structures with arc-length greater than or equal to four is asymptotically given by cn- n, where c is some constant. this exponential growth rate is very close to schuster et al.'s finding for 2-canonical rna secondary structures with arc-length greater than or equal to four n-3/ n. for the analysis presented here, we use the algorithm cross, which produces a transparent output. this algorithm does not follow the dp paradigm and generates the mfe-k-noncrossing τ-canonical structure via a combination of branch and bound, as well as dp techniques. cross inductively constructs k-noncrossing, τ-canonical rna structures via motifs. currently full loop-based energy models are derived an implemented for k = and τ ≥ therefore, cross finds the mfe-rna pseudoknot structure in which there are at most two mutually crossing arcs, which has minimum arc-length four and in which each stack has size at least three. while cross is an exponential time algorithm it allows to fold sequences of length with an average folding time of minutes. methods while it is beyond the scope of this paper to present the algorithm cross in detail, the objective of this section is first to sketch its key organization and second to discuss some basic properties of rna pseudoknot structures. these combinatorial properties enable us to assign a unique, loop-based energy. in the course of our analysis we show that an rna pseudoknot structure can be constructed via simpler substructures. these serve as the building blocks via which cross derives the mfe-pseudoknot structure. at present time we do not have an algorithm computing the partition function version of cross. for rna secondary structures, the partition function was obtained, three decades after the first mfe-folding algorithms were derived. the partition function is based on a fixed sequence and contains vital statistical information on the probabilities of specific structural configurations of the latter. for any inductively constructed structure class, it allows to compute the base pairing probabilities. in analogy to similar studies in the case of rna secondary structures, the partition function is for the type of analysis presented here not of key importance. we shall derive statistical information on the sequence-structure relation by mfe-folding a large number of sequences instead of considering the ensemble of structural configurations of a single sequence. cross the algorithm cross has three distinct phases: the motif-, skeleton- and saturation-phase, see figure for an overview. we will here briefly discuss these three parts. let ≺ denote the following partial order over arcs ≺ ⇔ i <i ∧ j <j i.e. an arc α is smaller then α if it is nested in it. i motifs let us begin by defining core-structures. a k-noncrossing core is a k-noncrossing diagram in which all stacks have size one. the core of a structure is obtained by identifying all its stacks by single arcs, keeping the unpaired nucleotides and finally relabeling, see figure a ⟨k, τ⟩-motif is a ⟨k, τ⟩-diagram over, having the following properties it has a nonnesting core all its arcs are contained in stacks of length exactly τ = and length λ = a m-shadow is a k-noncrossing diagram obtained by successively increasing the stacks of m from top to bottom, see figure the key observation about motifs is that they can, despite the fact that they exhibit cross-serial dependencies, be generated inductively. ii skeleta skeleta represent the non-inductive "frames" of pseudoknot rna, i.e. skeleta entail exactly the cross-serial dependencies, that need to be considered exhaustively. a skeleton, s, is a 3-noncrossing structure, whose core has a connected l-graph. an l-graph is a diagram whose arcs are the vertices and two being adjacent if their corresponding arcs cross. an irreducible shadow, isi,j, over. isi,j is a skeleton which has no nested arcs, see figure phase ii consists in the generation of all skeleta-trees, which are rooted in irreducible shadows. iii saturation given a skeleton, cross saturates or "fills" via context-sensitive dp routines the skeleton-intervals. note that, while the inserted substructures cannot cross any arc of the skeleton, they will in general contain crossing arcs within themselves. to summarize, first cross inductively constructs all roots of the skeleta-trees, second cross generates the skeleta-trees themselves and third it saturates the skeleta. loops we next discuss loops of 3-noncrossing rna structures. loops are not only the basic building blocks for the mfe-evaluation but also of importance for the coarse grained notion of pseudoknot-shapes, discussed in subsection. let α be an arc in the 3-noncrossing rna structure, s and denote by as the set of s-arcs that cross β. clearly, we have β ∈ as if and only if α ∈ as. an arc α ∈ as is called a minimal, β-crossing arc if there exists no α' ∈ as such that α' ≺ α. let the interval denote the sequence. it is shown in that any 3-noncrossing rna structure can be uniquely decomposed into the following four loop-types: a hairpin-loop is a pair, ) where is an arc. an interior-loop is a sequence,,, ), where is nested in. a multi-loop, see figure is a sequence,,sω1τ,sω2τ...) where sωhτh denotes a pseudoknot structure over ) and subject to the following condition: if all sωhτh =, i.e. all substructures are simply arcs, for all h, then h = a pseudoknot, see figure consisting of the following data: a set of arcs p = {,,..., }, where i = min{is} and jt = max{js}, such that the diagram induced by the arc-set p is irreducible, i.e. the line-graph of p is connected and for each ∈ p there exists some arc β such that is minimal β-crossing. all vertices i <r <jt, not contained in hairpin, interior- or multi-loops. decomposition we now show that each 3-noncrossing rna structure can uniquely be constructed by simpler substructures. furthermore, each 3-noncrossing rna structure has a unique loop decomposition-the basis of our energy evaluation. we remark that assertion of the following result remains valid for arbitrary crossing number, k. theorem. suppose k ≥ τ ≥ any k-noncrossing, t-canonical rna structure corresponds to an unique sequence of shadows. any ⟨ τ⟩-structure has an unique loop-decomposition. in figure we illustrate how these decompositions work.  our results are organized in two sections. first we describe our findings with respect to the statistics of pseudoknot rna structures and second we present our data with respect to the particular organization of the sequences in neutral networks. minimum free energy rna pseudoknot structures in this section we present some key statistics on pseudoknotted rna structures. in order to put our findings into context we consider two variants of cross: first, cross which generates 3-noncrossing, 3-canonical mfe-structures and second, cross which produces 3-noncrossing, 4-canonical mfe-structures. the fraction of pseudoknots we next compute the fraction of rna structures with pseudoknots within all structures for cross and cross figure displays the fraction of structures with pseudoknots as a function of sequence length. it is evident that the fraction of pseudoknotted structures is monotone with respect to the sequence length. our data are based on folding random sequences via cross and suggest an linear relation. in particular, for n = approximately 50% of the structures folded by both versions of cross contain pseudoknots. pseudoknot-shapes next we study the dominant pseudoknot-shapes as a function of sequence length. our notion of pseudoknot-shape is based on k-noncrossing cores discussed in subsection. the shape of a structure s, is a subset of the core-arcs, induced by all arcs either contained in pseudoknots or arcs contained in multi-loops which contain nested pseudoknots. in other words, a pseudoknot-shape contains all pseudoknot-arcs and all arcs affecting the energy of pseudoknots, see figure in figure we display for cross and cross the dominant types. the shape data are obtained by folding random sequences. in figure we display the fraction of sequences on which cross and cross coincide, based on folding random sequences. stack-statistics in pseudoknot rna it is wellknown that large stacks contribute to a low mfe of a structure. in this section we relate the distribution of stacks in random structures to the distribution of stacks in mfe-pseudoknot structures generated by cross. this provides insight in what particular spectrum of pseudoknot structures cross produces. let us first discuss the distribution of stacks in random pseudoknot structures. the naive approach would be to generate a random structure and count the number of stacks. however, it is at present time not known how to construct a random pseudoknot structure with uniform probability. therefore we have to employ a different strategy in order to obtain this distribution for random structures. the key idea is to consider the bivariate generating function tk,τ=∑n≥0∑0≤t≤n2tk,τutxn where tk, τ denotes the number of k-noncrossing, τ-canonical pseudoknot structures having exactly t stacks. tk, τ can be computed using the cores introduced in section. the stack-distribution is now given by p=tk,τ/tk,τ and via singularity analysis one can show that this distribution becomes asymptotically normal with mean μk, τ and variance σk,τ given by μk,τ=−γ′k,τγk,τ σk,τ2=γk,τ)2−γ″k,τγk,τ. where γk,t is the unique dominant singularity parameterized by u = es. in table we display the values μk, τ and σk,τ for k = and τ =..., accordingly the number of stacks scales linearly with sequence length and so does the number of loops, since each loop corresponds to a stack. in figure we present the stack distributions of structures of random sequences folded by cross and the normal distribution obtained from table. analogously we present the stack distributions of structures of random sequences folded by cross and the normal distribution obtained from table. neutrality and local connectivity the mapping from sequence to structures plays an important role for evolution. one of its key roles is to facilitate the search of a sequence-population for better adapted shapes. in tis context, table contains some nontrivial information about the mapping from rna sequences into their pseudoknot structures. to be precise, table in combination with central limit theorems for the number of arcs in k-noncrossing rna structures allows us to conclude that there exist exponentially many k-noncrossing canonical structures with exponentially large preimages. indeed, according to table the exponential growth rate of the number of k-noncrossing canonical structures, = k = is strictly smaller than four-the growth rate of the space of all sequences over the natural alphabet. the central limit theorems for the number of arcs of k-noncrossing, canonical pseudoknot structures exhibit a mean of n and a variance of n. we conclude from this that sequence to structure maps in pseudoknot rna structures cannot be trivial, since the preimages of particular structures have exponential growth rates strictly smaller than four. as a result the number of canonical pseudoknot structures grows exponentially. accordingly, a sequence to structure map in pseudoknot rna necessarily generates exponentially many canonical structures. in light of this, the interesting question then becomes how the set of sequences folding into a given structure is "organized" in sequence space. the analysis presented in this section is analogous to the investigations for rna secondary structures and can be viewed as a basic protocol for the local statistics of a genotype-phenotype map. the only exception is subsection, which elaborates on the novel concept of local connectivity. it is only possible to derive local statistics, since, for instance, exhaustive computations of the set of all sequences over the natural alphabet with fixed pseudoknot structure for n > is at present time impossible. neutral walks let us consider a fixed rna structure, s. let furthermore c denote the set of s-compatible sequences, consisting of all sequences that have at any two paired positions one of the nucleotide pairs,,,,,. the structure s motivates to consider a new adjacency relation within c. indeed, we may reorganize a sequence into the pair,), where the uj denote the unpaired nucleotides and the pj = all base pairs, respectively, see figure we can then view vu = and vp = as elements of the formal cubes q4nu and q6np, implying the new adjacency relation for elements of c. accordingly, there are two types of compatible neighbors in sequence space: u- and p-neighbors: a u-neighbor has hamming distance one and differs exactly by a point mutation at an unpaired position. analogously a p-neighbor differs by a compatible base pair-mutation, see figure note however, that a p-neighbor has either hamming distance one ↦ )) or hamming distance two ↦ )). we call a u- or a p-neighbor, y, a compatible neighbor. if y is contained in the neutral network we refer to y as a neutral neighbor. this gives rise to consider the compatible- and neutral distance, denoted by c and n. these are the minimum length of a c-path and path in the neutral network between v and v', respectively. our basic experiment is as follows: we select a sequence, v and fold it into the structure s. we then proceed inductively: assume vi is constructed. we randomly select some neutral neighbor of vi, denoted by vi+ subject to the condition dh > dh, where dh denotes the hamming distance. if no such neighbor exists we choose some vi+ ≠ vi with the property dh = dh. if all neutral vi-neighbors satisfy dh <dh we stop and output the integer dh. in figure we study neutral walks for the following four structures: first an h-pseudoknot loop structure, second a hairpin-loop structure, third an interior-loop structure and finally the phenylalanine trna structure, see figure our findings are in accordance with those for rna secondary structures. one can easily neutrally traverse sequence space, suggesting the picture of vast, connected networks composed by neutral sequences. neutral neighbors complementing the analysis of neutral walks, we study now the distribution of neutral neighbors. recall that a neutral neighbor of a sequence v with respect to the structure s = s is a u- or a p-neighbor, y, contained in the neutral network of s. it has hamming distance one or two, depending on whether it is induced by a point or base pair mutation, see figure the distribution of neutral neighbors provides relevant information about the mutational robustness of the structure s. the data presented here, are obtained in the course of the neutral walk experiments, displayed in figure they are given in figure in order to put things into context we also present in figure the distribution of neutral neighbors for random sequences folded by cross local connectivity connectivity of a subgraph, Γn, of an n-cube alone does not imply that a small hamming distance implies a small distance in Γn. for neutral sequences this means that two neutral sequences with hamming distance less than four, are possibly connected via a neutral path of much greater length. evidently, for molecular evolution it is therefore not connectivity but the existence of these short paths what matters. local connectivity is a property which guarantees the existence of these short paths. if Γn is locally connected then a small hamming distance does imply a Γn-distance scaled by at most a factor of Δ > we shall begin by studying local connectivity for random induced subgraphs of n-cubes, i.e. where we select sequences with independent probability λn. then we transfer the derived concepts to neutral networks of rna pseudoknot structures. we call Γn is locally connected if and only if almost surely ∃Δ>0;dΓn≤Δdq2n, provided v, v' are in Γn. we immediately observe that, trivially, for any finite n such Δ exists. however, the key point is that employs the notion "almost surely", i.e. it holds for arbitrary n. random graph theory shows that on the one hand, for λn smaller than nδ/n, where δ > is arbitrarily small, there exists a.s. no finite Δ satisfying. on the other hand, for λn larger than or equal to nδ/n, there exists a.s. some finite Δ satisfying. in other words, there exists a threshold value for local connectivity. since random subgraphs of n-cubes have giant components for λn = /n, where ε > we can conclude that local connectivity emerges distinctly later in the evolution of random subgraphs of n-cubes. suppose we are given a structure s and sequence v, contained in its neutral network. by construction, local connectivity refers to the two n-cubes q4nu and q6np induced by s, see figure let c = |{v'| c = 2}| be the cardinality of the set of sequences in compatible distance two. then the degree of local connectivity of s at v is given by ds=|{v′|c= n=4}|c2− in other words, ds is the fraction of locally connected vertices of the compatible distance two neighbors of v, that can be obtained via a neutral path of length at most four. we perform the following experiment: we consider neutral walks for the utr-pseudoknot structure of the mouse hepatitis virus displayed in figure see subsection. along these walks we compute the locality degree ds and the total number of locally connected sequences. our findings are presented in figure we can report that the degree of local connectivity is, as suggested by random graph theory, almost 100%.  rna pseudoknot structures-in particular their statistical properties-are a fascinating and new territory. to our knowledge the only statistical data beyond rna secondary structures were derived for bi-secondary structures in. the structural concept of k-noncrossing canonical rna structures and the resulting sequence to structure map employed for our experiments is new and represents a natural generalization of rna secondary and bi-secondary structures. to be precise, bi-secondary structures are exactly planar 3-noncrossing rna structures. it is clear, that for sequence-length less than or equal to we only encounter pseudoknots of limited complexity. our findings presented in figure provide a transparent picture of which pseudoknot-shapes dominate for given sequence length. these results, in combination with the data on the fractions of pseudoknotted structures over sequence length show, that for n = we have approximately 35% structures with nontrivial pseudoknots. in addition it is striking that basically all folded structures are irreducible, i.e. only a very small fraction can be decomposed into several independent substructures. this is of interest since decomposable structures can be folded much faster. it is known, that dyck-paths, i.e. path starting at the origin, having only up, or down steps which end on the x-axis, decompose on average into three irreducible parts. this is of relevance, since a slight generalization of dyck-path, the motzkin-paths, having additional horizontal steps, correspond to secondary structures. our findings suggest, that while secondary structures, decompose nontrivially, higher and higher crossing numbers change the picture. this complicates the computation of mfe-pseudoknot rna due to their imminent irreducibility. both versions of cross produce analogous findings, confirming the generality of our results. the vast majority of pseudoknot-shapes is of a single type. as expected, cross exhibits more structural variety due to the fact that its minimum stack-length is only three. the ratio of pseudoknot structures shifts significantly from n = to n = to approximately 50%. we can conclude from this that pseudoknots cannot be ignored, they evidently become the dominant structure class for n greater than or equal to figure shows that the fraction of sequences for which cross and cross coincide, decreases linearly as a function of sequence length. this indicates that larger and larger sequences will exhibit more subtle structural elements whose emergence is facilitated by stabilizing large stacks. furthermore, the mfe-pseudoknot structures generated by cross are far from being random. the central limit theorems for random k-noncrossing canonical rna structures, given in table imply, that stacks and consequently loops scale linearly with the sequence length. figure clearly shows that the mfe-structures, generated by cross and cross have for n = two stacks less than random 3-noncrossing structures with minimum stack-length greater than four and five, respectively. this deviation is significant and indicates that mfe-pseudoknot structures are far from "typical" random structures. we remark that, while it is straightforward to generate random rna secondary structures, it is nontrivial to obtain random pseudoknot structures. in particular, at present time, no polynomial time algorithm is known which generates a random 3-noncrossing rna structure with uniform probability. the organization of the sequences contained in neutral networks of rna pseudoknot structures seems to be very analogous to the neutral networks of rna secondary structures. figure shows that neutral walks can effectively traverse sequence space and the fractions of neutral neighbors, presented in figure and figure suggest a high degree of neutrality. we discussed in subsection local connectivity, a property of neutral networks which implies the existence of short, neutral paths. it is apparent that local connectivity is of central importance for molecular evolution and any type of evolutionary optimization. it has been shown in that local connectivity is a prerequisite for preserving any type of sequence specific information. having a random graph threshold value localized at 1/n, local connectivity appears much later than connectivity, being localized at 1/n. however, the high neutrality degrees of rna pseudoknot structures of figure and figure imply locally connected neutral networks. our findings for the utr-pseudoknot structure of the mouse hepatitis virus of length given in figure confirm the local connectivity of neutral networks of particular pseudoknot rna structures. at all steps of the neutral walks almost all sequences are locally connected. list of abbreviations used utr: untranslated region; hdv: hepatitis delta virus; dp:dynamic program; lhs: left hand side; rhs: right hand side. competing interests the authors declare that they have no competing interests. authors' contributions all authors contributed equally to this paper. 
we study properties, like the fraction of pseudoknot structures, the dominant pseudoknot-shapes, neutral walks, neutral neighbors and local connectivity. our results imply that, in analogy to rna secondary structures, 3-noncrossing pseudoknot rna represents a molecular phenotype that is well suited for molecular and in particular neutral evolution. we can conclude that extended, percolating neutral networks of pseudoknot rna exist. after giving some background on rna pseudoknot structures and providing an outline of the folding algorithm being employed, we present in this paper various, statistical results on the mapping from rna sequences into 3-noncrossing rna pseudoknot structures. we then put our results into context of molecular evolution of rna. the analysis of sequence-structure relations of rna is based on a specific notion and folding of rna structure. these structures are folded by a novel, ab initio prediction algorithm, cross, capable of searching all 3-noncrossing rna structures.
 the analysis of sequence-structure relations of rna is based on a specific notion and folding of rna structure. the notion of coarse grained structure employed here is that of canonical rna pseudoknot contact-structures with at most two mutually crossing bonds. these structures are folded by a novel, ab initio prediction algorithm, cross, capable of searching all 3-noncrossing rna structures. the algorithm outputs the minimum free energy structure.  after giving some background on rna pseudoknot structures and providing an outline of the folding algorithm being employed, we present in this paper various, statistical results on the mapping from rna sequences into 3-noncrossing rna pseudoknot structures. we study properties, like the fraction of pseudoknot structures, the dominant pseudoknot-shapes, neutral walks, neutral neighbors and local connectivity. we then put our results into context of molecular evolution of rna.  our results imply that, in analogy to rna secondary structures, 3-noncrossing pseudoknot rna represents a molecular phenotype that is well suited for molecular and in particular neutral evolution. we can conclude that extended, percolating neutral networks of pseudoknot rna exist. 13– january the seventh asia pacific bioinformatics conference beijing, china 