Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA combinatorial framework for RNA tertiary interaction
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we show how to express RNA tertiary interactions via the concepts of tangled diagrams. Tangled diagrams allow to formulate RNA base triples and pseudoknot-interactions and to control the maximum number of mutually crossing arcs. In particular we study two subsets of tangled diagrams: 3-noncrossing tangled-diagrams with $ell$ vertices of degree two and 2-regular, 3-noncrossing partitions (i.e. without arcs of the form $(i,i+1)$). Our main result is an asymptotic formula for the number of 2-regular, 3-noncrossing partitions, denoted by $p_{3,2}(n)$, 3-noncrossing partitions over $[n]$. The asymptotic formula is derived by the analytic theory of singular difference equations due to Birkhoff-Trjitzinsky. Explicitly, we prove the formula $p_{3,2}(n+1)sim K 8^{n}n^{-7}(1+c_{1}/n+c_{2}/n^2+c_3/n^3)$ where $K,c_i$, $i=1,2,3$ are constants.
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.
There exists many complicated $k$-noncrossing pseudoknot RNA structures in nature based on some special conditions. The special characteristic of RNA structures gives us great challenges in researching the enumeration, prediction and the analysis of prediction algorithm. We will study two kinds of typical $k$-noncrossing pseudoknot RNAs with complex structures separately.
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.
Recently several minimum free energy (MFE) folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Their folding targets are interaction structures, that can be represented as diagrams with two backbones drawn horizontally on top of each other such that (1) intramolecular and intermolecular bonds are noncrossing and (2) there is no zig-zag configuration. This paper studies joint structures with arc-length at least four in which both, interior and exterior stack-lengths are at least two (no isolated arcs). The key idea in this paper is to consider a new type of shape, based on which joint structures can be derived via symbolic enumeration. Our results imply simple asymptotic formulas for the number of joint structures with surprisingly small exponential growth rates. They are of interest in the context of designing prediction algorithms for RNA-RNA interactions.
In this paper we enumerate $k$-noncrossing RNA pseudoknot structures with given minimum stack-length. We show that the numbers of $k$-noncrossing structures without isolated base pairs are significantly smaller than the number of all $k$-noncrossing structures. In particular we prove that the number of 3- and 4-noncrossing RNA structures with stack-length $ge 2$ is for large $n$ given by $311.2470 frac{4!}{n(n-1)...(n-4)}2.5881^n$ and $1.217cdot 10^{7} n^{-{21/2}} 3.0382^n$, respectively. We furthermore show that for $k$-noncrossing RNA structures the drop in exponential growth rates between the number of all structures and the number of all structures with stack-size $ge 2$ increases significantly. Our results are of importance for prediction algorithms for pseudoknot-RNA and provide evidence that there exist neutral networks of RNA pseudoknot structures.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
