毕业设计（论文）-图的控制参数在RNA二级结构预测中的应用.pdf

中国科学技术大学本科毕业论文 1 目录： 中文内容摘要2 英文内容摘要3 第一章 引言4 1.1 rna 基因序列4 1.2 用图论方法描述 rna6 第二章 概念与方法8 2.1 rna 二级结构及其图表示8 2.2 图论的基本概念10 2.3 图的控制参数12 2.4 基于控制理论的参量18 2.5 统计方法验证参数有效性25 第三章 预测与分析28 3.1 寻找新型 rna 二级结构树28 3.2 设计和预测新型 9 阶树结构29 3.3 设计和预测新型 10 阶树结构32 3.4 汇总与结论34 第四章： 参考附录37 附录一： rna 树图的枚举公式37 附录二： 树图与双图的关系39 附录三： 树图表示 rna 二级结构的局限40 参考文献42 中国科学技术大学本科毕业论文 2 摘要摘要 理解 rna 分子对于基因研究工作至关重要。对 rna 结构与功能的研究是 当今生物信息学一个非常重要的课题，对 rna 自身功能的认识在当前已经得到 了极大的拓展和深入，而研究它更可以作为研究蛋白质结构与功能以及 dna 序 列中基因信息的突破口。在此文中，我们应用图的控制参数来定量的分析 rna 分子的二级结构，得到现存的十个结点以下 rna 结构树的普遍共性，从而预测 新 rna 的树结构。最后，对于图论应用到生物基因预测这一领域未来的研究发 展趋势作了大胆的展望。 关键词：控制数，图论，预测 rna 二级结构。 中国科学技术大学本科毕业论文 3 abstract understanding rna molecules is important to genomics research. recently researchers at the courant institute of mathematical sciences used graph theory to model rna molecules and provided a database of trees representing possible secondary rna molecules. in this thesis we use domination parameters to predict which trees are more likely to exist in nature as rna structures. this approach appears to have promise in graph theory applications in genomics research. keywords: domination, graph theory, predict rna secondary structure 中国科学技术大学本科毕业论文 4 第一章 引言 1.1 rna 基因序列 rna 分子是为完成蛋白质合成、运输、转录调节，染色体复制，rna 加 工与修改和其他基础生物机能的细胞结构整体的构成元素。随着对 rna 研究的 逐步深入，人们再也不像过去那样，仅仅把 rna 看成 dna 到蛋白质之间的一 种信息传递中介。rna 正在从人们眼中简单的、线性的、功能单一的形象演变 成今天种类多样、结构复杂、功能特异的新形象，并且逐渐在中心法则中取得了 与 dna 和蛋白质同等重要的地位。当编码蛋白质的基因结构变得相对容易鉴别 的时候，编码 rna 的基因目前还不好鉴别，加深对这些序列的了解，加快对结 构化功能 rna 的研究已经提上了议事日程。搞清楚 rna 的具体结构，不仅能 使我们更细致的了解各类 rna 在细胞中的运作机制，而且还可以为在基因组中 寻找基因，以及为提高蛋白质结构预测的准确率提供帮助。 rna 结构同蛋白质类似，也具有一级结构、二级结构、三级结构甚至四级 结构等形式，一级结构是指 rna 序列中四种核苷酸的不同排列顺序（图 1-1） ， 二级结构是指 rna 序列通过自身回折形成碱基配对的茎区(stem)以及不配对的 发卡环（hairpin loop） 、突环（bulge loop） 、多分支环（multi-branched loop）等 等（图 1-2） ，三级结构则是由各二级结构单元（motif）之间相互作用并在空间 中形成稳定的定位和取向而构成的（图 1-3） 。无论是蛋白质还是 rna，直接针 对其三级结构的理论预测， 目前进展都不是很顺利， 是当前结构预测的难点所在。 rna 结构实际上就是一组特定的碱基配对关系，给定一条 rna 序列，一 旦其中的碱基配对关系清楚了，那么它的结构也清楚了。面对当前海量的生物序 列，有些依靠实验的方法虽然精确但费力而且代价高昂。从而像蛋白质结构研究 一样，借助于计算机手段和各种数学方法从理论上去预测 rna 的空间结构，是 提高我们认识 rna 空间结构效率的一个捷径。 假设你手头上现有一条 rna 序列或者少数几条 rna 相关序列，为了预测 到可能构成的二级结构，可以使用目前最流行的一种算法最小自由能算法， 它自 1981 年由 zuker 提出并发展至今，其算法已经相当成熟，使用起来非常方 便，预测的精度有时能达到 90%以上，算是比较成功的，尤其是对于小分子的 rna。因为 rna 二级结构只需考虑序列在二维平面上的排布，这使得模型大大 中国科学技术大学本科毕业论文 5 简化了。它不仅仅着眼于序列自身内部碱基关系而且应用热力学中的能量参数 法：碱基配对的形成可以使 rna 分子的能量降低，结构更加稳定，因此最小自 由能算法认为在一定温度下，rna 分子通过构象调整达成某种热力学平衡，使 之自由能达到最小，形成最稳定的状态，此时的二级结构即被认为是 rna 的真 实二级结构。算法计算的对象是一套复杂的自由能参数。其基本思想就是针对各 种不同的 rna 基本结构单元并根据不同的碱基组成，分别用实验方法测出它们 的自由能，建立完整的自由能参数表。一个二级结构的自由能是组成它的各基本 结构单元的自由能之和且这些自由能之间是互不影响互补关联的， 然后用递推公 式来算出总体能量的全局最小值。 我们看使用 zucker 的 mfold 算法构造的 pr0021 结构。pr0021 由 nucleic acid 数据库 ndb 所定义，是具有如下碱基线性排列构成的 rna 单链序列（图 1-1） ； 详见 /ndb/index.html。 这条序列经过折叠形成如 下的二级结构 （图 1-2） ； 下图 （1-3） 是由 nucleic acid 数据库提供的一张 pr0021 分子三级结构的彩色视图。 图(1-3)：与蛋白质分子复合的 pr0021 三级结构 图(1-2)：二级结构举例 紫色为蛋白质分子 g g c u c u g u u u a c c a g g u c a g g u c c g a a a g g a a g c a g c c a a g g c a g a g c ccc 图 1-1：rna 序列举例 中国科学技术大学本科毕业论文 6 1.2 用图论方法描述 rna rna 的描述尽管有以上一些限制，核酶和模块化 rna 结构为新的概念和 数学方法提供了肥沃的土壤,。例如，我们在这里推出的图论的方法。事实上， 已有越来越多的人们认识到数学和计算机科学为结构生物学研究提供了良好的 工具。 生物学家丹尼斯近日宣称： 理论需要认可和接受， 并成为生物研究的主流。 量化和准确的预测，届时必然崛起。特别的，为解决一些限制现行办法的 rna 结构, 我们为探索 rna 的二级结构全体，开发了一个图论的方法，再加上建模 和计算生物学的工具。更多了解的 rna 的二级结构目录将为寻找新的 rna 提 供重要线索。目前国外的数学研究学者们开始使用图论来模拟 rna 分子的二级 结构,并且尝试用树图的多种性质来调查研究现存 rna 的拓扑结构，通过设计、 预测来寻找新 rna。我们可以这样示意地列举所有可能的二级结构代表的 rna 二级结构的平面图：用树图来代表 rna 的树状结构；双图代表任何 rna 二级结构包括树和假结。简单树的表示允许利用键图理论分析 rna；但要 求表示假结时，由于树型图比较简单，必须使用这些较复杂拓扑图形。rna 树 和双图都提供了二级 rna 结构单元的离散表示型。其中，rna 二级结构单元的 元素，诸如环，苞，茎，接合就用树图中的结点（）和边（）分别表示。所 有可能的二级 rna 的图案， 包括自然结构和理论推导都能用这类离散图形列举。 尽管 rna 树图早先是被 le et al.与 benedetti 2000. 8 h. gan, s. pasquali, t. schlick, exploring the repertoire of rna secondary motifs using graph theory; implications for rna design, nucleic acids research 2003, 31(11):2926-2943. 9 f. harary, g. prins, the number of homeomorphically irreducible trees and other species, acta math 1959, 101: 141-162. 10 r. durbin., s. eddy, biological sequence analysis: probabilistic models of proteins and nucleic acids. cambridge uk: cambridge university press, 1998. 11 d. fera, n. kim, n. shiffeldrim, j. zorn, u. laserson, h. gan, t. schlich, rag:rna-as-graphs web resource, bmc bioinformatics 2004, 5: 88. 12 h. h. gan, d. fera, j. zorn, n. shiffeldrim, u. laserson, n. kim, and t. schlick, rag: rna-as-graphs database-concepts, analysis and features, bioinformatics 2004, 20: 1285-1291. 13t. w. haynes, p. j. slater, paired-domination in graphs, networks 32 (1998) 中国科学技术大学本科毕业论文 43 199-206. 14c. j. colbourn, p. j. slater, and l. k. stewart, location-domination sets in series-parallel networks. congr. number. 56 (1987), 135-162. 15m. a. henning and o. r. oellermann, metric-locating-domination sets in graphs. to appear in ars combin. 16p. j. slater, leaves of trees. ars combin. 2 (1976),549-559. 17 n. trinajstic: chemical graph theory crc press; 1992. 18 j. yellen, j. gross,: graph theory and its applications crc press;1998. 19p. j. slater, dominating and location in acyclic graphs. networks 17 (1987), 55-64. 20a. finbow and b. l. hartnell, on locating dominating sets and well-covered graphs. congr. number. 65 (1988), 191-200. 21d. f. rall and p. j. slater, on location-domination numbers for certain classes of graphs. congr. number. 45 (1984), 97-106. 22p.j. slater, location dominating sets and locating-dominating sets. in y. alavi and a. schwenk, editors, graph theory, combinatorics, and applications, proc. seventh quad.