（计算数学专业论文）rna二级结构的计数.pdf

大连理工大学硬士学位论文 摘要 r n a 是由四种普通的核苷酸( 腺嘌呤a 、鸟嘌呤g 、胞嘧啶c 和尿嘧啶u ) 组成 单链的r n a 分子通过自身回折，使链中分子中的一部分核苷酸可与其它部分核苷酸互 补配对，即r n a 的二级结构 根据r n a 的结构与功能的关系，在预测碱基配对的类型方面进行了相当多的研究 这也是确定r n a 三维构象的必不可少的一部分组合学和统计学的工具和方法在研究 生物序列和生物结构上起到了很大的作用同样我们可以用几何方法来表示生物序列和 二级结构，几何拓扑和群论也起到了很大的作用 所谓二级结构的预测，就是计算给定长度的r n a 序列的最优结构目前所有有关 r i g a 二级结构的预测算法要预测出所有序列的二级结构仍然很困难，所以自然估计给定 长度的所有可能的二级结构数则成了数学任务本文主要是利用组合的技巧对r i g a 二级 结构计数进行了更迸一步的讨论主要工作如下z 第一部分：简单介绍了分子生物学的一些基础知识，包括常用的术语和基本概念都 在这里做了简要的介绍 第二部分：接着介绍了r n a 二级结构预钡! 基本原理、表示方法及其子结构的定义， 最后应用组合的技巧解决r n a 二级结构及子结构计数的一般情形 第三部分：r i g a 二级结构是由一些环和茎组成的结构在此基础上，本节以端环中 自由基数为参量，我们又利用组合技巧解决了一类r n a 二级结构的计数并给出了它们的 近似值 关键词：r n a 二级结构；递归公式；环；组套；组合计数 b n a 二级结构的计数 t h ee n u m e r a t i o no fr n a s e c o n d a r ys t r u c t u r e a b s t r a c t r n am o l e c u l a ri sc o m p o s e do ft h ef o u rn u c l e o t i d sa ，c ，g i u r n as e c o n d a r ys t r u c t u r e i sas i n g l e - s t r a n d e dc h a i no ft h eu u c l e o t i d ei nw h i c hp a r to ft h em o l e c u l ec a nb a s e - p a i rw i t ha c o m p l e m e n t a r yn u c l e o t i d ei na n o t h e rp a r tb yf o l d i n go n e s e l f b a s e do nt h er e l a t i o n s h i pb e t w e e nt h es t r u c t u r ea n df u n c t i o n al o to fr e s e a r c hh a v e b e e np e r f o r m e do np r e d i c t i n gb a s e - p a i rw h i c hi si n d i s p e n s a b l et ot h e 冗at h r e e - d i m e n s i o n a l s t r c u t r u e t h et o o l sa n dm e t h o d si nc o m b i n a t o r i c sa n ds t a t i s t i c sw i l lp l a yi m p o r t a n tr o l e si n s t u d y i n gl i n e a rs e q u e n c e so fb i o m o l o c u l a ru n i t s s i m i l a r l y , w ec a np r e s e n tt h eg e o m e t r i cr e p r e - s e n t a t i o no fb i o l o g i c a ls e q u e n c e sa n ds t r u c t u r e s s ot h eg e n o m e t r i ct o p o l o g ya n dg r o u pt h e o r y a mi m p o r t a n ta l s o p r e d i c t i n ga l lt h er n as e c o n d a r ys t r u c t u r e si st oc a l c u l a t e t h e b e s ts t r u c t u r e so ft h e s e q u e n c e so fg i v e nl e n g t h a tp r e s e n ti t i sv e r yd i f f i c u l tt op r e d i c t a l lt h er as e c o n d a r y s t r u c t u r e s s oi t i st h em a t h e m a t i c a lm i s s i o nt op r e d i c ta 1 1t h er n as e c o n d a r ys t r u c t u r e so f g i v e nl e n g t h t h i st h e s i sm a i n l ym a k eaf u r t h e rd i s c u s s i o na b o u tt h ee n u m e r a t i o no fr n a s e c o n d a r ys t r u c t u r e t h em a i nc o n t e n t so ft h et h e s i sc a nb es u m m a r i z e da sf o l l o w s ： i nc h a p t e r2 ，w ei n t r o d u c es o m eb a s i ck n o w l e d g eo fm o l e c u l a rb i o l o g y m o s to ft h et e r m s a n dc o n c e p t su s e di nt h i sp a p e ra y ee x p l a i n e db r i e f l yh e r e i nc h a p t e r3 ，s o m ei n f o r m a t i o no ft h er n a s e c o n d a r ys t r u c t u r ei si n t r o d u c e di nd e t a i l ， s u c ha sd e n o t a t i o no fr n a ，t h ec a r d i n a ip r i n c i p l e ，s o m eb a s i cd e f i n i t i o n sa n ds oo n t h e na c o m m o ne n u m e r a t i o np r o b l e mo fr as e c o n d a r ys t r u c t u r ea n ds u b s t r u c t u r ei ss t u d i e dw i t h t h em e t h o do fc o m b i n a t o r i a le n u m e r a t i o n i nc h a p t e r4 ，t h e r ea r et w oi m p o r t a n ts t r u c t u r e s ，l o o p sa n ds t a c k sf o ra na b s t r a c ts i n g l e - s t r a n dr a b a s e do nt h em e t h o do fc o m b i n a t o r i a le n u m e r a t i o n ，w em a k ean e wd i s c u s s i o n a b o u tt h ee n u m e r a t i o np r o b l e ma n dg e ti t sa p p r o x i m a t i o nw i t ht h el i m i t e dl e n g t ho fe n dl o o p k e y w o r d s ：r n as e c o n d a r ys t r u c t u r e ；r e c u r s i o nf o r m u l a ；l o o p s ；s t a c k s ；c o m b i n a - t o r i a le n u m e r a t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的贡献均已在论文中做了明确的说明并表示了澍意。 作者签名；i 弛芝一日期：盈址 大连理工大学硬士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完垒了解呋连理工大学硕士、博士学位论文版权使用 规定，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 。缸 导师貅逑亟导师签名；翌堡墼 皿上1 a 大连理工大学硕士学位论文 分子生物学这个术语首先在1 9 8 3 年被w a r r e nw e a v e r 使用它是2 0 世纪发展最快 的学科和领域之一随着人们对生物大分子序列操纵能力的增强，科研工作已经产生并 仍在产生大量的数据然而，由于数据的规模和复杂性，从创造到使用这些数据都需要 多学科特别是数学和计算机科学的参与这种要求产生了一个新的领域，通常叫做计算 分子生物学 计算分子生物学是数学、计算机科学和生物科学交叉的新兴领域之一它是一个十 分活跃的研究领域，它致力于应用可计算的技术研究生物学问题，包括存储，抽取和分 析生物学数据，如核酸( d n a r n a ) 、蛋白质序列、结构、功能、调控网络等计算分 子生物学的研究对象是与基因和蛋白质序列有关的组合和计算问题，计算分子生物学的 主要课题有：序列组合，序列分析【1 ，引，生物信息资料库，基因认定，种族树的构建以及 分子结构预测等 分子的结构决定分子的性质和分子的功能研究分子结构，有助于了解分子的作用， 了解分子如何行使其生物功能，认识分子与同种分子( 或其它分子) 之间的相互作用， 这无论是对于生物学还是对于医学和药学，都是非常重要的自2 0 世纪8 0 年代发现核 酶后，人们再也不象过去那样，仅仅把r n a 看成d n a 到蛋白质之间的一种信息传递中 介r n a 正在从人们眼中简单的、线性的、功能单一的形象演变成今天种类多样，结构 复杂，功能特异的新形象，并且逐渐在中心法则中取得了与d n a 和蛋白质同等重要的地 位r n a 多种全新的生物功能被发现，如它的催化功能，携带与调控遗传信息的功能， 信号分子的功能，运动功能等人们开始相信在生命起源过程中的某个时期，曾经有过 一个由r n a 组成的生命世界，也就是人们所提出的“r n a 世界”的假说1 3 】r n a 分子 能够通过碱基互补与同一分子的其它部分结合，即r n a 二级结构我们通过研究r n a 的二级结构来获得更多有关其功能的知识 r n a ( r i b o n u c l e i ca c i d ) 是具有重要生物学功能的一种核酸，其含量在原核细胞中约 占6 ，在真核细胞中约占1 1 。它是由核昔酸小分子生成的聚合物核苷酸有四种，可 以用四种基来区分他们四个基分别是a ，g ，g ，u r n a 分子可以看成是四卟字母字符集 k = a ，a g ，吩上的词a 与u 以及g 与c 分别形成配对一个典型的细胞含有 的r n a 量是d n a 的1 0 倍r n a 的高含量主要是因为r n a 在细胞中扮演了大量不 同的角色 r n a 主要有三种基本类型：核糖体r n a ( r r j q a ) 、转移r n a ( t r n a ) 以及信 使r n a ( m r n a ) 其中r r n a 的丰度最大r r n a 在核糖体中的催化机制和构成作用、 m r n a 自身的稳定性及其翻译效率、r n a 酶对t r n a 和r r n a 的转录后加工、等等一系 列问题都在促使着人们对r n a 的具体结构更深一步的了解 r n a 二级结构的计数 为了更好的了解r n a 的功能，解读遗传密码，就需要剖析r n a 的结构目前理解 r n a 的空间结构成为分子生物学的最重要的目标而r n a 三级结构是在二级结构基础 上，再折叠形成的三度空间的高级结构由于r n a 分子具有降解速度快，难以结晶等特 点，故通过x 射线结晶衍射和核磁共振确定生物分子的三维结构很不容易，这样费时费 力还代价高昂，虽然测得的结果比较精确可靠，可是面对当前大量的生物序列，这种方 法显然并非总是可行的，这与确定生物分子的一级结构( 如r n a 中的碱基和蛋白质中的 氨基酸) 的相对容易形成了鲜明对照，其后果是形成目前的序列知识与结构知识之间的 鸿沟如我们已知道几千种蛋白质的序列，僵仅知道几百种蛋白质的三维结构，且该鸿 沟每年都在不断的扩大因此加大了结构预测的方法的研寇 r n a 二级结构的预测较为著名的方法有t 碱基最大配对方法，基于螺旋区所有可能 组合的r n a 二级结构预测【4 】和z u k e r 极小化自由能方法等 5 , e l ，并编写了程序，预测了 许多r n a 分子的二级结构不过许多预测结果与试验结果常有出入。特别是r n a 大分 子和带假结的r n a 分子的二级结构结构预测首先要处理好的两个问题是：结构数的估 计和能量的处理从而，本文主要是应用了组合的技巧讨论了关于r n a 二级结构的计数 问题 二十世纪的七八十年代，w a t e r m a n 及其合作者曾对这一课题做了大量的研究1 7 - 1x l ， 也为以后奠定了坚实的基础本文主要是根据w a t e r m a n 等的论证，对k n a 二级结构计 数进行了更进一步的讨论本文的主要工作共分三部分： 第一部分：简单介绍了分子生物学的一些基础知识，包括常用的术语和基本概念都 在这里做了简要的介绍 第二部分：接着介绍了r n a 结构的表示方法及子结构的定义，最后应用组合的技巧 解决r n a 二级结构及子结构计数的一般情形 第三部分：r n a 二级结构是由一些环和茎组成的结构在此基础之上，我们又利用 组合技巧对r n a 二级结构计数问题作出了新的讨论 2 大连理工大学硕士学位论文 2 分子生物学的基本概念 分子生物学是实验学科，在分子水平上研究生物的结构、组织和功能的科学广义 的说，分子生物学主要包括分子生物学技术、分子生物学技术的应用及这些技术研究所 取得的理论成就等方面狭义的讲，分子生物学的范畴偏重于核酸( 或基因) 的分子生物 学，主要研究基因或d n a 的复制、转录、翻译和调控等过程分子生物学是在各门生物 分支学科发展的基础上建立起来的新学科，其后随着发展的新理论和新技术又为研究各 种生物学现象鉴定了坚实的分子基础 细胞是生命的基本单位一个典型的细胞包含1 0 4 1 0 5 个不同种类的分子这些 分子约一半都是小分子，它们的相对质量通常不超过7 0 0 其他的分子是一些大的聚合 体，它们的相对分子质量范围是1 0 4 1 0 1 2 ，被称为大分子这些分子主要有三种类型： d n a 、r n a 和蛋白质它们是由某些小分子聚合在一起而形成的这些生物大分子行使 各种不同的生理功能，使细胞维持各种各样的生命活动d n a 的遗传信息决定了生命的 主要性状，而m r n a 在信息传递中起很重要的作用，其它两大类r n a ：r r n a 和t r n a ， 同样在蛋白质的生物合成中发挥着不可替代的重要功能下面讨论大分子的性质以及结 构，包括怎样由d n a 生成r n a 和蛋白，以便能从容应对本文中涉及的生物学背景【1 2 】 2 1 核酸 核酸( n u c l e i ca c i d ) 是生物体的基本组成物质，是遗传信息的携带者，它在生物的个 体生长、发育、繁殖、遗传和变异等生命过程中起着极为重要的作用生物体包含两类 核酸：核糖核酸( r i b o n u c l e i ca c i d ) ，简写为r n a ；脱氧核糖核酸( d e o x y r i b o n u c l e i ca c i d ) ， 简写为d n a 2 1 1d n a d n a ( d e o x y r i b o n u c l e i ca c i d ) 是遗传特征的基础，它是由核苷酸小分子生成的聚合物 实际上d n a 分子是双链结构两条链缠绕在一起形成双螺旋，此著名的双螺靛( d o u b l e h e l i x l 结构是由j a m e sw a t s o n 和f r a n c i sc r i c k 在1 9 5 3 年发现的先认识一下d n a 的单 链( s t r a n d ) ，它是由重复的基本单元按照一定的方式、数量和排列顺序而形成的骨架这 种基本单元由一个称做2 脱氧核糖的糖分子和一个磷酸残基组成糖分子含有5 个碳 原子，标记为1 - - - + 5 7 ( 图2 1 ) 形成骨架的键是在一个单元的3 。碳原子和下一个单元的 5 碳原子之间因此，d n a 分子具有方向性( o r i e n t a t i o n ) ，一般从5 1 开始到3 + 结束， 3 r n a 二级结构的计数 国8 。n 8 n j 核糖2 脱氧核糖 图2 1 核酸中的糖，符号1 _ 5 表示碳原子两种糖的唯一差别是 2 碳原子中的氧。r n a 中是核糖d n a 中是脱氧核糖 在骨架中与1 碳原子相连的分子为碱基( b a s e ) 在d n a 分子中有4 种碱基，分别是：腺 嘌呤( a d e n i n e ，a ) 、鸟嘌呤( g u a n i n e ，g ) 、胞嘧啶( c y t o s i n e ，c ) 和胸腺嘧啶( t h y m i n e ， t ) 图2 2 显示了每种碱基的分子结构，图2 3 为单链d n a 分子的示意图碱基a 和g 是嘌呤，而碱基c 和t 属于嘧啶d n a 分子的基本单元由糖、磷酸和碱基组成，该基 本单元谓之核苷酸( n u c l e o t i d e ) h i 嘲a r 一( 。匝回 h 襞v f 一，h h 气。二n 7 厩o - - - 广h 臣围舾 图2 2d n a 中氮化的碱基，两种w a t s o n c r i c k 配对，注意腺嘌呤与胸腺嘧啶、鸟嘌岭与胞嘧啶之 间所形成的键，图中用点线表示 图2 3 一个d n a 链分子结构的图示 4 尸飞广i 一 大连理工大学硬士学位论文 d n a 蕴含的复制机制的关键特征是碱基互补即a 和t 配对，g 和c 配对这种 配对是由于氢键作用如图2 4 所示 图2 4 双链d n a 链分子结构的图示 由图2 4 我们能看出，在a t 配对时，有两个氢键连接，而在g c 配对时有三个 氢键连接因此，我们把a ，t 称谓弱氢键碱基而把g ，c 称为强氢键碱基 通常可以把d n a 看成是字符集n = a ，c ，g ，t ) 上的字符串，每一个字符代表一个 碱基原理是d n a 单个链( 按5 到3 的次序) 5 agtgagt gc3 与相反方向写的互补的链配对 5 hc l 3 t tg 这种碱基互补配对的机制使得d n a 在细胞中得以复制三维结构是螺旋状，下面图 指出这些字母或基是附在一个线上或骨架上注意，标明氢键的杠删去了为准确地看 这个图，把它想象为两个边是对应骨架的缎带拧成一个螺旋状如图2 5 5 3 5 c i g g l c t a c g a 1 t 0 1 c t l a r n a 二级结构的计数 2 1 2r n a 图2 5d n a 的三维结构 一个典型的细胞含有的r n a 量是d n a 的1 0 倍r n a 分子与d n a 分子很相似， 但在组成和结构上也有一些重要的不同在r n a 分子中，核糖取代了d n a 分子中的2 脱氧核糖另外，胸腺嘧啶t 被u 取代了，u 与t 样能够与a 配对还有r n a 分子 并不形成双螺旋有时我们可以看到r n a d n a 杂交双螺旋此外，r n a 能够通过碱基 互补与同一分子的其他部分结合r n a 的三维结构远比d n a 复杂d n a 与r n a 的另 一个不同是，d n a 本质上仅有一个功能，即编码信息，而在细胞中有不同的r n a ，各自 行使不同的功能 r n a 的种类主要有核糖体r n a ( r r n a ) 、转移r n a ( t r n a ) 以及信使 r n a ( m r n a ) 它们的主要功能是参与蛋白质的生物合成近年来发现的反义r n a 、具 有催化作用的r n a ( r i b o z y m e ) 、细胞核小分子r n a ( s n r n a ) 、核仁小分子r n a ( s n o r i n a ) 等亦都具有重要的生物学功能和广阔的应用前景 要更好的了解r n a 的功能，就需要分析r n a 的结构r n a 二级结构可以简单地 认为是形成三维结构的一个中间步骤r n a 二级结构由双链r n a 区域组成，这些双 链r n a 区域是通过单链分子内自身折叠形成的为了产生这样的双链区，r n a 序列 下游区域一连串碱基必须和另一个上游区域互补，使得互补的核苷酸g c 和a u 产生 w a t s o n c r i c k 碱基人们已经根据已解析的r n a 结构，识别出这些碱基对和其他一些 碱基对 1 3 】 r n a 分子同样可以看作是字符集q a ，c ，g ，u 上的字符串同样具有方向性的， 左端通常记为5 ，另一端记为3 在r n a 分子中a 与u 配对，g 和c 配对构成r n a 二级结构r n a 二级结构是平面图，磷酸骨架用实线表示，基用点表示，氢键或基对 表示为两个非相邻间的线，在二级结构的通常的生物学表示中基对线不与基连接对于 口：c a g c a u c a c a c c c g c g g g g u a a a c g c u 的所谓三叶草结构的一个例子，见图2 6 在图2 7 示出同样序列与同样的二级结构初级结构沿水平轴画出，基对用弧线表示 6 大连理工大学硕士学位论文 爨 2 2 蛋白质 c 图2 6 三叶草二级结构的一般表示 图2 7 三叶草二级结构的半圆表示 生物体的大部分物质是各种各样的蛋白质，他们既是工作部件，又是组成原料蛋 白质包括很多种，结构蛋白质是组织的构成单元，酶是化学反应的催化剂蛋白质的其 他功能还包括氧气输送和抗体防御等蛋白质是由一类称为氨基酸( a m i n oa c i d ) 的简单 分子组成图2 8 是氨基酸的例子，每一个氨基酸有一个中心碳原子，谓之“碳原子或 以连接1 个氢原子( h ) ，1 个氨基( 一n h 2 ) 、1 个羧基( - c o o h ) 和1 个侧链正是这 个决定了氨基酸间的差异 7 k n a 二级结构的计数 r 辆c a c o o h l h 丙氨酸 h 0 c 琏 。 c h l 如n 一吒一c o o h l h 苏氨酸 圈2 8 氨基酸的例子 在自然界中发现了2 0 种不同的氨基酸这些单元是a ( 丙氨酸) 、g ( 半胱氨酸) 、 d ( 天冬氨酸) 、e ( 谷氨酸) 、f ( 苯丙氨酸) 、g ( 甘氨酸) 、日( 组氨酸) 、j ( 异亮氨酸) 、 k ( 赖氨酸) 、五( 亮氨酸) 、m ( 甲硫氨酸) 、( 天冬酰氨酸) 、p ( 脯氨酸) 、日( 谷氨酰氨 酸) 、尉精氨酸) 、s ( 丝氨酸) 、t ( 苏氨酸) 、y ( 颉氨酸) 、w i 色氨酸) 和y ( 酪氨酸) ，这 是蛋白质中最常见的2 0 种另外还有几种非标准的氨基酸表2 1 是2 0 种氨基酸的一个 字母或三个字母的缩写表示以及氨基酸的遗传密码，蛋白质也有方向性 在蛋白质中，氨基酸通过肽键相连因此，蛋白质是多肽链肽链使得每个蛋白质都 有一个骨架( b a c k b o n e ) ，在骨架的一端是一个氨基酸，另一端是一个羧基我们因此可以 区别多肽链的两端，并给它定一个方向，习惯上多肽始于氨基( n 端) ，止于羧基( e 端) 蛋白质按外形和在生物组织中的位置和作用，可分为三大类：纤维蛋白( f i b r o u sp r o t e i n ) ，膜蛋白和球蛋白其中球蛋白的种类最多，功能也最重要，蛋白质并不仅仅是氨 基酸残基的线性序列，这种序列称为一级结构( p r i m a r ys t r u s t u r e ) 蛋白质实际上在三维 空间中折叠，形成二级结构( s e c o n d a r ys t r u c t u r e ) 、三级结构( t e r t i a r ys t r u s t u r e ) 和四级结 构( q u a t e r n a r ys t r u c t u r e ) 二级结构和三级结构有重要的区别，即二级结构是由肽基团间 的氢键产生的，肽基团在肽链序列中是挨在一起的三级结构是由二级结构( 口螺旋、卢 折叠) 的折叠产生三维结构形成的因为蛋白质的三维结构非常复杂，而且蛋白质的三维 结构与其功能相关，因此确定蛋白质的折叠或三维结构是分子生物学的一个重要领域 2 3 遗传密码与中心法则 d n a 分子的重要性在于，机体中合成k n a 和蛋白质的信息编码于d n a 分子中 基于此，d n a 有时被称为“生命蓝图”每一个细胞都有几个非常长的d n a 大分子， 每一个这样的分子称为染色体( c h r o m o s o m e ) d n a 中仅有一部分连续的片段编码构建蛋 白质的信息，而且其它部分并不编码蛋白质信息，每一种不同的蛋白质仅对应一段d n a 序列，该段序列称为基因( g e n e ) 贮存在d n a 上的遗传信息通过m r n a 传递到蛋白质上，m r n a 与蛋白质之间的联 系是通过遗传密码的破译来实现的m r n a 上每3 个核苷酸翻译成蛋白质多肽链上的一 个氨基酸，这3 个核苷酸称为密码，也叫三联子密码三联核苷酸和与氨基酸之间的对 应关系称为遗传密码( g e n e t i cc o d e ) ，见表2 1 8 大连理工大学硕士学位论文 表2 1 ：蛋白质中发现的2 0 种常见氨基酸以及氯基酸的遗传密码 g e n e t i cc o d e 氨基酸3 个字母1 个字母 g c u ，g c c ，g c a ，g c g 丙氨酸( a l a n i n e ) a 1 8a c g u ，c g c ，c g a ，c g g 精氨酸( a r g i n i n e )a r g r g a i j 、g a c 天冬氨酸( a s p a r t i ca c i d ) a s p d a a u a a c 天冬酰胺( a s p a r a g i n e ) a s h n u g u ，u g c半胱氨酸( c y s t e i n )c y s c g a a g a g 各氨酸( g l u t a m i ca c i d ) g l u e c a a c a g 谷氨酰胺( g l u t a m i n e ) g i n q g g u ，g g c ，g g a ，g g g 甘氨酸( g l y c i n e ) g 1 y g c a u c a c 组氨酸( h i s t i d i n e ) h i s h a u u ，a u c ，a u a 异亮氨酸( i s o l e u c i n e ) i l e i c u u ，c u c ，c u a ，c u g ，u u a ，u u g亮氨酸( 1 e u c i n e ) l e u l a a a ，a a g赖氪酸( 1 y s i n e )l y s k a u g 甲硫氨酸( m e t h i o n i n e ) m e tm u u u ，u u c苯丙氨酸( p h e n y l a l a n i n e ) p h ef c c u ，c c c ，c c a ，c a g脯氨酸( p r o l i n e ) p r op u c u ，u c c ，u c a ，u c g 丝氨酸( s e r i n e ) s e xs a c u ，a c c ，a c a ，a c g苏氨酸( t h r e o n i n e ) t h rt u g g 色氨酸( t r y p t o p h a n ) t r p w u a u u a c 酪氨酸( t y r o s i n e )w y r y g u u ，g u c ，g u a ，g u g缬氨酸( v v i n e ) v a l v 表2 1 中的三联体核苷酸是用r n a 碱基而非d n a 碱基表示，因为r n a 分子提供了 d n a 和蛋白质之间的关联在表中可以看出6 4 种三联体密码子( c o n d o n ) 中有三个终止 密码子u a a ，u a g 和u g a ，其余的6 1 个密码子编码了2 0 种氨基酸，因此很多氨基酸 都有多种编码( 筒并) ；三种氨基酸有6 重简并编码：亮氨酸( l ) 、丝氨酸( s ) 和精氨酸 ( r ) ；五种氨基酸有4 重简并编码；缬氨酸( v ) 、脯氨酸( p ) 、丙氨酸( a ) 、甘氨酸( g ) 和苏氨酸( t ) ；有3 重筒并编码的是异亮氨酸( i ) 和终止密码子；有9 种氨基酸有2 重简 并编码：苯丙氨酸( f ) 、酪氨酸( y ) 、组氨酸( h ) 、谷氨酰胺( q ) 、天冬酰胺( n ) 、赖氨 酸( k ) 、天冬氨酸( d ) 、谷氨酸( e ) 和半胱氨酸( c ) ；只有甲硫氨酸( m ) 和色氨酸( w ) 是单重编码 下面我们介绍d n a 信息是如何指导蛋白质合成的一个识别基因或基因簇起始的 机制是启动子( p r o m o t e r ) 启动子是基因前面的一段d n a 序列，密码子a i g 则是基因 开始的信号识别出基因的起始点后，基因到r n a 的拷贝就开始了，合成的r n a 称为 信使r n a ( m r n a ) ，其序列与d n a 的一条链相同，但是u 代替了t ，该过程称为转录 ( t r a n s c r i p i o n ) 9 r n a 二缀结构的计数 因r n a 是单链而d n a 是双链的，m r n a 在序列上与一条d n a 链相同( 只不过是u 代替了r ) ，与另一条链互补d n a 中，与m r n a 序列一致的链称为反链( a n t i s e n s es t r a n d ) 或编码链( c o d i n gs t r a n d ) ，而另一条链称为有意义链( s e n s es t r a n d ) 、反密码链( a n t l c o d i n g s t r a n d ) 或模板链( t e m p l a t es t r a n d ) 实际上被转录的是模板链，因为m r n a 是由与该链互 补的核糖核酸组成的，合成过程是从5 端向3 端，因此模板链是从3 端向5 端阿读的 上述的转录在原核生物( p r o k a r y o t e ) 中是对的在这些生物中，由于缺乏核膜，d n a 是自由悬浮于细胞中的但在真核生物( e u k a r y o t e ) 的细胞中有细胞核，d n a 位于细胞 核中，其转录模式更为复杂许多真核细胞基因具有不同的组成部分，即内含子( i n t r o n ) 和外显子( e x o n ) 转录后内含子必须从m r n a 中切除，这意味着内含子不参与蛋白质的 合成在内含子被剪切后，离开细胞核的剪短的m r n a 仅含有外显子与起始和终止的调 控序列 因为有内含子和外显子，我们用不同的名字命名染色体上的全基因和剪切后仅含外 显子的基因，前者称为基因组d n a ( g e n o m i cd n a ) ，后者称互补d n a ( c o m p l e m e n t a r yd n a ) 或c d n a ，通过细胞核外的m r n a ，然后使用一个称为反转录( r e v e r s et r a n s c r i p t i o n ) 的过 程，以m r n a 为模板合成c d n a 这样，人们可以不经染色体而获得c d n a 在某些生物 体中也存在反转录现象，例如，反病毒通过反转录的机制能将它们的r n a 基因组复制成 d n a 在这个过程中另外两种r n a 分子起到重要的作用蛋白质的合成是在细胞内被称 为核糖体中进行的核糖体由蛋白质和被称为核糖体r n a ( r i b o s o m a lr n a ，r r n a ) 的大分 子组成遗传信息从r n a 传到蛋白质的过程称为翻译( t r a n s l a t i o n ) 实际上，遗传密码的翻译是由t r n a 实现的，它连接密码子和其所编码的氨基酸当 m r n a 穿过核糖体内部时，t r n a 匹配当前的密码子，即当前位于核糖体内部的m r n a 密码子，与它结合，并带进对应的氨基酸( 细胞中总是悬浮着大量的氨基酸) 这些分子 此时所处的空间位置使它们可以完成下列操作，即随着t r n a 与密码子结合，新结合的 氨基酸紧靠先前巳形成的氨基酸链，一个合适的酶则催化该氨基酸加入肽链，然后释放 t r n a 蛋白质按这种一个氨基酸接一个氨基酸的方式合成起来当出现终止密码子时， 没有t r n a 与之对应，合成便终止，m r n a 被释放，并被降解成核糖核苷酸 总结上面描述的过程，细胞内遗传信息的流动通常用中心法则( c e n t r a ld o g m a ) 来说 明，如图2 9 中心法则：生物的信息是由一个核酸传给另一个核酸，也可能从核酸传给蛋白质 但一旦信息传入蛋白质，它就不能再出来这里的信息是指已知确定的序列，或者是核 酸中碱基序列，或者是蛋白质中的氨基酸序列简单地说，d n a 双螺旋是遗传信息的携 带者，它在一定条件下可以准确地自我复制遗传信息只能通过最终的蛋白质产物体现 或表达 1 0 大连理工大学硕士学位论文 硝 图2 , 9 细胞内的遗传信息流动t 分子生物学的中心法则 大连理工大学硕士学位论文 3 r n a 二级结构及子结构的计数 我们知道，d n a 、r n a 和蛋白质是三种重要的生物大分子，是生命现象的分子基 础d n a 的遗传信息决定了生命的主要性状，而m r n a 在信息传递中起很重要的作用， 其它两大类r n a ：r r n a 和t p u n a ，同样在蛋白质的生物合成中发挥着不可替代的重要功 能因此，深入对r n a 结构的研究，进而了解r n a 的功能有着极其重要的意义【1 4 1 7 | r n a ( 即t r n a ，r r n a ，m r n a 和s n r n a ) 有两大主要功能t 一是某些病毒的遗传物 质；二是参与蛋白质的合成这些与细胞分化、代谢、记忆的储存等有重要关系为了 更好的了解r n a 的功能，解读遗传密码，就需要剖析r n a 的结构对于r n a 的高级 结构传统分析是生物化学和生物物理学方法这不仅费时，且只能用于小分子r n a 的 研究( 如t r n a ，只含有七八十个核苷酸) ，对大分子r n a ( 如r r n a ，含几百几千个核苷酸) 就相当困难由于多数r n a 含碱基达1 0 3 以上，目前依靠实验手段很难给出它们的二级 结构借助计算机来预测r n a 的高级结构是一种很经济的手段 i s 挪 近些年来，有关 r n a 分子二级结构的研究一直很活跃，给出了不少预测方法，如m a x i m a lm a t c h i n g 方法 【2 0 】，m i n i m a lf r e ee n e r g y 方法，d y n a m i cp r o g r a m m i n ga l g o r i t h m s 7 】以及t r e ea d j o i n i n g g r a m m a r s 2 1 】等，并编写了程序，预测了许多r n a 分子的二级结构，不过许多预测结果 与实验结果常有出入，结构不稳定 在1 9 6 0 年，f r e s c o 等提出了第一个r n a 二级结构预测算法，论述了r n a 二级结 构基本特征和预测的基本原理 1 9 7 5 年，p i p e s 和m c m a h o n 首先提出运用计算机技术 预测r n a 二级结构但是，由于实验条件的限制，绝大多数的r n a 分子的二级结构还 不能用实验的方法来测定因此，用理论方法预测r n a 二级结构就显得尤为重要了目 前理论预测r n a 二级结构的算法主要有两类：一类是基于矩阵运算的动态规划算法，如 n u s s i n o v 等提出的碱基最大配对算法和z u k e r 等提出的最小自由能算法另一类算法是 基于茎区组合的预测算法，如b e n e d e t t i 提出的茎区最优堆积算法这些算法在近二十年 得到了很大发展，但各算法的时间和空间复杂度都较大，限制了算法处理问题的规模， 并且准确性不高我们可以借鉴前些算法的优点，改善算法 所谓r n a 二级结构的预测，就是计算给定长度的r n a 序列的最优结构目前所有 预测算法要预测出所有序列的二级结构仍然非常困难，自然估计给定长度的所有可能的 二级结构数则成了数学任务这些结果在负面意义上对生物学有用，它肯定了存在巨大 数量的特殊结构数，直接枚举是没有希望的，并且它间接地决定了预测算法的时间复杂 性和空间复杂性在本文中我们应用组合计数的技巧，考虑了r n a 二级结构及子结构的 计数问题 r n a 二级结构的计数 3 1 r n a 二级结构预测基本原理 r n a 二级结构是通过分子中的碱基之间配对形成的碱基之间配对有三种类型t g c 、如u 和g u ，它们之间分别有三个、二个和一个氢键碱基之间的连续配对形成螺 旋区，对r n a 二级结构起着稳定作用嘲，从而降低整体结构自由能，而r n a 分子中没 有配对的部分形成环状结构，如发卡环、内部环、凸包环和多分支环等，不利于结构的稳 定，提高了结构的自由能，r n a 二级结构的形成就是在这种矛盾之间的一种平衡预测 r n a 二级结构最常用的方法就是在各种可能结构之间寻找最小自由能结构，而基本结构 的自由能数据是通过研究体外寡核苷酸稳定性获得的最常用的自由能数据为s a i z e r 和 t u r n e r 能量积分系统1 2 3 ，但在这两组数据中，没有提及多分支环的能量计算，目前一般 将之作内部处理，或用公式计算：4 7 + o 4 x 单链碱基数+ o 1 螺旋区数目有了这些 数攮就可评价r n a 二级结构的稳定性，通过这种方法可以得到近乎稳定能量的结构和 最可靠的预测结构在相关序列中发现的序列变异也可用于预测哪种碱基配对有可能在 每个分子中都存在r n a 结构预测方法的一种变体是预测一组可能形成一种特定结构 的序列。 3 2 r n a 二级结构表示 r n a 二级结构表示方法很多，如半圆表示、圆形表示、点阵表示、山峰表示、正多边 形表示等，其中以正多边形表示最为直观形象，便于分子生物学家观察，研究r n a 二级 结构特征，但是利用这种方式来比较不同的结构是较为困难的，因为利用这种表示方式 时，常导致许多子结构的重叠，为此，人们不得不借助于旋转的办法来克服重叠现象， 这样一来，即使是对同一种结构，可能由于在不同的地方旋转或在同一地方旋转的角度 不同而导致结构形状的变化目前，再现结构或对结构进行比较的最好方法是树状表示 方法，这种方法是从图论的角度来考虑的，与上述方法不同，在r n a 二级结构中，每个 配对碱基用一个点表示，然后用一条有向线段将点按顺序连接起来，便可获得r n a 二级 结构的树状表示，在这种显示中，环区碱基等信息将被丢失。r n a 二级结构是平面图， 磷酸骨架用实线表示，基用点表示，氢键或基对表示为两个非相邻间的线，在二级结