Enumeration Problems And Evolutionary Analysis Of RNA Secondary Structures

An RNA molecule is a single-stranded chain consisting of the nucleotides A, U, C, G. A nucleotide in one part of the molecule can be paired with a complementary nucleotide in another part, and thus the molecular folds to form secondary structures. Today, the research on the enumeration of RNA secondary structures is one of the hot topics in Computational Molecular Biology. RNA secondary structures are usually abstracted to discrete mathematic objects, which establishes a connection between Discrete Mathematics and Computational Molecular Biology. On the one hand, the skills of combinatorics enumeration have been successfully applied to the enumeration problems of RNA secondary structures. On the other hand, the enumeration problems of RNA secondary structures have inspired some new interesting combinatorial questions. In addition, there are abundant of data during the implement of Human Project. And it is a great challenge to analyze the phylogenetic relations among different species by choosing valid methods used to extract essential information. The core of this thesis is RNA secondary structures, and we mainly discusses the enumeration problems and the evolution relations. The main contents of this thesis can be summarized as follows:Chapter 2 describes some information of the RNA secondary structure in detail, including some elements of RNA secondary structures and various traditional representations, and makes a further discussion about the enumeration problem of RNA secondary structures with limited length of each loop using its generating function. Moreover, a method to compute S_m(n) is given.In order to specify the recurrence relations of RNA secondary structures with limited length of each loop, we establish one to one correspondences between the sets of secondary structures and three special sets in combinatorics in chapter 3. And an exact expression about secondary structures with k base pairs whose loop has at least m bases is obtained by one bijection.In chapter 4, a new representation is obtained based on the Watson-Crick principle, i.e., let circles to represent the bases A(U) and dots to represent the bases G(C). The representation is more reasonable and meaningful than the traditional representations. Based on the new representation, we make a new discussion by choosing the least length of loops and stacks as parameters.In the final chapter, we transform complex RNA secondary structures into linear symbolic sequences defined in 20 alphabet, and compute their LZ complexities. Furthermore, we obtain the phylogenetic trees using two different programmes. The results adequately indicate the validity of our method.