Combinatorial Analysis For Pseudoknot RNA With Complex Structure

There exists many complicated k-noncrossing pseudoknot RNA structures in na-ture based on some special conditions. The special characteristic of RNA structuresgives us great challenges in researching the enumeration, prediction and the analysisof prediction algorithm. We will study two kinds of typical k-noncrossing pseudoknotRNAs with complex structures separately.The main content of Chapter1introduces the background and the significance ofthe project. We also present the chief results of this thesis.InChapter2,wemainlyillustratethebasicconcepts,includingthefollowingitems:1. The construction of RNA, containing the secondary structures, pseudoknotstructures and substructure of RNA.2. Symbolic enumeration method. It is one of the most important method forstudying the enumeration of RNA structures. All the generating functions areconcluded by this method.3. Combinatorial analysis, basic tool for asymptotically analyzing the enumera-tion of RNA structures. We mainly show D-finiteness, P-recursive, singularityanalysis and distribution analysis in detail.InChapter3,wediscussakindofcomplicatedstructuresnamedmodulark-noncrossingdiagram. Such diagrams frequently appear in RNA prediction. The prediction programbased on modular k-noncrossing diagram is much more difficult to code. Therefore, weneedtomakethediagramclear,includingthewayofbuildingitandthetimecomplexity we build. To reach the purpose, we invent a whole new method to enumerate and find the asymptotic behavior of modular κ-noncrossing diagrams. The method is made with reconstructing Vκ4-shape, recurrence, differential equation and symbolic method. Finally we get the result that the asymptotic formula of the number of modular, κ-noncrossing diagram with n nucleotides, which is, where γκ is the minimum real solution ofυ(z)=ρκ2and Cκ is some positive constant, see eq.(3.4.28).In Chapter4, we emphasize the research on κ-noncrossing skeleton structure, es-pecially when k=3. The skeleton structure is well known in Huang’s folding algorithm for3-noncrossing RNA structures. The algorithm constructs a skeleton tree first, in which every leaf is a skeleton structure. The structure of the skeleton tree is so com-plicated that the complexity of the algorithm is only concluded by experiment data in their paper. We will give a proof for the complexity and obtain the asymptotic formula of the number of canonical3-noncrossing skeleton diagrams with n vertices, where C’≈7892.16, η≈0.4934. Afterwards, we study the statistical properties of arcs in canonical3-noncrossing skeleton diagrams. We prove the central limit theorem for arcs distributions in terms of their bivariate generating function. Our result allows to estimate the arc numbers in a random canonical3-noncrossing skeleton diagrams.