（计算数学专业论文）计算分子生物学中若干问题研究.pdf

摘要 d n a 、r n a 和蛋白质的初级结构( 或线性序列) 都是由较小的单元组成的无分 枝的线性聚合体大分子。对于d n a ，这些单元是a ( 腺嘌呤) 、c ( 胞嘧啶) 、g ( 鸟嘌 呤) 和t ( 胸腺嘧啶) 这4 种核苷酸残基；对于r n a ，这些单元是a 、c 、g 和u ( 尿 嘧啶) 这4 种核苷酸残基；对于蛋白质这些单元是2 0 种氨基酸残基，即a ( 丙氨醐、 c ( 半胱氨酸) 、d ( 天冬氨酸) 、e ( 谷氨酸) 、f ( 苯丙氨酸) 、g ( 甘氨酸) 、h ( 组氨酸) 、 i ( 异亮氨酸) 、k ( 赖氨酸) 、l ( 亮氨酸) 、m ( 甲硫氨酸) 、n ( 天冬酰氨酸) 、p ( 脯氨 酸) 、q ( 谷氨酰胺酸) 、r ( 精氨酸) 、s ( 丝氨酸) 、t ( 苏氨酸) 、v ( 缬氨酸) 、w ( 色氨 酸) 和y ( 酪氨酸) 这样，一个d n a ( r _ n a ) 序列可以看作是在一个有四个字母的字母 表= f a ，c ，g ，t ( u ) ) 上的字( w o r d ) ，同样，蛋白质也可以看作是一个在2 0 个字母上 的字。而r n a ( d n a ) 二级结构是由自由基( f r e eb a s e ) 和基对a - u ( a - t ) 和c g 组 成的，在一定程度上，r n a ( d n a ) 二级结构经过处理后都可以转化为线性序列。 因此组合学和统计学的工具和方法可以在研究生物序列和生物结构上发挥很大的作 用。同样我们可以用几何方法来表示生物序列和二级结构，几何拓扑和群论也发挥很 大作用。 本文的主要工作包括以下几个方面： 由于目前所有有关r n a 二级结构的预测算法要预测出所有序列的二级结构仍然 很困难，在第二章我们就应用组合计数的技巧解决了有关r n a 二级结构及其子结构 的计数问题，推广了ms w a t e r m a n 等人f 5 7 ，9 1 的结果 自由能是衡量最优结构的常用标准，在第三章我n 给出了算法用于计算r n a 二 级结构( 含假结) 的最小自由能。 在第四章，我们给出了算法用于寻找m r n a 序列和蛋白序列的最优局部对比和全 局对比，我们还解决了生物序列和生物结构的l c s 问题。 在第五章，我们根据d n a 序列中四种核苷酸a 、g 、c 和t 的化学结构分类， 给出了d n a 序列一种符征表示，2 种三维图形表示方法，一种二维图形表示和一种 四维表示，利用序列对应点的坐标构造距离矩阵和l l 矩阵。计算l l 矩阵的正规化 最大特征值相距离矩阵的平均频带宽度，并把它们作为d n a 序列的一种不变量。基于 这些d n a 序列的不变量我们分析了h u m a n ，g o a t ，g a l l u s ，o p o s s u m ，l e m u r ，m o u s e ，r a b b i t ， r a t ，b o v i n e ，g o r i l l a ，c h i m p a n z e e 等1 1 个物种的球蛋白( g l o b i n ) 基因序列的第一个外显子 序列的相似性和非相似性。我们还根据2 0 种氨基酸的化学性质分类，给出了氨基酸 序列的一种特征表示，提出了，x 一独立成分和特征信息熵的概念，利用特征信息熵和 产- 独立成分分别构造向量比较了几种动物的神经元基因序列。 在最后一章，根据r n a 二级结构中自由基和基对的化学结构分类，我们自 r n a 二级结构的一种三维图形表示，一种四维表示和一种7 维表示，并构造型 阵和l l 矩阵，利用l l 矩阵的正规化最大特征值和结构不变量比较了9 种* r n a 3 二级结构的相似性。 关键词：d n a 序列、特征序列、蛋白质、r n a 二级结构、距离矩阵、l j 、正规化最大特征值、序列不变量、结构不变量、最小自由能 a b s t r a c t t h ep r i m a r ys t r u c t u r e so fd n a ( d e o x y r i b o n u c l c i ca c i d ) ，r n a ( r i b o n u c l e i ca c i d ) ，a n d p r o t e i na r ea l lm a c r o l n o l e c u l e sw h i c ha r eu n b r a z l c h e dp o l y n m r sb u i l tu pf r o ms m a l l e ru n i t s i nt h ec a s eo fd n a ，t h e s eu n i t sa r et h ef o u rn u c l e o t i d er e s i d u e sa ( a d e n i n e ) ，c ( c y t o s i n e ) ， g ( g u a n i n e ) a n dt ( t h y m i n e ) ，w h i l ef o rr n a t h eu n i t sa r et h ef o u rn u c l e o t i d er e s i d u e sa ， c 、ga n du ( u r a c i l ) f o rp r o t e i n ，t h eu n i t sa r ct h et w e n t ya m i n oa c i dr e s i d u e sa ( a l a n i n e ) ， c ( c y s t e i n e ) ，d ( a s p a r t i ca c i d ) ，e ( g l u t a m i ca c i d ) ，f ( p h e n y l a l a r l i n e ) g ( g l y c i n e ) ，h ( h i s t i d i n e ) i ( i s o l e u c i n e ) ，k ( 1 y s i n e ) l ( 1 c u e i n e ) m m e t h i o n i n e ) ，n ( a s p a r a g i n e ) ，p ( p r o l i n e ) ，q ( g l u t a m i n e ) ， r ( a r g i n i n e ) ，s ( s e r i n e ) ，t ( t h r e o n i n e ) ，v ( v a l i n e ) ，w ( t r y p t o p h a n ) a n dy ( t y r o s i n e ) t h u s ，a d n a ( r n a ) s e q u e n c e c a nb ei d e n t i f i e dw i t haw o r do v e rt h ea l p h a b e t = ( a ，c ，g ，t ( u ) ) ， a n dap r o t e i ns e q u e n c ec a nb et a k e na 8as t r i n go v e rt w e n t yl e t t e r sw h i l et h es e c o n d a r y s t r u c t u r eo fr n a ( o rd n a li sas e to ff r e eb a s e sa n dp a i r sw h i c hf o r m sb o n d sb e t w e e na u ( o r a t ) a n dc g i ns o m ec o n s i d e r a b l ee x t e n t 、t h es e c o n d a r ys t r u c t u r e so fr n a ( o rd n a ) c a n b er e d u c e di n t ol i n e a rs e q u e n c e s s o 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 s w i l lp l a yi m p o r t a n tr o l e si ns 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 e c u l a ru n i t s a l s o ，w ec a n p 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 o m e t r i c t o p o l o g ya n dg r o u pt h e o r ya r ei m p o r t a n t ，a l s o t h cm a i nc o n t e n t ss i cl i s t e da sf o l l o w s ： i ti sd i f f i c u l tt op r e d i c tt h er n a s e c o n d a r ys t r u c t u r e so fa l ls e q u e n c e sb yp r e d i c t i o n a l g o r i t h m s i nc h a p t e r2 w ec o n s i d e rt h ee n u m e r a t i o np r o b l e m o fr n a s e c o n d a r ys t r u c t u r e s a n ds u b s t ，r u c t u r e s3 sag e n e r a t i o no ft h er e s u l t si np a p e r s 5 7 9 1 f r e ee n e r g yi sn s u a l l yl o o k e du p o n3 , 8t h es t a n d a r dm e a s u r eo ft h e o p t i i n a ls t r u c t u r e s i n c h a p t e r3 ，w ep r e s e n ta l g o r i t h m st oc o m p u t e t h em i n i n m mf r e ee i m r g yo ft h er n a s e c o n d a r y s t r u c t u r ew i t hp s e u d o k n o t so rn o t i nc h a p t e r4 ，w ep r e s e n tt w oa l g o r i t h m sf o rs e a r c h i n gt h el o c a la l i g n m e n ta n dg l o b a l a l i g n m e n to fm r n as e q u e n c e sa n dp r o t e i ns e q u e n c e sa n ds o l v et h el c sp r o b l e m sb e t w e e n b i o l o g i c a ls e q u e n c ea n db i o l o g i c a ls t r u c t u r e i nc h a p t e r5 a c c o r d i n gt ot h ec l a s s i f i c a t i o n so fc h e m i c a ls t r u c t u r eo ff o u rn u c l e o t l d e r e s i d u e sa ，c ，ga n dt ，w ei n t r o d u c eac h a r a c t e r i s t i cr e p r e s e n t a t i o n t w o3 dg r a p h i c a lr e p r e s e n t a t i o n s ，a2 dg n - a p h i c a lr e p r e s e n t a t i o na n da4 dr e p r e s e n t a t i o no fd n a s e q u e n c e sw e c o n s t r u c td i s t a n c em a t r i xa n d l lm a t r i xa s s o c i a t e dw i t ht h ec o o r d i n a t e so ft h ec o r r e s p o n d i n gp l o t f u r t h e r m o r e t h en o r m a l i z e dl e a d i n ge i g e n v a l u e so fl lm a t r i c e sa n dt h ea v e r a g e b a n d w i d t h so fd i s t a n c ea r ec o m p u t e da n dc o n s i d e r e da 8ak i n do fi n v a r i a n t sf o rt h ed n a p r i m a ys e q u e n c e ss i m i l a r i t ya n dd i s s i m i l a r i t ya n a l y s i sb a s e do ni n v a r l a n t so fd n ap r i m a r y s e q u e n c e s a r cg i v e nf o re i g h te x o n l g e n e so f 口一g l o b i na b o u te i g h ts p e c i e s ：h u m a n g o a t l g a l l u s ，o p o s s u m ，l e m u r ，m o u s e ，r a b b i t ，r a t ，b o v i n e g o r i l l aa n dc h i m p a n z e ew p r e s e n ta c h a r a c t e r i s t i cr e p r e s e n t a t i o no fa m i n oa c i db a s e d0 1 2t h ec l a s s i f i c a t i o no fc h e m i c a lp r o p e r t i e s o f2 0a m i n oa c i d s ，p r o p o s et h ed e f i n i t i o n so f ，“一i n d e p e n d e n tc o m p o n e n ta n dc h a r a c t e r i s t i c i n f o r m a t i o ne n t r o p y l q ! r t h o r m o r e ，v em a k ec o m p a r i s o nf 。】s e v e r a l n e l ，r o c a ng o n eb yc o n s t r u c t i n gv e c t o r sc o n s i s t i n go ft h ec h a r a c t e r i s t i ci n f o r m a t i o ne n t r o p ya n df 一i n d e p e n d e n t c o m p o n e n t s ， i nc h a p t e r6 a e c o r d i u gt ot h ec l a s s i f i c a t i o n so fc h e m i c ms t r u c t u r eo ff r e e b a q e sa n db a s e p a i r so fr n as e c o n d a r ys t r u c t u r e s ，w ep r e s e n ta3 dg r a p h i c a lr e p r e s e n t a t i o n a4 1 ) r e p r e s e n t a t i o na n da7 1 ) r e p r e s e n t a t i o na dc o n s t r u c td 谗t a n c em a t r i xa n dl zm a t r i xs i m i l a r i t va n d d i s s i m i l a r i t ya n a l y s i sb a s e do nn o r m a l i z e dl e a d i n ge i g e n v a l u e so fl lm a t r i c e sa n ds t r u c t u r e i n v a r i a n t sa r eg i v e nf o rd j l ) cr n a s e c o n d a r ys t r u c t u r e so fr n a 3o fv i r u s k e y w o r d s ：d n as e q u e n c e s 、c h a r a c t e r i s t i cs e q u e n c e s ，p r o t e i n ，r n as e c o n d a r y8 t r u c t u r e ，d i s t a n c em a t r i x ，l lm a t r i x ，n q r m a t i 2 e dl e a d i n ge i g v a l u e ，s e q u e n c ei n v a r i a r t t 、s 6 r n c c u f e i n v a r i a n t ，m i n i m u mf r e ec n e r g y 0 前言 随着人类基因组计划( h g p ) 实施的进一步深入，生命科学已步入后基因时 代基因和蛋白质已成为现代生命科学的主要研究对象过去，生物科学家们研究单 个基因或蛋白质现在和将来，科学家们将着重于研究d n a 序列信息，蛋白质结构 信息，以及它们之间的相互作用破译每一水平的生物信息提出了与基因或蛋白质有 关的统计和组合数学问题生物信息的的急剧增长也带来了对计算机科学的挑战为 此，计算分子生物学和生物信息学便应运而生。 计算分子生物学( c 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 ) 是- - f 崭新的的交叉学科， 主要是研究分子生物学应用上具有计算复杂度的问题，它吸引了许多计算机科学家， 分子生物学家，数学家，物理学家投入研究计算分子生物学的研究对象是与基因和 蛋白序列有关的组合和计算问题计算分子生物学的主要课题有：序列组合，序列分 析，生物信息资料库，基因认定，种族树的构建以及结构预测等从计算理论的角度 来讲，它们都是难处理的；换句话讲，我们并不知道是否存在有效的算法去解决这些 问题目前的研究集中在设计好的近似算法或概率算法；这些算法虽然并不能对有关 问题的每一个实例都能求出好的解，但对大多数实例却行之有效本文就针对某些算 法的缺陷性，我们考虑用其他方法来试图解决问题。比如我们用几何图形表示的方法 来比较生物序列的相似性 生物信息学是计算分子生物学的”孪生学科人们常常不加区别的使用这两个 学科名称。严格来讲，生物信息学还包括对各种生物信息存储和查询的研究 本文主要涉及计算分子生物学中两大课题： 第一；r n a 二级结构预测。结构预测首先要处理好的两个问题是：结构数的估计和能量 的处理针对目前所有有关r n a 二级结构的预测算法要预测出所有序列的二级结构仍 然很困难，我们就应用组合计数的技巧考虑了r n a 二级结构的计数问题。本文第二章 就解决了带两个参数的r n a 二级结构及其子结构的计数问题，推广了m s w a t e r m a n 等人的结果【5 7 ，9 】目前衡量最优结构的标准大致有两个：最大基对数和最小自由 能，本文第三章给出了两个算法( 带假结和不带假结) 计算k n a 二级结构的最小自 由能。 第二：序列分析( 含结构分析) 本文主要有以下几方面的成果： 大连理工大学博士学位论文：计算分子生物学中若干问题研究 1 ，目前所有有关两个序列的对比或多重序列对比算法都只限于生物序列之间一对一的 比较，( 即核苷酸与核苷酸的一一对应) 而在破译人体密码时，一个氨基酸对应三个 核苷酸，为了判断m r n a 序列和蛋白序列之间的关系，我们给出了m r n a 序列和蛋 白序列的局部对比和全局对比算法 2 序列的比较是字符上的比较，它们的差异性体现在彼此间存在不同的子序列或子结 构，而相似性体现在它们有共同的子序列或子结构，因此我们很自然的会想到寻找生 物序列的最长公共子序列或生物结构的最大公共子结构，这就是所谓的l c s 问题本 文解决了t e q a 二级结构的l c s 问题 3 根据d n a 核苷酸a ，g ，t ，c 的化学结构分类，给出了d n a 序列的一种特征表示法， 提出了特征信息熵的概念，构造了一类3 8 压缩矩阵，利用特征信息熵比较了一类 不同物种的同一段基因序列之间的相似性 4 根据2 0 种氨基酸的化学性质分类，给出了氨基酸序列的一种特征表示，提出了，x 独立成分和特征信息熵的概念，利用矩阵不变量，特征信息熵和，x 独立成分构造向 量比较了几种动物的神经元基因序列，得到了与实际基本相符的结果。5 ，由于序列比 对算法只是字符串的比较算法，只是考虑字符串本身，没有考虑字符串组成成分的化 学结构和化学性质以及本身的结构，并且比较的结果完全取决于罚分函数的建立为 了避免这些缺陷，我们考虑用几何图形来表示生物序列，本文给出了d n a 序列两种 3 - d 图形表示，一种二维图形表示和一种4 d 表示法，引入d d ，m m ，l l 矩阵， 利用矩阵不变量和序列不变量进行相似性分析 6 利用d n a 序列构成的三联体( 不同于遗传密码) 来比较d n a 序列的相似性，给出 了三联体一种6 d 表示法 7 根据r n a 二级结构组成和核苷酸a ，c ，g ，u 的化学结构分类，给出了r n a 二级结 构的一种三维图形表示，一种4 - d 和7 - d 表示法，利用正规化最大特征值和结构不变 量分别构造3 维，5 维，1 0 维，1 5 维向量进行相似佳分析 2 1 分子生物学知识概论 生命的基本单位是细胞，它是由细胞膜、细胞质和细胞核三者组成， 遗传信息储存在细胞核中细胞的分子有两类：大分子和小分子大分子有 三种类型：d n a ，r n a 和蛋白，这些是我们感兴趣的分子，它们是由某 些小分子聚合在一起形成的 1 1 d n a ，r n a 和蛋白 d n a 是遗传特征的基础，它是由称为核苷酸的小分子生成的聚合物核苷酸有 四种，可用四个基来区分：a ( 腺嘌呤) 、c ( 胞嘧啶) 、g ( 鸟嘌呤) 和t ( 胸腺嘧啶) 一般地，我们可以把d n a 分子看成是字符集n = a ，g g ，t ) 上的词细胞里还有另 一种核酸r n a ，对于r n a ，它的组成单元是a 、c 、g 和u ( 尿嘧啶) ，r n a 分子 同样可以看作是字符集n + = 且，g ，g ，以上的词这些分子都是有方向性的，左端通 常记为5 7 ，另一端记为3 蛋白质也是聚合物，是2 0 种氨基酸字符集上的词。表1 2 是2 0 种氨基酸的组成及一个字母或三个字母的缩写表示，蛋白也有方向性 表1 - 1 ：d n a ，r n a 的化学结构 d n ar n a 腺嘌呤【a d e n i n e ，a )腺嘌呤( a d e n i n e ，a ) 碱基 鸟嘌呤( g u a n i n e ，g )鸟嘌呤( g u a n i n e ，g ) 胞嘧啶( c y t o s i n e ，g )胞嘧啶( c y t o s i n e ，c ) 胸腺嘧啶( t h y m i n e ，t )尿嘧啶( u r a c i l ，u ) 戊糖脱氧核糖( d e o x y r i b o s e )核糖( r i b o s e ) 磷酸磷酸磷酸 d n a 蕴涵的复制机制的关键特征是互补基对：a 与t 配对，g 和e 配对，这种 配对是由于氢键作用，其原理是：单链( 或单个词) 按从5 7 到3 7 的次序与相反方向的互 补链配对，这样就形成d n a 的双螺旋结构如单链5 7 a c c t g a c 3 与3 t g g a c t g 5 配对( 见图1 1 ) 3 大连理工大学博士学位论文：计算分子生物学中若干问题研究 5 cctgc， 川liill f 了tc-gcib 掣 在r n a 分子中a 与u 配对，g 和c 配对构成r n a 的二级结构，这对参与蛋白 质的合成起着决定性的作用核酸是遗传信息的携带者，而蛋白质是信息转化为生物 结构和功能的表达者蛋白质按外形和在生物组织中的位置和作用，可分为三大类： 纤维蛋白( f i b r o u sp r o t e i n ) ，膜蛋白和球蛋白。其中球蛋白的种类最多，功能也最重要 一般地，球蛋白质的结构分为一级结构、二级结构和三级结构，除此之外还有超二级 结构和四级结构等它的一级结构就是指这个蛋白质的氨基酸本原序列二级结构是 指蛋白质多肽主链在空间中的趋向，是一级结构通过折叠产生的二级结构中主要由 两类：a 螺旋和卢折叠蛋白质的三级结构是蛋白质的肽链中所有肽键和残基( 包括 侧链) 键的相对位置。 1 2 中心定理与遗传密码 d n a 携带遗传材料，即生物功能所要求的信息( 某些病毒除外，它们的遗传材料 是r n a ) ，而且生物体通过d n a 将遗传信息传给下一代在真核生物中，d n a 被保 存在细胞核内，而由细胞质形成的蛋白质在细胞核的外面，携带核外信息的中间分子 是r n a 1 9 5 8 年f r a n c i sc r i c k 提出的中心定理概括了生物中的信息流的方向 中心定理：生物的信息是由一个核酸传给另一个核酸，也可能从核酸传给蛋白质。 但一旦信息传入蛋白质，它就不能再出来这里的信息是指已知确定的序列，或者是 核酸中碱基序列，或者是蛋白质中的氨基酸序列简单地说，d n a 双螺旋是遗传信 息的携带者，它在一定条件下可以准确地自我复制遗传信息只能通过最终的蛋白质 产物体现或表达 中，5 - 定理的模式是： o d n a - - - + m r n a 蛋白质 从d n a 到d n a 的环是指d n a 分子可以被拷贝，这个过程被称为复制从d n a 到r n a 的箭头被称为转录另外m r n a 可以反转录成c d n a 在进入下一个箭头前， r n a 分子要被加工，即去掉那些不编码的碱基留下编码的部分之后是从r n a 到蛋 白质的过程，这个过程我们称为翻译在翻译过程中，每三个碱基构成一个三联体，对 应一个氨基酸或者一个停止密码子我们称这种对应为遗传编码，可数学地表示为： 设 厂= a ，a g ，矿( t ) ) 是核酸集合，刀= ( 1 x 2 。3 ) ：观) ，万是氨基酸和停止 密码子的集合，遗传编码就是一个映射g ：刀斗刁。下面的表1 2 列出了这个对应， 4 第1 章分子生物学知识概论 除u a a ，u a g 和u g a 表示三个终止密码外。 g e n e t i cc o d e氨基酸 f3 个字母i1 个字母 g c u ，g c c g c a ，g c g a l a n i n e l a l a l a c g u ，c g c c g a ，c g ga r g l n i n e ia r gf r g a u ，g a c a 3 p a r t i ca c i dfa s pf d a a u a a ca s p 罅r g i n i n e l a s h i n u g u u g c o 螂e i nlg y 81 c g a a g a g g l u t a m i ca c i d i g l u l e c a a c a g 百u t a r a i n e f g i n fq g g u ，g g c ，g g a g g gg l y c l n e ig l yi g c a u ，c a ch i s t i n e i h i s l h a u u a u c ，a u ai s o t e u c i n e1 i l e i i c u u ，c u c ，c u a ，g u g ，u u a ，u u g l e u c i n e f l e u f l a a a a a g l y s i n e il y si k a u gm e t h i o n i n elm 甙1m u u u u u c p h e n y l a l a n i n ei p h e l f c c u c c c ，c c a ，c c gp r o l i n e ip r oip u c u ，u c c ，u c a ，u c g s e r i n e i s e r i s a c u ，a c c a c a a c g t h r e o n i n e i t h r 1 t u g g t r y p t o p h a nit r pl w u a u u a c 时r p t o p h a s n ft y r i y g u u ，g u c ，g u a ，g u g v a l i n e l v a l 1 v 从表中可以看出，在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 ) 是单重 编码 5 2 r n a 二级结构及子结构的计数 r n a ( 即t r n a ，r r n a ，m r n a 和s n r n a ) 有两大主要功能：一是某些病毒的遗传 物质；二是参与蛋白质的合成这些与细胞分化，代谢，记忆的储存等有重要关系 为了更好的了解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 的高级结构是一种很经 济的手段。近些年来，有关r n a 分子二级结构的研究一直很活跃，给出了不少预 测方法如m a x i m a lm a t c h i n g 方法【3 】，m i n i m a lf r e ee n e r g y 方法【2 【3 】，d y n a m i c p r o g r a m m i n ga l g o r i t h m s 5 】以及t r e ea d j o i n i n gg r a m m a r s 6 等，并编写了程序，预测 了许多r n a 分子的二级结构，不过许多预测结果与实验结果常有出入，结构不稳 定 所谓r n a 二级结构的预测，就是计算给定长度的r n a 序列的最优结构目前所 有预测算法要预测出所有序列的二级结构仍然非常困难，自然估计给定长度的所有 可能的二级结构数则成了数学任务。这些结果在负面意义上对生物学有用，它肯定 了存在巨大数量的特殊结构数，直接枚举是没有希望的，并且它间接地决定了预测 算法的时间复杂性和空间复杂性。在本章中我们应用组合计数的技巧，考虑了r n a 二级结构及子结构的计数问题 文献f 5 7 ，9 j 都讨论了r n a 二级结构的计数问题，但这些文章都只给出一个 参数( 多数以发夹环中最小未成对基数为参数) ，讨论了几类带限制条件的的r n a 二级结构的计数问题本文以端环中自由基数为参数考虑了r n a 二级结构及其子 结构的计数问题，并同时引入两个参数m ( 发夹环中最小自由基数) 和f ( 组套的 最小长度) 考虑了r n a 二级结构计数问题的一般情形 7 大连理工大学博士学位论文：计算分子生物学中若干问题研究 2 1 基本概念和引理 2 1 1 i t _ n a = 级结构和子结构的定义 单链的r n a 分子通过自身回折，使链中a 和u ，g 和c 之间分别配对，形成多端 的双股螺旋区即为r n a 的二级结构，这是生物学上的定义二级结构中的碱基分为两 类，没有与别的碱基匹配形成氢键的称为自由基( 丘e eb a s e ) ，否则称为匹配基( p a i r ) 我们规定( i ) 用i ，i + 1 ，i + 2 等分别表示第i ，i + 1 ，i + 2 个碱基哦，啦+ 1 ，啦+ 2 ( 从5 端开始 算起) ( i i ) 若a 与q 匹配，用( i ，j ) 表示碱基对( i i i ) 如果k f ，且与f 匹 配，则称i 在碱基对( ，z ) 的内部 i r n a 二级结构( 不带假结p s e u d o k n o t ) 的数学定义：线性序列a = 0 1 口2 口。，啦 ( a ，c ，g ，叫， = 1 ，2 ，n ，将其视为札个顶点的标号图，其邻接距阵a = ( a i d ) 满足： ( i ) 口t ， + 1 = 1 ，1 i n 一1 ( i i ) 对任意的i ，至多存在一个 i 一1 ，i + 1 满足n t ，t = l ( i i i ) 若口t ，f = 1 _ 1 且t k j ，则有l a o 使得 ( i ) 对某个6 0 ，f ( z ，c ) ) 在 r + 6 ， 。+ 6 中解析； ( i i ) f ( r ，s ) = 兄( ns ) = 0 ； ( i i i ) f ：( r ，s ) ，j ( n5 ) 不等于零； ( i v ) 在i = lsn l u l s 中若f ( z ，u ) = 咒( 。，w ) = 0 贝4 。n 一( 蔫) 1 2 f , - - n + n 司7 2 ( 2 1 1 ) 其中e ，咯在z = r u = s 处计算 引理2 1 _ 2 2 【9 】假设y n 0 ，( z ) = 罂o y n x “满足g ( 。) = 卢( z ) + ( 1 一詈严，其中q 是 大于零的实数，卢( z ) 在a 附近解析，u 并非非负整数如果( 正) 在邻域 o 中解 析，且x = o t 是y ( x ) 在其收敛环上的唯一奇异解，那么 y a 一器n - - i - - w ( 去) “ ( 2 1 2 ) 1 n 第2 章r n a 二级结构及子结构的计数 引理2 1 _ 2 3 9 】假设毋( z ，y ) 在h q + j ， 0 内解析，且( 。) = 卢( z ) + ( 1 一詈) 1 2 9 ( z ) ，设序列 ) 的发生函数为z ( z ) = 袅o 扩，且z = 垂( z ，) ，则 l i m n 一+ 。= 西( a ，卢( a ) ) 笋n 。 ( 2 1 3 ) 引理2 1 2 4 1 9 1 解析函数圣( 。，) 同引理2 1 2 3 ，( 。) = 卢( z ) + ( 1 一：) 1 2 9 ( z ) ，设序列 ( 卸 的发生函数为z ( z ) = e 器o 扩，且z ( z ) = 石可壬( $ ，) ，此处卢= 卢( a ) ，则 z 。2 圣( a ，卢) “ 磊“i 丽 ( 2 1 4 ) 此处b 。一h 表示1 i n h _ + m 鲁= 1 引理2 1 2 5 9 】设 1 ，n 上发夹环中自由基的最小个数为m 且最小组套长为 的二级 结构数为；【1 ，n 】上发夹环中自由基的最小个数为m 且仅连接末端碱基对的组套长 至少为f 的二级结构数为螃；【1 ，州上发夹环中自由基的最小个数为m ，最小组套长为 j 且( 1 ，n ) 不是基对的二级结构数为妒# ，则，惦，币满足 皿n + l ( f ) = 皿n ( f ) + 譬未+ 2 l 一2 皿：( f ) 皿n k l “) ，n 兰m + 2 l 皿：( f ) = 瘩2 7 2 皿甚2 ( f ) 礼m + 2 1 ? ( f ) = 皿n ( f ) 一皿：一2 ( ：) ，n m + 2 1 皿算1 ( f ) = 雪。( f ) + 器矗+ 2 i 一2 皿；( f ) 皿n k l ( z ) ，n2 m + 2 l 皿。( f ) = 皿? ( f ) = l ，皿：( f ) = 0 ，礼 m - t - 2 1( 2 1 _ 5 ) 引理2 1 2 6 9 令妒( z ) = e 罢。皿n ( f ) 扩，咖( z ) = 器。冁( f ) p ，口( z ) = 忍o m ( f ) 扩，则 母= 1 + z 妒+ 。2 伽 ，2 ( 1 一1 ) = * i ( 日一( 。) ) 目= 妒一z 2 西( 2 1 6 ) 引理2 1 2 7 【9 皿。一- 。c 。t 。r l _ 一3 2 ( ：p 此处。是方程p ( z ) = ( 1 - - x ) ! i - - x 2 + z 2 ) + 2 吒m ( z ) 】2 4 2 2 ( 1 一z 2 + z 2 2 ) = 0 的最小正 解，且满足9 ( a ) = ； 一n 掣i 。0 引理2 1 2 8 【9 设( = e ：爵扩，( z ) = 芝 k 一，如果f _ 1 ，则 删= 等 ，、 3 口一l ( 1 2 a ) 2 ( q ) 2 而一葫t 二訇 张a ) = 生攀铲 ( 2 1 7 ) 大连理工大学博士学位论文：计算分子生物学中若干问题研究 引埋2 1 2 9 6 j 设一端碱基数为6 ，另一端碱基数为。的臂数为k ( o ，b ) ，则 耳( 。，6 ) = a 吉皇i2 ) ( 2 ，18 ) 定理2 1 2 1 0 l i 一器= 万1 ( 2 1 9 ) 证明：由引理2 1 2 5 得 咖= 掣 应用引理2 i 2 3 定理即得证 口 定理2 1 2 1 1 一器= 崧 协“ 证明：由引理2 1 2 5 得 舄( z ) = 生掣掣+ 撕) 2 2 限制端环基数的r n a 二级结构及子结构的计数 在以前的研究中，有关r n a 二级结构的计数都是以任意发夹环中自由基数为参 量，而端环是发夹环的一种特殊形式，本节就以端环中自由基数为参量，考虑了r n a 二级结构的计数设端环中自由基个数的最小值为m ，通常说的二级结构就是m = 1 的情况通常 1 ，礼- 4 - 1 】上任意二级结构可由( 1 ，n 】上二级结构通过如下两种方式获得： ( i ) 在末端添加一自由基( 事实上是插入一外点) ( i i ) 插入一碱基对( i ，4 - 2 ) ，k m 或者插入一碱基对( ，n4 - 1 ) ，n 一兰m ( 见下图) 插入自由基 12k丑n 十1 插入基对 ( 1 ，h 2 ) 、。卜。 12k + 2na + l 1 2 第2 章r n a 二级结构及子结构的计数 2 2 1 递推关系 定理2 2 11 设s ( n ) 是序列 1 ，川上m = 0 时的二级结构数，s ( o ) = 1 ，则 n - 2 s ( n ) = s ( n 一1 ) + s u ) s ( n 一2 一j ) ( 22 1 ) j = o 证明：对于n = 1 ，唯一的二级结构是”，假定对1 k