RNA Structures: Tertiary Contacts And Interaction

This thesis mainly concerns some combinatorial and computational results on RNA tertiary structures and RNA-RNA interaction structures.The notion of k-noncrossing tangles, where k∈Z, arose from the study of ter-tiary structures in computational biology. It is well-known [14] that there exists a bijection between the set of k-noncrossing partitions of [n]={1,2,..., n} and the set of vacillating tableaux with less than k-rows of length n. In Chapter 2, we gen-eralize this result to tangles and give a proof in Section 2.3. Next, in Section 2.4, we exactly enumerate the set k-noncrossing tangles of [n] and give an asymptotic formula of our result via integral-representation method [18]. Furthermore, we introduce 2-regular, k-noncrossing partitions, which is a subclass of k-noncrossing tangles, as a combinatorial framework to facilitate the RNA tertiary structures with pscudoknots as well as base triples in Section 2.6 and then construct an algo-rithm to generate 2-regular, k-noncrossing partitions in linear time with uniform distribution. The main idea is to firstly interpret k-noncrossing partitions and 2-regular,k-noncrossing partitions as restricted generalized vacillating tableaux and then interpret the tableaux as sampling paths of a Markov-processes over shapes to derive their transition probabilities.In Chapter 3,4 and 5, we introduce a computational solution of RNA-RNA interaction problems, which is implemented by a C-program package named rip. The source code can be downloaded from http://www.combinatorics.cn/cbpc/rip.html.In Chapter 3, we first introduce the notion of joint structure as a combina-torial framework of the RNA-RNA interaction problems (RIP). Next, we derive a grammar rip1 that allows the unambiguous parsing of zigzag-free interaction structures, thus forming the basis for the computation of the partition function in O(N6) time and O(N4) memory, corresponding the minimal free energy (MFE) algorithm of Alkan et.al. [2]. Then we proceed by deriving the recursions for the base pairing probabilities, which are based on a conceptual reversing of the pro-duction rules. Indeed, one has to compute the pairing probabilities by explicitly "tracing back" all contributing joint structures.Next, in Chapter 4, we extend our previous framework rip1 to rip2 in two directions:(1) A modification of the underlying grammar explicitly treats hybrids, i.e., maximal regions with exclusively intermolecular interactions. This allows us to investigate local aspects in much more detail. (2) A stochastic brack-tracing algorithm, in analogy to similar approaches for RNA secondary structure prediction [17,52], which can be used to produce representative structure and to generate samples from the thermodynamic properties. These samples can be useful to assess complex structural features for which it would be too tedious or expensive to design and implement dedicated exact backtracing algorithms.Finally, since multiple sequence alignments of homologous RNA sequences improve the accuracy of RIP prediction by deriving the lowest free energy struc-ture consistent with every sequence-pair of the alignments,we extend rip2 as a software (rip3) for computing the partition function and block probabilities for RNA-RNA interaction structures based on a set of aligned RNA sequences in Chapter 5.