学位论文 > 优秀研究生学位论文题录展示

核糖核酸结构：三级联接与相互作用

作　者: 秦晶
导　师: Christian M. Reidys
学　校: 南开大学
专　业: 应用数学
关键词: tangle图徘徊杨表积分表示均匀分布目标预测 Boltzmann取样结合区间联合结构紧结构配分函数基因匹配概率多重序列比对
分类号: Q522
类　型: 博士论文
年　份: 2010年
下　载: 34次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要涉及核糖核酸(RNA)本身三级结构和核糖核酸之间相互作用结构的一些组合学和计算生物学的相关结果。假设k为正整数,k不相交tangle图这一组合概念起源于计算生物学对核糖核酸三级结构的研究。众所周知,在[14]中,陈永川教授等建立了集合[n]={1,2...,n}上的k不相交分拆与长度为n并且行数小于k的徘徊杨表(vacillating tableaux)集合之间的一一映射。在第二章中,我们将这一重要结论推广到k不相交tangle图上,并在第2.3节给出了相应的组合证明。然后,我们在第2.4节给出了集合[n]上k不相交tangle图一个计数公式,并且用积分表示方法[18]给出了相应的逼近结果。紧接着,我们以2正则、k不相交集合分拆作为刻画核糖核酸三级结构的数学模型,在第2.6节给出了一个按照均匀分布生成2正则、k不相交集合分拆的组合算法。该算法的空间和时间复杂度均为O(n)。算法的主要原理分为两个部分：首先利用第2.3节的一一映射,将集合分拆的生成问题转化为徘徊杨表的马尔可夫链的生成问题：然后通过格路上的一些计数结果得到相应的转移概率最终实现对马尔可夫链的生成。从第三章起,我们开始介绍关于核糖核酸相互作用结构的预测问题(RIP)。主要的研究成果是一个基于计算生物学的算法解决方案。这一解决方案相关的C程序代码可以从以下网址下载：http://www.combinatorics.cn/cbpc/rip.html.在第三章中,我们首先引入联合结构、紧结构等一系列新的图论概念作为研究核糖核酸相互作用的数学模型并围绕紧结构的特点对联合结构的一些图论特点进行分析。利用这些图论特点,我们设计了一个具有多项式复杂度计算RIP配分函数的动态递归算法rip1(空间复杂度：O(N4),时间复杂度：O(N6),N为序列长度)并通过对这个算法的回溯计算得到了基因匹配概率。在第四章中,我们通过对rip1的优化得到rip2。具体算法上的改进集中在以下两个方面：(1)计算hybrid这一具有生物学特殊意义的“子图”的概率进一步贴合了对核糖核酸相互作用的研究的需要,节省了生物实验的时间和物质成本。(2)引入Boltzmann取样这一兼具生物学和统计学双重意义的算法最终实现对核糖核酸相互作用生物结构的预测。第五章是在rip2的基础上进一步改进得到rip3,主要优点是根据一个核糖核酸的多重基因比对(multiple alignment)应当具有类似相互作用结构这一重要的生物进化学性质,考虑一对多重基因比对之间的相互作用,用类似加权平均的方法,得到相对于考虑单个核糖核酸之间相互作用更加可靠的预测结构。

全文目录

摘要  5-7
Abstract  7-11
1 Introduction  11-17
  1.1 RNA and its structures  11-14
  1.2 The RNA-RNA interaction problems  14-17
2 RNA tertiary contacts:tangles  17-50
  2.1 Young tableaux,RSK insertion and extraction  17-19
  2.2 Tangled diagrams and vacillating tableaux  19-22
  2.3 The bijection  22-29
  2.4 Enumeration  29-35
  2.5 Random k-noncrossing partitions  35-42
  2.6 Random 2-regular,k-noncrossing partitions  42-50
3 Partition function and basepair probabilities of RIP problem  50-77
  3.1 Mathematical model:joint structures  50-56
  3.2 The dynamic program of partition function  56-66
  3.3 Base pairing probabilities  66-70
  3.4 Computational result  70-77
4 Target prediction and a statistical sampling algorithm for RNA-RNA interaction  77-93
  4.1 The hybrid-grammar  77-84
  4.2 Hybrid-probabilities  84-86
  4.3 Boltzmann sampling  86-87
  4.4 Computational results  87-89
  4.5 Contrasting the rip1- and rip2-grammars  89-93
5 RNA-RNA interaction prediction based on multiple sequence alignments  93-107
  5.1 Multiple sequence alignments and compatibility  93-96
  5.2 Loop-energy of joint structures of alignments  96-97
  5.3 The grammar of canonical joint structures and the partition function  97-99
  5.4 Probabilities and the Boltzmann sampling  99-100
  5.5 Conclusion  100-107
Bibliography  107-113
Acknowledgement  113-115
Resume  115-116

核糖核酸结构：三级联接与相互作用

内容摘要

全文目录

相似论文