BACKGROUND: The neutral theory of Motoo Kimura stipulates that evolution is mostly driven by neutral mutations. However adaptive pressure eventually leads to changes in phenotype that involve non-neutral mutations. The relation between neutrality and adaptation has been studied in the context of RNA before and here we further study transitional mutations in the context of degenerate (plastic) RNA sequences and genetic assimilation. We propose quasineutral mutations, i.e. mutations which preserve an element of the phenotype set, as minimal mutations and study their properties. We also propose a general probabilistic interpretation of genetic assimilation and specialize it to the Boltzmann ensemble of RNA sequences. RESULTS: We show that degenerate sequences i.e. sequences with more than one structure at the MFE level have the highest evolvability among all sequences and are central to evolutionary innovation. Degenerate sequences also tend to cluster together in the sequence space. The selective pressure in an evolutionary simulation causes the population to move towards regions with more degenerate sequences, i.e. regions at the intersection of different neutral networks, and this causes the number of such sequences to increase well beyond the average percentage of degenerate sequences in the sequence space. We also observe that evolution by quasineutral mutations tends to conserve the number of base pairs in structures and thereby maintains structural integrity even in the presence of pressure to the contrary. CONCLUSIONS: We conclude that degenerate RNA sequences play a major role in evolutionary adaptation.

Motivation: DNA data is transcribed into single-stranded RNA, which folds into specific molecular structures. In this paper we pose the question to what extent sequence- and structure-information correlate. We view this correlation as structural semantics of sequence data that allows for a different interpretation than conventional sequence alignment. Structural semantics could enable us to identify more general embedded ‘patterns’ in DNA and RNA sequences. Results: We compute the partition function of sequences with respect to a fixed structure and connect this computation to the mutual information of a sequence–structure pair for RNA secondary structures. We present a Boltzmann sampler and obtain the a priori probability of specific sequence patterns. We present a detailed analysis for the three PDB-structures, 2JXV (hairpin), 2N3R (3-branch multi-loop) and 1EHZ (tRNA). We localize specific sequence patterns, contrast the energy spectrum of the Boltzmann sampled sequences versus those sequences that refold into the same structure and derive a criterion to identify native structures. We illustrate that there are multiple sequences in the partition function of a fixed structure, each having nearly the same mutual information, that are nevertheless poorly aligned. This indicates the possibility of the existence of relevant patterns embedded in the sequences that are not discoverable using alignments. Availability and Implementation: The source code is freely available at http://staff.vbi.vt.edu/fenixh/Sampler.zip Contact: [email protected] Supplimentary Information: Supplementary data are available at Bioinformatics online.

In this paper, we introduce plane permutations, i.e., pairs $\mathfrak{p}=(s,\pi)$, where $s$ is an $n$-cycle and $\pi$ is an arbitrary permutation, represented as a two-row array. Accordingly, a plane permutation gives rise to three distinct permutations: the permutation induced by the upper horizontal ($s$), the vertical ($\pi$), and the diagonal ($D_{\mathfrak{p}}$) of the array. The latter can also be viewed as the three permutations of a hypermap. In particular, a map corresponds to a plane permutation, in which the diagonal is a fixed-point free involution. We study the transposition action on plane permutations obtained by permuting their diagonal blocks. We establish basic properties of plane permutations and analyze transpositions and exceedances, deriving various enumerative results. In particular we prove a recurrence for the number of plane permutations having a fixed diagonal and $k$ cycles in the vertical, generalizing a recursion of Chapuy for maps filtered by the genus. As applications of this framework, we present a combinatorial proof of a result of Zagier and Stanley, on the number of $n$-cycles $\omega$, for which the product $\omega(1~2~\cdots ~n)$ has exactly $k$ cycles. Furthermore, we provide a unified framework for the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. Plane permutations allow us to generalize and recover various lower bounds for transposition and block-interchange distances and to connect reversals with block interchanges.

Contact:[email protected] It has come to our attention that several concepts and results underlying the gfold software presented in our article ‘Topology and prediction of RNA pseudoknots’ (Reidys et al., 2011) are also present in earlier work by Bon et al. (2008); Orland and Zee (2002); Pillsbury et al. (2005b); Vernizzi et al. (2005) and (Pillsbury et al., 2005a). Here, we briefly examine these works in relation to the results of our paper. The classification and expansion of pseudoknotted RNA structures in terms of the topological genus of an associated fatgraph or double line graph were first proposed by Orland and Zee (2002) and Bon et al. (2008), although fatgraphs were applied to RNA secondary structures already by Penner and Waterman (1993) and Penner (2004). The enumerative results initiated by Orland and Zee (2002) are based on matrix models, while our generating functions are derived via representation theory Zagier (1995). Enumeration results on RNA structures according to genus were already obtained by Vernizzi et al. (2005), again using the formal framework of the matrix model. Genus as well as other topological invariants of fatgraphs were introduced and studied as descriptors of proteins in Penner et al. (2010). Pillsbury et al. (2005a) report recursion relations of time complexity O(N6) to generate RNA structures of genus one in the context of an RNA folding algorithm that is substantially different from our algorithm gfold. Aside from not incorporating loop-based energy models, gfold is not restricted to genus one RNA structures. The four basic irreducible shadows of genus one in Theorem 2.3 of our paper appeared first in Pillsbury et al. (2005b; Bon et al. (2008). The shadows of Reidys et al. (2011) are derived from (i) the notion of irreducibility formulated by Kleitman (1970) and (ii) the work on pseudoknot shapes by Jin and Reidys (2009; Reidys and Wang (2010). Irreducibility is equivalent to the concept of primitivity introduced by Bon et al. (2008), inspired by the work of Dyson (1949). The equation to compute the genus of a fatgraph is classical going back to Euler (1752) and was first applied in the context representing RNA structures by Orland and Zee (2002) and Bon et al. (2008). Additivity of genus under topological sums is elementary (Massey, 1967) and for reducible and nested RNA structures first discussed by Bon et al. (2008). Our Equations (2.1), (2.2) and (2.4) are thus textbook knowledge. Lemma 2.1 is also well known and was used e.g. by Penner and Waterman (1993) and Bon et al. (2008). Funding: 973 Project of the Ministry of Science and Technology; the PCSIRT Project of the Ministry of Education; National Science Foundation of China to CMR and his lab, as well as the Deutsche Forschungsgemeinschaft, projects STA 850/2-1 & STA 850/7-1; the European Union FP-7 project QUANTOMICS (no. 222664) to P.F.S. and his lab. J.E.A. and R.C.P. are supported by QGM, the Centre for Quantum Geometry of Moduli Spaces, funded by the Danish National Research Foundation. Conflict of Interest: none declared.

MOTIVATION: Many computerized methods for RNA-RNA interaction structure prediction have been developed. Recently, O(N(6)) time and O(N(4)) space dynamic programming algorithms have become available that compute the partition function of RNA-RNA interaction complexes. However, few of these methods incorporate the knowledge concerning related sequences, thus relevant evolutionary information is often neglected from the structure determination. Therefore, it is of considerable practical interest to introduce a method taking into consideration both: thermodynamic stability as well as sequence/structure covariation. RESULTS: We present the a priori folding algorithm ripalign, whose input consists of two (given) multiple sequence alignments (MSA). ripalign outputs (i) the partition function, (ii) base pairing probabilities, (iii) hybrid probabilities and (iv) a set of Boltzmann-sampled suboptimal structures consisting of canonical joint structures that are compatible to the alignments. Compared to the single sequence-pair folding algorithm rip, ripalign requires negligible additional memory resource but offers much better sensitivity and specificity, once alignments of suitable quality are given. ripalign additionally allows to incorporate structure constraints as input parameters. AVAILABILITY: The algorithm described here is implemented in C as part of the rip package.

MOTIVATION: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered. RESULTS: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10-20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed. AVAILABILITY: The source code of gfold is freely available at http://www.combinatorics.cn/cbpc/gfold.tar.gz. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: It has been proven that the accessibility of the target sites has a critical influence on RNA-RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N(6)) time and O(N(4)) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA-RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties. RESULTS: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the 'hybrid probabilities' is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA-RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k.N(3)). AVAILABILITY: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The RNA-RNA interaction problem (RIP) consists in finding the energetically optimal structure of two RNA molecules that bind to each other. The standard model allows secondary structures in both partners as well as additional base pairs between the two RNAs subject to certain restrictions that ensure that RIP is solvabale by a polynomial time dynamic programming algorithm. RNA-RNA binding, like RNA folding, is typically not dominated by the ground state structure. Instead, a large ensemble of alternative structures contributes to the interaction thermodynamics. RESULTS: We present here an O(N(6)) time and O(N(4)) dynamics programming algorithm for computing the full partition function for RIP which is based on the combinatorial notion of 'tight structures'. Albeit equivalent to recent work by H. Chitsaz and collaborators, our approach in addition provides a full-fledged computation of the base pairing probabilities, which relies on the notion of a decomposition tree for joint structures. In practise, our implementation is efficient enough to investigate, for instance, the interactions of small bacterial RNAs and their target mRNAs. AVAILABILITY: The program rip is implemented in C. The source code is available for download from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html.

BACKGROUND: 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 (3-noncrossing). 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. RESULTS: 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. CONCLUSION: 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.