（应用数学专业论文）rna二级结构的计数问题及其进化分析.pdf

大连理工大学博士学位论文 摘要 r n a 是由a 、c 、g 、u 四种不同的核苷酸组成的单链r n a 通过自身回折， 使链中的一部分核苷酸与其它部分核苷酸互补配对，形成r n a 二级结构r n a 二级结 构的计数研究是计算分子生物学的重要课题之一由于r n a 二级结构经常被抽象为离 散的数学对象，从而使得离散数学和分子生物学密切联系在一起一方面，组合技巧成 功的应用到了k n a 二级结构的计数问题中；另一方面，r n a 二级结构的计数问题启发 了新的有趣的组合问题另外，人类基因组计划的实现产生了大量的数据，如何选择有 效的方法从这些数据中提取信息，进而分析物种间的进化关系，将面临着巨大的挑战 本文主要研究了r n a 二级结构的组合计数问题及其进化分析，主要内容如下z 一、详细介绍了r n a 二级结构的基本信息，主要包括二级结构的各组成元素以及各 种传统的表示形式，并且利用发生函数的方法讨论了限制端环长度的r n a 二级结构的 计数问题。另外，给出了一种计算s m ( n ) 的方法 二、为了化简限制端环长度的r n a 二级结构的递推公式，建立了二级结构与组合数 学中三种特殊的集合间的一一对应通过建立的双射关系，得到了关于限制端环长度至 少为仇且有k 个基对的二级结构数( 礼，k ) 的一个封闭和式 三、按照w a t s o n - c r i c k 碱基配对原则，用圈表示a ( u ) 而用点来表示a ( c ) ，提出 了r n a 二级结构一种新的表示形式这种表示比传统的表示形式更为合理在此基础之 上，研究了以端环长度为参数且带有各种限制条件的二级结构的计数问题，并且进一步 研究了同时选取端环和堆积的长度作为参数的二级结构的渐近计数问题 四、将两组复杂的r n a 二级结构分别转换成定义在2 0 个字符上的线性符号序列， 计算出其l z 复杂性，进而基于两种不同的算法构造了进化树，结果充分证明了我们方 法的有效性 关键词：r n a 二级结构；递归公式；发生函数；多项式等式；组合计数；渐进计数；线性 树；s c h r & l e r 路；不交叉分拆；l e m p e l - z i v 复杂度；进化树 大连理工大学博士学位论文 e n u m e r a ti o np r o b l e m sa n de v o l u t i o n a r ya n a l y s i so f r n as e c o n d a r ys t r u c t u r e s a b s t r a c t a nr n am o l e c u l ei sas i n g l e - s t r a n d e dc h a i nc o n s i s t i n go ft h en u c l e o t i d e sa ，阢c ，g an u - c l e o t i d ei no n ep a r to ft h em o l e c u l ec a nb ep a i r e dw i t hac 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 r p a r t a n dt h u st h em o l e c u l a rf 0 1 d st of o r ms e c o n d a r ys t r u c t u r e s t o d a y , t h er e s e a r c ho nt h e e 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 si so n eo ft h eh o tt o p i c si nc o m p u t a t i o n a lm o l e c u l a r b i o l o g y r n as e c o n d a r ys t r u c t u r e sa r eu s u a l l ya b s t r a c t e dt od i s c r e t em a t h e m a t i co b j e c t s ，w h i c h e s t a b l i s h e sac o n n e c t i o nb e t w e e nd i s c r e t em a t h e m a t i c sa n dc o m p u t a t i o n a lm o l e c u l a rb i o l o g y o nt h eo n eh a n d ，t h es k i l l so fc o m b i n a t o r i c se n u m e r a t i o nh a v eb e e ns u c c e s s f u l l ya p p l i e dt ot h e e n u m e r a t i o np r o b l e m so fr n as e c o n d a r ys t r u c t u r e s o nt h eo t h e rh a n d ，t h ee n u m e r a t i o np r o b - l e m so fr n a s e c o n d a r ys t r u c t u r e sh a v ei n s p i r e ds o m en e wi n t e r e s t i n gc o m b i n a t o r i a lq u e s t i o n s i na d d i t i o n ，t h e r ea r ea b u n d a n to fd a t ad u r i n gt h ei m p l e m e n to fh u m a np r o j e c t a n di t i sa g r e a tc h a l l e n g et oa n a l y z et h ep h y l o g e n e t i cr e l a t i o n sa m o n gd i f f e r e n ts p e c i e sb yc h o o s i n gv a l i d m e t h o d su s e dt oe x t r a c te s s e n t i a li n f o r m a t i o n t h ec o r eo ft h i st h e s i si sr n a s e c o n d a r ys t r u c t u r e s a n dw em a l i l l yd i s c u s s e st h ee n u m e r a t i o np r o b l e m sa n dt h ee v o l u t i o nr e l a t i o n s t h em a i n c o n t e n t so ft h i st h e s i sc a nb es u m m a r i z e d 鹊f o u o w s ： c h a p t e r2d e s c r i b e ss o m ei n f o r m a t i o no ft h er n as e c o n d a r ys t r u c t u r ei nd e t a i l ，i n c l u d i n g s o m ee l e m e n t so fr n a s e c o n d a r ys t r u c t u r e sa n dv a r i o u st r a d i t i o n a lr e p r e s e n t a t i o n s ，a n dm a k e s af 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 np r o b l e mo fr n a s e c o n d a r ys t r u c t u r e sw i t hl i m i t e d l e n g t ho fe a c hl o o pu s i n gi t sg e n e r a t i n gf u n c t i o n m o r e o v e r ，am e t h o dt oc o m p u t e m ) i s 酉v e n i no r d e rt os p e c i f yt h er e c u r r e n c er e l a t i o n so fr n a s e c o n d a r ys t r u c t u r e sw i t hl i m i t e dl e n g t h o fe a c h1 0 0 p ，骶e s t a b l i s ho n et oo n ec o r r e s p o n d e n c e sb e t w e e nt h es e t so fs e c o n d a r ys t r u c t u r e s a n dt h r e es p e c i a ls e t si nc o m b i n a t o r i c si nc h a p t e r3 a n da ne x a c te x p r e s s i o na b o u ts e c o n d a r y s t r u c t u r e sw i t hkb a s ep a i r sw h o s el o o ph a sa tl e a s tmb a s e si so b t a i n e db yo n eb i j e c t i o n i nc h a p t e r4 ，an e wr e p r e s e n t a t i o ni so b t a i n e db a s e do nt h ew a t s o n - c r i c kp r i n c i p l e ，i e ， l e tc i r c l e st or e p r e s e n tt h eb a s e sa ( u ) a n dd o t st or e p r e s e n tt h eb a s e sg ( c ) t h er e p r e s e n t a t i o n i sm o r er e a s o n a b l ea n dm e a n i n g f u lt h a nt h et r a d i t i o n a lr e p r e s e n t a t i o n s b a s e do nt h en e w r e p r e s e n t a t i o n w em a k ean e wd i s c u s s i o nb yc h o o s i n gt h el e a s tl e n g t ho fl o o p sa n ds t a c k sa s p a r a m e t e r s i nt h ef i n a lc h a p t e r ，w et r a n s f o r mc o m p l e xr n a s e c o n d a r ys t r u c t u r e si n t ol i n e a rs y m b o l i c s e q u e n c e sd e f i n e di n2 0a l p h a b e t ，a n dc d m p u t et h e i rl zc o m p l e x i t i e s f u r t h e r m o r e ，w eo b t a i n t h ep h y l o g e n e t i ct r e e su s i n gt w od i f f e r e n tp r o g r a m m e s t h er e s u l t sa d e q u a t e l yi n d i c a t et h e i i i r n a 二级结构的计数问题及其进化分析 v a l i d i t yo fo u rm e t h o d 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 r e n c er e l a t i o n ；g e n e r a t i n gf u n c t i o n ；m u l t i n o - 血a li d e n t i t y ；c o m b i n a t o r i a le n u m e r a t i o n ；a s y m p t o t i ce n u m e r a t i o n ；l i n e a rt r e e ；s c h r s d e rp a t h ； n o n c r o s s i n gp a r t i t i o n ；l e m p e l - z i vc o m p l e x i t y ；p h y l o g e n e t i et r e e i v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 一、 一 d 莎 日期：坦p 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文 版权使用规定一，同意大连理工大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、 缩印或扫描等复制手段保存和汇编学位论文 作者签名： 导师签名： 至4 年月l 日 大连理工大学博士学位论文 1 绪论 2 1 世纪是生命科学，新材料技术，信息技术突飞猛进的发展时期生物信息学作为 跨越生命科学和信息科学两大热点领域的学科展现了它蓬勃的生命力( 1 】生物信息学 是用数理和信息科学的观点、理论和方法去研究生命现象，组织和分析呈现指数增长的 生物学数据的一门学科从整体上来讲，生物信息学主要把核酸和蛋白质等生物大分子 的结构及其在遗传信息和细胞信息传递中的作用作为研究对象【2 j 其中，蛋白质无所 不在，它的功能多样，几乎所有的生命活动中都有蛋白质的参与 3 而核酸是生命体内 重要的高分子化合物，它储存着生物体内全部遗传信息，是基因表达不可缺少的物质基 础 4 核酸可分为两大类；脱氧核糖核酸( d n a ) 和核糖核酸( r n a ) d n a 主要以双链形 式存在，是生物遗传信息的携带者，而r n a 是单链核酸，具有多种生物功能，如催化蛋 白质生物合成的功能，携带与调控遗传信息的功能，信号分子功能等等f 3 】另外，r n a 在生物进化中起着不可忽视的重要作用【2 】在2 0 世纪8 0 年代核酶的发现表明了生命 起源的早期可能首先出现的是r n a 因此，国际科技界对r n a 的作用也越来越重视 r n a 的发展一直受d n a 研究的推动特别是，自1 9 5 3 年，w a t s o n 和c r i c k 共同提出 d n a 双螺旋结构学说后的4 5 年里，6 个诺贝尔奖与r n a 的研究领域有关，而在2 0 世 纪末2 1 世纪初，r n a 方面的进展连续5 年被美国s c i e n c e 杂志评为年度科技十大突破之 一【3 这也预示着在新的世纪里，关于r n a 的研究正迎接着崭新的挑战 理解分子的生物功能是生物信息学的核心问题因为分子在三维结构空间里折叠， 并且因为其功能取决于这种折叠的方式在过去的几十年里，科学家关心的一个重要议 题是发现这些大分子的三维结构，特别是r n a 和蛋白质的三维结构，这孕育出基于分子 原始序列预测其结构的方法。所谓r n a 二级结构的预测，就是计算给定长度的r n a 序 列的最优结构目前所有预测算法要预测出所有序列的二级结构仍然非常困难，自然估 计给定长度的所有可能的二级结构数则成了数学任务这些结果在负面意义上对生物学 有用，它肯定了存在巨大数量的特殊结构数，并且它间接地决定了预测算法的时间复杂 性和空间复杂性。因此，研究r n a 二级结构计数问题成了非常必要而有意义的课题 另外，随着人类基因组计划的完成以及后基因时代的到来，生物学数据呈现指数级 增长同时，从单一的生化数据向遗传信息数据的飞跃，以及进一步向遗传与结构功能 相互关系信息的飞跃然而，理解生物序列编码结构信息仍然面临严峻考验例如，理解 l r n a 二级结构的计数问题及其进化分析 碱基匹配或单链r n a 序列的二级结构对r n a 分子的生化功能至关重要争7 】那么，如 何计算分析这些高度复杂的生物学数据，生物学家，数学家，计算机专家同样面临巨大 挑战【8 】 特别地，关于r n a 进化的研究也一直是一个十分活跃的领域f 2 】由于r n a 二级结 构比一级序列有更好的保守性，并且r n a 分子承载了丰富的遗传信息，因此，从r n a 二级结构数据中提取信息进行分析比较，能有效的反映物种问的进化关系p 1 4 】 1 1 关于r n a 二级结构计数问题的研究概况 关于单链核酸r n a 的二级结构计数的研究已经有很长的历史，它是个典型的组合 问题1 9 7 8 年，美国科学院院士m s w a t e r m a n 最先将r n a 二级结构这一概念给出了数 学化的描述，从而，开启了从数学角度分析r n a 二级结构这一课题的研究，也使得数学 与分子生物学紧密联系在一起正如文献 1 5 】中指出，二级结构计数这一问题在各种条件 的限制下产生的序列可以看作是c a t a l a n 数以及m o t z k i n 数的一般推广因此，这一课题 引起了国内外许多从事组合数学，分子生物学以及计算机科学研究人员的关注f 1 扣2 4 由于r n a 是d n a 和蛋白质之间的一个中间语言，因此r n a 二级结构的准确预测 对于了解基因调控和蛋白质产物的表达具有重要的作用【2 5 】对于r n a 二级结构计数问 题的研究，它肯定了现实中存在了大量的r n a 二级结构，从负面意义上对r n a 二级结 构预测起到了重要作用因此说，关于r n a 二级结构数的一系列递推关系是指导r n a 的二级结构预测的重要因素例如，在1 9 7 8 年，w a t e r m a n 与s m i t h 根据得到的递归公 式进行了r n a 二级结构预测【2 6 】在1 9 8 4 年，z u k e r 也提出了r n a 二级结构预测算 法 2 7 】，等等 1 1 1 关于带各种限制条件的r n a 二级结构计数的研究 r n a 二级结构结构复杂，由堆积，端环，发夹环，凸包环，多分支环，尾巴等等多 种基本结构组成，从而吸引了很多学者的关注f 1 7 ，2 2 ，2 8 3 0 】。 对于带有各种限制条件的r n a 二级结构计数的研究，其主要思想是：考虑b + 1 】上 任意的二级结构可以由m 上的二级结构通过下列两种方式得到： ( i ) 在末端增加一个自 由基；( i i ) 增加的碱基n + 1 与k 形成碱基对( k ，佗+ 1 ) ，n k m ，其中m 是阈值( 由于 在自然界中，r n a 自身的折叠不能过于尖锐，因此，在通常情况下，人们都考虑限制端 环长度至少为m ) 根据这一思想，w a t e r m a n 最先给出了二级结构计数中的一个基本递 推关系式： 引理1 1 1 j p 玎设有序集m ：= 1 ，2 ，几) ，& 为h 上限制端环长度至少为m 的二级 结构数，那么& 满足下列关系： 7 n扎一 l 一1 & + 1 = 岛+ 岛一1 一j + 岛晶一2 。， j = aj = m + l 2 大连理工大学博士学位论文 边界值为岛= 研= = 一1 = 0 ，= 1 ，& = 0 ，n 0 。 对于取特定的m = 2 ，r n a 二级结构可以看作m o t z k i n 路，从而建立了r n a 二级 结构数与c a t a l a n 数和m o t z k i n 数之间的联系【1 5 】并且基于这一递推关系式的思想提出 了r n a 二级结构的预测算法 3 2 3 4 在1 9 9 8 年，i l h o f a c k e r 等人基于同样的思想给出了带有各种限制条件的r n a 二 级结构数的递推关系式 17 】例如：讨论了二级结构的所有分支数k ( 仡) ，具有b 个外点 的结构数e ( 礼，b ) ，所有外点的结构数点( 竹) ，以及所有自由基的结构数u 赢( 他) ，并且 还考虑了含有c 个分支且阶数为u 的结构数，等等 在最初的研究中，许多关于r n a 计数的渐进工作是建立在e a b e n d e r 定理的基础 上 3 5 】后来，h o f a c k e r 等人给出了不能直接应用b e n d e r 引理的反例，并且利用一个简 化的d a r b o u x 定理来讨论了r n a 二级结构的渐进计数的问题f 17 以后文中出现的符 号一具有通常意义下的含义。 f ( x ) 一夕0 ) 今兰_ 1 ，n 0 0 y 正， 引理1 1 2 设y n 0 ，其发生函数y ( z ) = y n x n 可以表示为y ( z ) = 卢( z ) + 9 ( z ) ( 1 一罟) u ， 其中q 是大于0 的实数，p ( z ) 和g ( z ) 在q 处是解析的，并且u 是非负的整数若y ( x ) 在 q 域内解析，且z = q 是y 在其收敛域内的唯一解，那么有下式成立 鼽一鹣n - l - w ( 护鼽”商i 云， 引理1 1 3 设圣( z ，y ) 是y 的多项式并且在z 处解析，这里 0 假定y 满足引理j j 2 的条件，且有耖 ) = 扛) + 夕( z ) ( 1 一罢) 考设z = 圣( z ，) 的发生函数为 z ( z ) 2 互z n 矿，那么有，熙舞。( q ，p ( q ) ) ，并且有下式成立 钿一样n 一( 护 下面给出了部分r n a 二级结构组成元素的渐进值，见下表 表格1 1r n a 二级结构组成元素的渐进公式 部分二级结构组成元素相对应的渐近值 a 2 b ，1 2 q 、6 1 厶( 6 ) ( 1 3 q ) 2 、1 一q 7 r ( b ) & 砉( 6 + 1 ) ( 壶) 6 2 q + ? 7 2 ( 1 2 q ) u n | s n 2 + m i 卜2 q m e n | s n 2 z o i n | s n一一j a 3 r n a 二级结构的计数问题及其进化分析 另外，r n a 二级结构中阶数是衡量结构复杂性的一个重要标准自1 9 7 8 年，m s w a t e r m a n 最先提出阶数这一课题的框架，一直没有非常令人满意的结果出现直到2 0 0 2 年，基于v i e n n o t 等人的工作【2 1 】，m e n e b e l 以发生函数作为工具，计算出对任意阶p 的二级结构数的渐近公式文中忽略了碱基之间的差异，完全从组合的观点考虑了平面 二级结构的拓扑性 3 6 】 在2 0 0 4 年，t d o s l i c ，d s v r t a n 和d v e l j i a n 将数学知识应用于分析r n a 二级结构 数( 死) 和七) f 2 2 】 ( 1 ) 证明了序列( 竹) 是对数凸的 ( 2 ) 证明了序列( n ，k ) 是对数凹的 ( 3 ) 利用超几何级数得到了s k ( k ) 的表达式： 晰= e ) m + 2 - 2k 瓠- k , 赢l1 ) 其中( - - f m ) i = 一m - n m + 一i - 1 ，( _ p m ) t = ( 才m ) i + 丽2 k ，i = 1 ，仇 1 1 2 关于r n a 二级结构集合与特殊集合之间的一一对应的研究 双射是一个非常有技巧性的方法特别的，建立生物学与数学之间联系更具特别之 处通过建立一一对应关系，我们可以借助于熟悉的知识来加深对新事物的了解，间接 地解决相对困难的问题由于直接根据r n a 二级结构数的递归关系式很难得到简单明 了的显式表达，为此很多学者试图将r n a 二级结构组成的集合与数学中一些比较特殊 的集合建立起一一对应关系，利用已知的数学知识来解决r n a 的计数问题在这一部分 中我们所提到的r n a 二级结构的集合均是指长为n 有k 个碱基对的所有的二级结构， 记为圣n ，k ，并且设该集合的势为s ( 礼，k ) ( 1 ) 早在1 9 9 4 年，m s w a t e r m a n 构造了圣n k 和线性树之间的一一对应r n a 二 级结构采用了点弧式表示形式，具体可参考文献 3 7 】下图是一个长1 3 有4 个碱基对的 二级结构以及与其相对应的线性树 21 3 图1 1r n a 二级结构与相对应的线性树 4 3 大连理工大学博士学位论文 进一步，根据所建立的双射关系以及已知的n a y a n a r a 数的计数公式得到了关于s ( n ，k ) 的一个漂亮的封闭表达式 s c 礼，忌，= 昙( ：) ( 死：三il ) ( 2 ) 圣n k 和特殊置换集合之间的一一对应，并且根据建立的双射关系获得了关于二 级结构的一些统计特性 3 8 】 简单的说，该特殊置换集合需要满足下列几个条件： ( a ) 7 r 是3 - 2 1 可避免的； ( b ) 若位置i 为一个严格不超过，则位置i + l 不是； ( c ) 若c 是一个严格不超过，那么c + l 不是； ( d ) 每个严格不超过至少是两个逆序的第2 个元素； ( e ) 恰好有k 个严格不超过 上面使用的术语可以参考文献 3 8 ，3 9 】下图是一个长1 8 有7 个碱基对的r n a 二级 结构与其相对应的置换 9 l1 5 1 6 1 8 12345678 91 01 11 21 31 4 1 5 1 61 7 1 8 图1 2r n a 二级结构与相对应的置换 ( 3 ) 圣础和二色有序树之间的一一对应 所谓的二色有序树是指高度为偶数的顶点为一种颜色，而高度为奇数的顶点为另一 种颜色的有根标号树，并且其每个顶点的子树均是线性有序的具体对应规则可以参考 文献【4 0 】下图给出的是一个长2 8 有8 个碱基对的二级结构以及与其相对应的一棵二色 有序树 5 r n a 二级结构的计数问题及其进化分析 胍 71 92 1 2 32 52 7 图1 3r n a 二级结构与相对应的二色有序树 9 另外，a n c w a n t 8 还研究了格路与r n a 二级结构之间的一一对应问题【2 8 ，并利 用几种著名的矩阵讨论了二级结构计数问题 1 2 关于r n a 进化分析的研究概况 近几年，生物学家发现r n a 分子在生物细胞内发挥着令人惊奇的作用r n a 具有 显著的构象灵活性和功能多样性，它已经成为揭示生命奥秘的重要分子除了众所周知的 血斟a 以及t r n a ，r n a 分子具有重要的生物功能，例如遗传密码的重译功能f 4 1 - 4 3 】， s m a l li n t e r f e r i n gr n a 和m i c r o r n a 的后转录调控功能惮，4 5 】另外，r n a 分子包含了 丰富的可用于分类的信息因此，近年来r n a 分子的研究引起了科学界的广泛关注 从生物学角度来讲，通常认为一个r n a 分子的二级结构比其一级序列更为保守也 就是说，对于一个r n a 分子构成二级结构的基对有很强的稳定性另外，r n a 二级结 构对确定r n a 分子的功能也起着重要的作用并且r n a 二级结构包含了丰富的可用于 分类的信息，在很大程度上决定了r n a 聚合体的三级结构对r n a 二级结构的研究变 得越来越重要 对于r n a 分子的研究存在许多方法一类是采用了碱基配对距离，如h a u s d o r f f 距 离法【删，山形度量法【4 7 等在1 9 8 9 年，z u k e r 利用碱基对点集之间的h a u s d o r f f 距离 来度量二级结构之间的差异程度，其中隔离的碱基对的位置对这个距离有很大影响后 来，z u k e r 等人又将该算法进行了一些改进1 4 8 山形度量算法以二级结构的峰函数之 间的r m s 距离来度量二级结构之间的差异程度，该方法克服了h a u s d o r f f 距离上述的缺 点一类是利用图形表示对r n a 二级结构进行分析l i a o 等利用折线图形的方法表示 了r n a 二级结构，分析了它们之间的相似关系 4 9 这种方法相对来说比较直观，但随 着序列长度的增加，处理会变得比较复杂 另一类是基于序列比对的算法最初，大多数比较方法只强调分子的一级序列或它 们的结构单元，如环和茎等例如，在1 9 9 0 年，s h a p i r o 提出了一类基于树编辑的r n a 6 大连理工大学博士学位论文 二级结构的比较方法，认为环和茎是基本的构成单元，建立了二级结构的树形结构( 5 0 】 以此为基础不断的出现了许多改进的算法【1 l ，5 1 5 3 】后来，人们开始同时考虑一级序列 以及基对的信息b a f l m 等给出了几个相似性概念，并且基于动态规划算法设计了两个 r n a 分子比对的新方法f 5 4 近来，非比对算法已广泛应用于序列的进化分析中l i 等人将r n a 二级结构转化 为影子序列，用l z 复杂性度量比较了r n a 分子的相似性f 5 5 1 而l i u 和w a n g 将复杂 的二级结构转化称简单的线性序列，建立了随机模型并且分析了r n a 分子之间的相似 性然而，这些方法存在退化现象，也就是说不同的的r n a 二级结构经过转化后可能对 应同样的序列近来，l i u 和w a n g 又通过二级结构中个堆积的划分进行了转化，得 到条特征序列，但每一条特征序列只包含二级结构一小部分信息并随着结构复杂性增 大，得到的线性序列数目也会增加f 1 3 总的来说，用于分析r n a 分子间的相似性的方法日渐丰富起来 1 3 本文的主要工作 生物学的一个中心问题是解释今天物种的进化历史通过核酸和蛋白质序列分析研 究生物的进化历程、确定物种间的进化关系已成为生物系统与演化研究中最重要与最热 门的工具之一随着对r n a 功能了解的不断深入，r n a 再也不是以往人们所认为的只 是将遗传信息从d n a 传递到蛋白质的中介r n a 至少是类与d n a 、蛋白质同等重要 的生物大分子 2 5 因此，通过对r n a 序列的分析同样能提供关于进化关系的新信息， 并且会越来越引起人们的重视 对于复杂的生物问题，如特定限制的r n a 二级结构，在一定程度上又能揭示奇特的 数学结构从本质上讲，生物序列经常被抽象为离散的数学对象：有限字母上的串以及 图论中的树等图形这一联系使得在离散数学和分子生物学之间产生了丰富的交叉一 方面，组合技巧成功地应用到了r n a 二级结构的计数问题中；另一方面，r n a 二级结 构的问题启发了新的有趣的组合问题因此，引起了国内外很多学者的关注 本文主要工作如下。 一、利用发生函数方法讨论了限制端环长度的r n a 二级结构的计数问题，给出了 s ( 礼) 以及s ( 礼，k ) 的封闭和式另外还给出了一种计算s 南( n ) 的方法 二、将限制端环长度的r n a 二级结构与组合数学中一些特殊的集合建立了一一对 应例如，给出了限制端环长度的二级结构与定义的m 树之间的一一对应关系限制端 环长度的二级结构与s c h r s d e r 路之间的一一对应关系并且给出了限制端环长度的二级 结构与特殊的规则不交叉分拆之间的一一对应关系，并且通过我们建立的双射关系，得 到了关于限制端还长度且有k 个基对的二级结构数( 礼，k ) 的一个封闭表达式 三、按照r n a 二级结构的w a t s o n - c r i c k 配对原则，将4 种核苷酸分为两类，只允许 同类之间的匹配，根据这一思想给出了r n a 二级结构的新的表示形式从生物学角度来 7 r n a 二级结构的计数问题及其进化分析 讲，这一表示比最初w a t e r m a n 给出的表示更具有实际意义在此基础之上，我们又研究 了以端环长度为参数且带有各种限制条件的二级结构数及其渐进结果并且还考虑了同 时以端环和堆积的长度为参数的渐近计数问题 四、由于r i g a 分子不仅携带遗传信息，还具有进化信息，并且考虑到r n a 二级结 构比一级序列更具有保守性，从而选取了两组真实的r n a 二级结构数据作为试验首先 将这两组复杂的r n a 二级结构按照我们给出的规则分别转换成定义在2 0 个字符上的线 性符号序列，并基于著名的衡量符号序列复杂性的l z 算法，定义了序列间的相似性度 量，进而应用两种常用的不同算法构造了进化树并且与已有的方法做了比较，结果证 明了我们方法的合理性及有效性 8 大连理工大学博士学位论文 2 组合方法在r n a 二级结构计数问题中的应用 2 1 r n a 二级结构及其表示形式 r n a 是由四种不同的核苷酸组成，分别记为a ，以g ，c ，称为基( b a s e ) 单链r n a 分子通过自身回折，使链中a 和u ，g 和c 之间分别配对，形成多端的双股螺旋区即 为r n a 的二级结构，这是生物学上的定义 5 6 】r n a 分子是极性分子，包含5 端和 3 端通常二级结构中的碱基分为两类，没有与其它的碱基匹配形成氢键的称为自由基 ( f r e eb a s e ) 。否则称为匹配基( b a s ep a i r ) 并且规定 ( i ) 用i ，i + 1 ，i + 2 分别表示第i ， + 1 ，i + 2 个碱基a t ，0 4 + l ，0 4 + 2 ( 从5 7 端开始算起) ( i i ) 若0 4 与q 匹配，用( i ，j ) 表示碱基对 ( i i i ) 如果k i 2 ，且k 与2 匹配，则称i 属于碱基对( k ，z ) 1 9 7 8 年，w a t e r m a n 从数学角度定义了r n a 二级结构，但它排除了假结( p s e u d k n o t ) 情况该定义的提出奠定了r n a 二级结构组合计数问题的研究 定义2 1 1 r n a 二级结构的数学定义： 线性序列q = a l a 2 a n ，0 4 【a ，gg ，u ) ，i = 1 ，2 ，n ，将其视为n 个顶点的标号 图，其邻接距阵a = ( 吼，) 满足： 例吼，i + 1 = 1 ，1 i 礼一1 i 以砂对任意的i ，至多存在一个k i 一1 ，i + 1 满足毗k = 1 ； ( i i i ) 若吼，j = a k ，z = 1 且i k j ，则有i z 歹， 称序列o t 为二级结构 一般地，如果0 4 , j = 1 ，j i 一1 ，i + 1 ，则称i 与j 匹配 下面先介绍r n a 二级结构各组成元素的基本定义 定义2 1 2 堆积( s t a c k ) 。他叫配对双螺旋区，包含连续碱基对0 一k ，q + 惫) ，0 一k + 1 ，g + k 一1 ) ，( p ，q ) 且一k 一1 ，g + 七+ 1 ) ，p + 1 ，q 1 ) 都不是碱基对，其长度为+ 1 ， 称p k ，口+ k ) 为堆积的末端碱基对 定义2 1 3 端环( e n dl o o p ) 。由一个末端碱基对和自由基构成，长度为自由基的个数 定义2 1 4 凸包环( b u l g ez o o p ) 。他叫膨胀环，由不少于一个自由基和两个碱基对构成， 这两个匹配基为开始基( b e g i nb a s e ) 和结束基( e n db a s e ) ，长度为自由基的个数 9 r n a 二级结构的计数问题及其进化分析 定义2 1 5 内环( i n t e r i o rl o o p ) ，由不少于2 个自由基侮边至少一州和两个碱基对构 成，长度为自由基的个数 定义2 1 6 发夹( h a i r p i n ) ，由基对侄少一纠，凸包环，内环和恰好一个端环构成的 结构 定义2 1 7 发夹环( 地i r p i nl o o p ) 。只包含一个发夹的的结构 定义2 1 8 多分支环( m u l t i b r a n e hl o o p ) t 从一个环上 伸出刀三个或三个以上的堆积， 长度为环上自由基的个数 定义2 1 9 外点( e x t e r n a lv e r t e x ) 。不在任何环内的自由基 定义2 1 1 0 内点( i n t e r n a lv e r t e x ) s 属于某个碱基对的自由基 定义2 1 1 1 尾巴( t a i l ) 。他叫末端单链区，位于始端或末端连续的自由基显然构成 尾巴的碱基一定为外点 定义2 1 1 2 分支( c o m p o n e n t ) ：如果p = 1 或q = t l 或碱基p 一1 ，q + 1 不属于任何碱基 对，我们称堆积( p ，g ) ，+ 七，g 一七) 为末端堆积( t e r m i n a ls t a c k ) 被末端堆积中的末 端碱基对( p ，g ) 所包含的子结构，我们称为二级结构的一个分支 昏营 图2 1r n a 二级结构的各组成元素 图2 1 给出了r n a 二级结构的基本组成元素的图示( a ) 是包含碱基对( 1 ，1 1 ) ， ( 2 ，1 0 ) ，( 3 ，9 ) ，( 4 ，8 ) 和自由基5 ，6 ，7 的序列( 1 23 1 1 ) 的一种二级结构从而， 当图2 1 加以标号后就变成了下图t 6 1 0 大连理工大学博士学位论文 区域( 1 2 3 4 ) 与( 1 1 1 0 一9 8 ) 相互匹配称为一个堆积，这一结构在图( c ) 中也同 样出