Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTopology of RNA-RNA interaction structures
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The topological filtration of interacting RNA complexes is studied and the role is analyzed of certain diagrams called irreducible shadows, which form suitable building blocks for more general structures. We prove that for two interacting RNAs, called interaction structures, there exist for fixed genus only finitely many irreducible shadows. This implies that for fixed genus there are only finitely many classes of interaction structures. In particular the simplest case of genus zero already provides the formalism for certain types of structures that occur in nature and are not covered by other filtrations. This case of genus zero interaction structures is already of practical interest, is studied here in detail and found to be expressed by a multiple context-free grammar extending the usual one for RNA secondary structures. We show that in $O(n^6)$ time and $O(n^4)$ space complexity, this grammar for genus zero interaction structures provides not only minimum free energy solutions but also the complete partition function and base pairing probabilities.
rate research
Read More
RNA-RNA binding is an important phenomenon observed for many classes of non-coding RNAs and plays a crucial role in a number of regulatory processes. Recently several MFE folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Here joint structure means that in a diagram representation the intramolecular bonds of each partner are pseudoknot-free, that the intermolecular binding pairs are noncrossing, and that there is no so-called ``zig-zag configuration. This paper presents the combinatorics of RNA interaction structures including their generating function, singularity analysis as well as explicit recurrence relations. In particular, our results imply simple asymptotic formulas for the number of joint structures.
In this paper we study $k$-noncrossing, canonical RNA pseudoknot structures with minimum arc-length $ge 4$. Let ${sf T}_{k,sigma}^{[4]} (n)$ denote the number of these structures. We derive exact enumeration results by computing the generating function ${bf T}_{k,sigma}^{[4]}(z)= sum_n{sf T}_{k,sigma}^{[4]}(n)z^n$ and derive the asymptotic formulas ${sf T}_{k,3}^{[4]}(n)^{}sim c_k n^{-(k-1)^2-frac{k-1}{2}} (gamma_{k,3}^{[4]})^{-n}$ for $k=3,...,9$. In particular we have for $k=3$, ${sf T}_{3,3}^{[4]}(n)^{}sim c_3 n^{-5} 2.0348^n$. Our results prove that the set of biophysically relevant RNA pseudoknot structures is surprisingly small and suggest a new structure class as target for prediction algorithms.
A topological RNA structure is derived from a diagram and its shape is obtained by collapsing the stacks of the structure into single arcs and by removing any arcs of length one. Shapes contain key topological, information and for fixed topological genus there exist only finitely many such shapes. We shall express topological RNA structures as unicellular maps, i.e. graphs together with a cyclic ordering of their half-edges. In this paper we prove a bijection of shapes of topological RNA structures. We furthermore derive a linear time algorithm generating shapes of fixed topological genus. We derive explicit expressions for the coefficients of the generating polynomial of these shapes and the generating function of RNA structures of genus $g$. Furthermore we outline how shapes can be used in order to extract essential information of RNA structure databases.
In this paper we study properties of topological RNA structures, i.e.~RNA contact structures with cross-serial interactions that are filtered by their topological genus. RNA secondary structures within this framework are topological structures having genus zero. We derive a new bivariate generating function whose singular expansion allows us to analyze the distributions of arcs, stacks, hairpin- , interior- and multi-loops. We then extend this analysis to H-type pseudoknots, kissing hairpins as well as $3$-knots and compute their respective expectation values. Finally we discuss our results and put them into context with data obtained by uniform sampling structures of fixed genus.
In this paper we study the distribution of stacks in $k$-noncrossing, $tau$-canonical RNA pseudoknot structures ($<k,tau> $-structures). An RNA structure is called $k$-noncrossing 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 cite{Reidys:08ma} we derive the bivariate generating function ${bf T}_{k,tau}(x,u)=sum_{n geq 0} sum_{0leq t leq frac{n}{2}} {sf T}_{k, tau}^{} (n,t) u^t x^n$, where ${sf T}_{k,tau}(n,t)$ is the number of $<k,tau>$-structures having exactly $t$ stacks and study its singularities. We show that for a certain parametrization of the variable $u$, ${bf T}_{k,tau}(x,u)$ has a unique, dominant singularity. The particular shift of this singularity parametrized by $u$ implies a central limit theorem for the distribution of stack-numbers. Our results are of importance for understanding the ``language of minimum-free energy RNA pseudoknot structures, generated by computer folding algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
