On RNA-RNA interaction structures of fixed topological genus.

Interacting RNA complexes are studied via bicellular maps using a filtration via their topological genus. Our main result is a new bijection for RNA-RNA interaction structures and a linear time uniform sampling algorithm for RNA complexes of fixed topological genus. The bijection allows to either reduce the topological genus of a bicellular map directly, or to lose connectivity by decomposing the complex into a pair of single stranded RNA structures. Our main result is proved bijectively. It provides an explicit algorithm of how to rewire the corresponding complexes and an unambiguous decomposition grammar. Using the concept of genus induction, we construct bicellular maps of fixed topological genus g uniformly in linear time. We present various statistics on these topological RNA complexes and compare our findings with biological complexes. Furthermore we show how to construct loop-energy based complexes using our decomposition grammar.

Combinatorics of γ-structures.

In this article we study canonical γ-structures, a class of RNA pseudoknot structures that plays a key role in the context of polynomial time folding of RNA pseudoknot structures. A γ-structure is composed of specific building blocks that have topological genus less than or equal to γ, where composition means concatenation and nesting of such blocks. Our main result is the derivation of the generating function of γ-structures via symbolic enumeration using so called irreducible shadows. We furthermore recursively compute the generating polynomials of irreducible shadows of genus ≤ γ. The γ-structures are constructed via γ-matchings. For 1 ≤ γ ≤ 10, we compute Puiseux expansions at the unique, dominant singularities, allowing us to derive simple asymptotic formulas for the number of γ-structures.

A phase transition in energy-filtered RNA secondary structures.

In this article we study the effect of energy parameters on minimum free energy (mfe) RNA secondary structures. Employing a simplified combinatorial energy model that is only dependent on the diagram representation and is not sequence-specific, we prove the following dichotomy result. Mfe structures derived via the Turner energy parameters contain only finitely many complex irreducible substructures, and just minor parameter changes produce a class of mfe structures that contain a large number of small irreducibles. We localize the exact point at which the distribution of irreducibles experiences this phase transition from a discrete limit to a central limit distribution and, subsequently, put our result into the context of quantifying the effect of sparsification of the folding of these respective mfe structures. We show that the sparsification of realistic mfe structures leads to a constant time and space reduction, and that the sparsification of the folding of structures with modified parameters leads to a linear time and space reduction. We, furthermore, identify the limit distribution at the phase transition as a Rayleigh distribution.

The 5'-3' distance of RNA secondary structures.

Recently, Yoffe and colleagues observed that the average distances between 5'-3' ends of RNA molecules are very small and largely independent of sequence length. This observation is based on numerical computations as well as theoretical arguments maximizing certain entropy functionals. In this article, we compute the exact distribution of 5'-3' distances of RNA secondary structures for any finite n. Furthermore, we compute the limit distribution and show that for n = 30 the exact distribution and the limit distribution are very close. Our results show that the distances of random RNA secondary structures are distinctively lower than those of minimum free energy structures of random RNA sequences.

Random K-noncrossing RNA structures.

In this paper, we introduce a combinatorial framework that provides an interpretation of RNA pseudoknot structures as sampling paths of a Markov process. Our results facilitate a variety of applications ranging from the energy-based sampling of pseudoknot structures as well as the ab initio folding via hidden Markov models. Our main result is an algorithm that generates RNA pseudoknot structures with uniform probability. This algorithm serves as a steppingstone to sequence-specific as well as energy-based transition probabilities. The approach employs a correspondence between pseudoknot structures, parametrized in terms of the maximal number of mutually crossing arcs and certain tableau sequences. The latter can be viewed as lattice paths. The main idea of this paper is to view each such lattice path as a sampling path of a stochastic process and to make use of D-finiteness for the efficient computation of the corresponding transition probabilities.

Stacks in canonical RNA pseudoknot structures.

In this paper we study the distribution of stacks/loops in k-non-crossing, tau-canonical RNA pseudoknot structures (k,tau-structures). Here, an RNA structure is called k-non-crossing if it has no more than k-1 mutually crossing arcs and tau-canonical if each arc is contained in a stack of length at least tau. Based on the ordinary generating function of k,tau-structures [G. Ma, C.M. Reidys, Canonical RNA pseudoknot structures, J. Comput. Biol. 15 (10) (2008) 1257] we derive the bivariate generating function T(k, tau)(x, u) = Sigma(n>or=0)Sigma(0

Pseudoknot RNA structures with arc-length > or =4.

In this article, we study k-noncrossing RNA structures with minimum arc-length 4 and at most k - 1 mutually crossing bonds. Let T(k)([4])(n) denote the number of k-noncrossing RNA structures with arc-length > or =4 over n vertices. We (a) prove a functional equation for the generating function summation operator(n> or =0) T(k)([4])(n)z(n) and (b) derive for 4 < or = k < or = 9 the asymptotic formula T(k)([4])(n) approximately c(k) n(-((k-1)(2)+(k-1)/2)) gamma(k)(-n). Furthermore, we explicitly compute the exponential growth rates gamma(k)(-1) and asymptotic formulas for 4 < or = k < or = 9.

DNA microarray reveals novel genes induced by mechanical forces in fetal lung type II epithelial cells.

Mechanical forces are essential for normal fetal lung development. However, the cellular and molecular mechanisms regulating this process are still poorly defined. In this study, we used oligonucleotide microarrays to investigate gene expression in cultured embryonic d 19 rat fetal lung type II epithelial cells exposed to a level of mechanical strain similar to the developing lung. Significance Analysis of Microarrays (SAM) identified 92 genes differentially expressed by strain. Interestingly, several members of the solute carrier family of amino acid transporter (Slc7a1, Slc7a3, Slc6a9, and tumor-associated protein 1) genes involved in amino acid synthesis (Phgdh, Psat1, Psph, Cars, and Asns), as well as the amiloride-sensitive epithelial sodium channel gene (Scnn1a) were up-regulated by the application of force. These results were confirmed by quantitative real-time PCR (qRT-PCR). Thus, this study identifies genes induced by strain that may be important for amino acid signaling pathways and protein synthesis in fetal type II cells. In addition, these data suggest that mechanical forces may contribute to facilitate lung fluid reabsorption in preparation for birth. Taken together, the present investigation provides further insights into how mechanical forces may modulate fetal lung development.