（计算机应用技术专业论文）随机文法在rna二级结构预测中的应用研究.pdf

摘要r n a 是一类重要的生物大分子，对r n a 二级结构的研究是当今计算分子生物学的一个前沿课题。r n a 单链由四种碱基( a 、c 、g 、u )排列组成，r n a z 级结构是指e h r n a 单链通过自身回折而形成部分碱基配对和单链交替出现的茎环结构，当r n a 单链中碱基出现交叉配对现象时就构成假结。r n a 的功能与其二级结构密切相关。本文采用随机文法的方法预测r n a 的二级结构。随机文法方法把r n a 序列看成是具有一定语法规则的语句，通过这些语法规则来分析r n a 序列中存在的碱基配对关系，也就是它的语义，从而得到该序列的二级结构。由于它是一种基于已有序列的先验知识的方法，需要拥有一定数量的相关序列样本，而且需要确保这些序列具有某些一致的二级结构和一些共同的基本结构单元。这样就能通过一种概率模型，把序列样本所具有的保守二级结构的统计信息加以利用，使预测结果具有很高的精度。通过扩展随机上下文无关文法使这种方法能考虑r n a z 级结构中假结的存在，预测结果将更加真实，而单纯的最小自由能方法是无法预测假结的。本文提出了一种语法二次分析的预测方法，先采用词条方法对r n a z - 级结构进行预处理，将r n a 序列划分成词条结构，再使用随机文法模型利用已获得的词条结构信息识别出各 中r n a 的二级结构。关键词随机文法，r n a ，二级结构，结构预测，假结a b s t r a c tr n ai sa ni m p o r t a n tb i o l o g i c a lm a c r o m o l e c u l a r , t h u st h ep r o b l e mo fp r e d i c t i n gr n as e c o n d a r ys t r u c t u r e si sah o tt o p i ci nt h ec u r r e n tr e s e a r c hf i e l do fc 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 r n ai sas i n g l es t r a n dm a d eo ft h er i b o n u c l e o t i d 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 du ( u r a c i l ) r n as e q u e n c e sf o l do v e ro n t ot h e m s e l v e st of o r md o u b l e 。s t r a n d e dr e g i o n so fb a s ep a i r i n g sa n du n p a i r e ds i n g l es t r a n dc a l l e dr n as e c o n d a r ys t r u c t u r ew h i c hl i k eas t e m - l o o ps t r u c t u r e w h e nc r o s s i n gp a t t e r n so fb a s e - p a i r i n g sa p p e a ro nr n as e q u e n c e ，w ec a l li tf o r m i n gp s e u d o k n o t s r n as e c o n d a r ys t r u c t u r e sa r ei m p o r t a n ti nt h em o l e c u l a rm e c h a n i s m si n v o l v i n gt h e i rf u n c t i o n si nt h i sp a p e rw ea d o p tam e t h o db a s e do ns t o c h a s t i cg r a m m a r st op r e d i c tr n as e c o n d a r ys t r u c t u r e s s t o c h a s t i cg r a m m a rf o rr n am o d e l i n gr e g a r d sr n as e q u e n c e sa sat y p eo fs e n t e n c e sw h i c hp o s s e s sas e to fs y n t a xr u l e s a n da n a l y s i n gt h e i rb a s e - p a i r e dr e l a t i o n s h i p si nr n as e q u e n c e st h r o u g ht h e s es y n t a xr u l e s c o n s e q u e n t l yw ec o u l df i n dt h es e q u e n c ec o r r e s p o n d i n gs e c o n d a r ys t r u c t u r e b e c a u s et h i sm e t h o di sb a s e do nap r i o rk n o w l e d g eo fs e q u e n c e s ，s of i r s t l yw em u s th a v ean u m b e ro fr e l e v a n ts e q u e n c e ss e t ，a n de n s u r et h i ss e to fs e q u e n c e sh a v es o m ec o n s i s t e n ts t r u c t u r eu n i t s s e c o n d l yw ec a nu s eap r o b a b i l i s t i cm o d e l sm a k i n gu s eo ft h es t a t i s t i c a li n f o r m a t i o no fc o n s e n s u ss e c o n d a r yi is t r u c t u r e s t h e r e f o r et h ep r e d i c t i o nr e s u l t sa r em u c hm o r ep r e c i s eb e s i d e s ，t h r o u g he x p a n d i n gs t o c h a s t i cc o n t e x t f r e eg r a m m a r ，t h i sm e t h o dc a ne a s i l yt a k ep s e u d o k n o t si n t oa c c o u n t ，s ot h er e s u l t sa r em o r er e a l i s t i c ，b yc o n t r a s tw i t h ，t h ef r e e e n e r g ym i n i m i z a t i o nm e t h o dc a n n o tc o n s i d e rp s e u d o k n o t s t h i sd i s s e r t a t i o np r o p o s e dat w i c ea n a l y z i n gb a s e do ng r a m m a rp r e d i c t i o nm e t h o d ，t h ef i r s ts t e pi st od i v i d et h es e q u e n c ei n t ol e m m as t r u c t u r e ，t h e ne m p l o ys t o c h a s t i cg r a m m a rm e t h o dt oi d e n t i f yd i s t i n c ts e c o n d a r ys t r u c t u r eu n i t sk e y w o r d ss t o c h a s t i cg r a m m a r ，r n a ，s e c o n d a r ys t r u c t u r e ，s t r u c t u r ep r e d i c t i o n ，p s e u d o k n o t si i i原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：垄塑耋；日期：兰竺年土月卫日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：避导师签名询继日期：丛年上月鱼日硕士学位论文第一章绪论第一章绪论1 1 本课题研究的领域和目的随着2 0 世纪后半叶分子生物学的长足进展，人们把生命活动的物质基础追溯到核酸和蛋白质这两类生物大分子上，并对这些生物大分子序列进行了测序，它们构成了当前生物数据的主要部分。据统计，目前一个典型的生物基因测序中心，每年可以产生1 0 “字节即1 0 00 0 0 g b 原始数据，如何理解这些生物序列数据，解读生物的遗传密码成为计算分子生物学的一项重要任务。其中，通过分析生物大分子的序列来推断其空间结构，力图从结构上来阐明和发掘其生物学意义和功能，称为计算分子生物学上的结构预测，目前结构预测研究的热点包括r n a二级结构预测和蛋白质的三维结构预测【2 】or n a ( 核糖核酸) 是一类重要的生物大分子，随着对r n a 研究的逐步深入，人们再也不像过去那样，仅仅把r n a 看成从d n a 到蛋白质之间的一种信息传递中介，r n a 正在从人们眼中简单的、线性的、功能单一的形象演变成今天种类多样、结构复杂、功能特异的新形象，并且逐渐在中心法则中取得了与d n a和蛋白质同等重要的位置，如图1 1 所示。人们普遍相信，生命始于r n a ，在还没有d n a 和蛋白质的时候，存在着一个“r n a 世界”，此时r n a 既充当信息传递的基因组，又充当信息表达的功能分子口】。复制a 石枭r n a 塑。蛋白质地转求。一自我复带归。li 、忒a 冀垂- - - r n a、r n 一- 奠竖图卜1 中。法则及其演变( 虚线代表罕见情况)r n a 在基因表达的各个阶段扮演着不同的结构和功能的角色，信使r n a( m r n a ) 、转运r n a ( t r n a ) 和核糖体r n a ( r r n a ) 这三种主要r n a 直接参与了蛋白质的翻译过程。这使得r n a 的功能正得到人们的日益关注，而功能与结构是密切相关的，因此r r n a 在核糖体中的催化机制的形成，m r n a 前体在转录后水平的选择性剪接，m r n a 自身的稳定性及其翻译效率，s n r n a 与蛋白q硕士学位论文第一章绪论质的相互作用以及作为信号识别颗粒的机制，r n a 酶对t r n a 和r r n a 的转录后加工，反义r n a 在翻译水平上的调控作用等许多问题都在促使人们对r n a的具体结构进行更深入的理解。1 2r n a 二级结构的特点及研究意义1 2 1r n a 二级结构的特点与d n a 分子不同，r n a 是由多个核苷酸聚合而成的一种单链高分子化合物，其多核苷酸链可通过自身回折而形成复杂的彼此配对的双螺旋区及不配对的无规则环区，而d n a 的二级结构相对简单，它是由两条核苷酸链环绕组成的相对均的双螺旋结构。r n a 这种可形成高级结构的能力使其比d n a 具有更大的构象多样性，使r n a 还具有了同蛋白质一样的催化功能。在很多种情况下，对于r n a 来说其结构构成上的生物学意义要远大于它的序列组成，例如很多同源的r n a 有着相同或相似的二级结构或三级结构，然而却在一级结构上很少有什么有意义的相似序列。只要维持其原来的碱基互补状况，即使对序列进行很大程度的补偿突变( c o m p e n s a t o r ym u t a t i o n s ) 常常也是可以容忍的，即对于r n a 在功能上没有多少太大的影响【4 j 。也就是说，这些r n a 的同源性更多的是建立在对其特定的二级结构具有保守性，而不是具有哪一段保守的序列，它们所具有的功能活性也是由它们特定的结构所决定的。这一点可以从t r n a分子上很明显的看到，所有t r n a 分子的二级结构都呈三叶草形，三级结构都呈倒三形。正是这种结构上的一致性决定了它们功能上的一致。当编码蛋白质的基因结构变得相对容易鉴别的时候，编码r n a 的基因目前还不好鉴别，加深对这些序列的了解，加快对结构化功能r n a 的研究已经提上议事日程。1 2 2r 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 空间结构效率的一个捷径，也是未来应该主要依靠的方法。1 3 国内外研究的现状虽然用生物化学的实验方法可以完全准确的测出r n a 分子的空间立体结构，目前使用的实验方法主要是x 射线晶体衍射法，但这种方法费时费力而且代价高昂。使用计算方法预测r n a 的二级结构已经有3 0 多年的历史，由于r n a 二级结构的复杂性，人们在解决问题时总是从各种不同的角度尽可能的尝试各种可行的手段去考虑它，希望能找到更好的方法，因此也就产生了各种各样的方法，可以说是五花八门层出不穷。尽管计算方法有时只能提供r n a 结构的近似模型，但它为进一步研究r n a 提供了很大的帮助。目前，r n a 二级结构的预测方法主要有两类：其一是基于热力学的最小自由能计分方法，其二是基于随机文法的比较序列分析方法。总的趋势就是相互之间取长补短，尽可能把各种有用的信息都利用上，在尽量减少计算复杂度的情况下，使自己的计算结果更加接近于真实的情况。1 3 1 最小自由能方法最小自由能方法基于目前一种普遍认同的假设，即r n a 的自然二级结构应该是稳定的，根据热力学的理论，物体在稳定状态时其自由能应该是最小的，对r n a 序列给定含有自由能参数的热力学模型，就可求得自由能最小的二级结构。但某些r n a 分子特别是较长的r n a 由于受所处细胞内溶剂环境等因素的影响，其自然结构的自由能并非最低，而是处于一种次低的状态”j 。这时这类算法的预测准确性就将受到一定影响。最小自由能方法实际上是基于某种最优化算法的，如遗传算法，模拟退火算法，粒子群算法等，也可以是这些算法的组合。1 3 2 随机文法方法随机文法方法把r n a 序列看成是具有一定语法规则的语句，通过这些语法规则来分析r n a 序列中存在的碱基配对关系，也就是它的语义，从而得到该序列的二级结构。该方法的缺点是计算复杂度较高，并且由于它是一种基于已有序列的先验知识的方法，需要拥有一定数量的相关序列样本，而且需要确保这些序列具有某些一致的二级结构和一些共同的基本结构单元。因此，这种方法实施起来不光要有待测序列还要选择好相关序列样本，显得比最小自由能方法麻烦。尽管目前随机文法方法预测r n a 二级结构还有这么多的缺点，使它得不到硕士学位论文第一章绪论足够的重视，但要看到它是一种比较序列分析的方法，只要拥有可靠的相关序列集，随机文法方法就能通过一种概率模型把序列样本所具有的保守二级结构的统计信息加以利用，使预测结果具有很高的精度。目前最小自由能方法预测的精度一般只有7 0 左右，而比较序列分析方法的精度有时能达到9 0 以上【6 j 。而且人们能在随机文法的基础上开发出许多更复杂的文法模型( 如并行通信文法、邻接树文法等) 或专门开发一种语言用来描述假结 7 1 ，这使它能考虑r n a 结构中假结的存在，预测结果将更真实，而单纯的最小自由能方法是无法预测假结的。因此说，基于比较序列分析的随机文法预测r n a 二级结构的方法只要作一些改进，还是有很广泛的应用前景的。1 3 , 3 评价预测算法的标准由于r n a 序列复杂多样，涉及的参数多，数据量大，另外也受到当前计算机计算能力的限制，使r n a 二级结构预测方法发展的总趋势是以种算法为主，并结合其他算法的优势，在结果上相互印证相互补充。因此，要评价一神r n a二级结构预测算法的好坏，主要可考察以下几方面：1 算法的有效性和复杂度，包括预测结果的准确性，可计算序列的长度以及在计算时间和存储空间上的耗费等；2 能否预测假结等更复杂的结构：3 能否充分利用已有的实验数据，在利用这些数据时算法能否有着方便简易的可扩充性：4 能否充分利用各种合理信息，如热力学信息、序列统计分析信息、系统发育信息等。1 4 本文完成的主要工作1 阅读了大量的国内外相关结构预测的研究文献，介绍并比较了当今r n a二级结构预测的两种常用的方法，特别是随机文法方法和比较序列分析理论。z 提出了一种二次分析的预测方法，先采用词条方法对r n a 二级结构进行预处理，将r n a 序列划分成词条结构，再使用随机文法模型利用己获得的词条结构信息识剐出各种r n a 的二级结构，包括假结。力图在r n a 二级结构预测的理论上有所创新。3 对基于随机上下文无关文法的r n a 二级结构建模及预测方法进行了改进，改进后的预测方法可以对带有假结的r n a 二级结构进行统一建模，使预测模型更接近于r n a 二级结构的真实情况。并利用并行文法的特点提高了算法的效率，算法在计算时间及存储空间上的耗费明显减少。4 ，给出了一套r n a 二级结构预测从理论到算法再到实验的整个方案，采用b i o j a v a 编程对预测算法进行了实际测试。硕士学位论文第二章r n a 二级结构及其数学模型第二章r n a 二级结构及其数学模型21r n a 结构的划分r n a 结构的划分和蛋白质类似，也可以分为一级结构、二级结构、三级结构等类型。一级结构是指r n a 单链中由四种核苷酸排列而成的有限线性序列，如图2 1 ( a ) 所示。二级结构是指r n a 序列通过自身回折而形成部分碱基配对和单链交替出现的茎环结构；三级结构则是由各二级结构单元之f i l $ h 互作用并在空间中形成稳定的地位和取向而构成的，如图2 一l ( c ) 所示的一种t r n a ，三级结构呈常见的到l 型。无论是蛋白质还是r n a ，直接从其一级结构预测其三级结构，目前进展都不顺利。而r n a 二级结构是三级结构的严格子集，它只需考虑序列在二维平面上的排布，为r n a 的结构预测提供了独特的计算模型。图2 - 1 ( b ) 给出了一个r n a 二级结构模型，其中包含了r n a 二级结构中各种基本单元。由a ，u ，g ，c 四种碱基组成的r n a 单链序列，通过序列内部a u 、g c 或g u 的碱基配对进行折叠而形成各种各样的形状，连续的碱基配对相互堆积而构成茎，茎在三维空间中看就是一段a 型双螺旋结构。不形成互补配对的单链结构称为环，根据形态的不同，茎中间若出现少数不配对的碱基则会形成突环或内环。相邻连续的一段序列因两端互补而回折，就会形成象发卡一样的结构，连茎带环的形状称为发卡环。连接各发卡环而未能配对的区域叫做多分支环。序列末端没有形成配对的单链叫做自由单链。5 ，- - a a c g g a a c c a a c a u g g a u u c a u g c u u c g g c c c u g g u c g c g 3 图2 1 ( a )r n a 的一级结构，由碱基组成的有限线性序列5 粕孵掸链口3 c g g ，娇多懈图acagc蚜图2 - 1 ( b ) r n a 的二级结构发怖蝈硕士学位论文第二章r n a 二级结构及其数学模型0 h 氯堪受端图2 - i ( c ) r n a 的三级结构( 酵母苯丙氨酸t r n a 8 1 )2 2r n a 二级结构的定义为了便于用计算方法对r n a 的二级结构进行预测，以及加深对r n a 二级结构的理解。有必要先给出r n a 二级结构的数学模型，本文中r n a 茎环结构的定义来源于文献 2 ，略有一些不同；假结的定义则来自于文献 9 。定义l ：r n a 一级结构是取自字母表= a ，u ，g ，c l 的字符串r ：r = r l ，r2 ，t 。r 。其中r 的左端代表四种碱基序列的起点，通常用5 表示；右端代表终点，通常用3 表示。该字符串代表了由四种碱基组成的起始于5 终止于3 的有向生物单链。r n a 序列通过分子内部的基对进行自身折叠并由构成基对的氢键稳定其结构，基对的形式主要有三种：g c ( c g ) 、a u ( u a ) 和g u ( u a ) 。其中，前两种基对称为w a t s o n c r i c k 基对( 能量较强) ，后一种基对称为不稳定基对。r n a 二级结构正是以基对为特征的，下面给出不包含假结的r n a 二级结构的定义。定义2 ：假设用i j 表示构成基对的碱基r 。和r ，其中1 i j n 。设s为一级结构r 的基对集合，则s 被称为r n a 的二级结构，如果s 满足下列条件：( 1 ) 对于任意两基对i 。j 。和i 。j ：，要么i 。= i 。且j 。；j ：，要么i 。i 。，i 。j 。，j t i ：且j 。j 。：( 2 ) 如果h i j k 则s 不能同时包含h i 和j k ：( 3 )如果s 包含i j ，则j j i 4 。硕士学位论文第二章r n a 二级结构及其数学模型其中，条件1 表明碱基存在于二级结构中只有两种形式：与别的碱基匹配形成匹配基( b a s ep a i r ) ，否则称为自由基( f r e eb a s e ) 。条件2 通常也称不交叉条件，如果不能满足条件2 和条件3 ，则可能出现假结等其他三维结构。定义3 ：设r l = r 。r h 。i 叫( 1 和r 2 = r j r j 小r j _ k + l 是r n a 序列r 的两个子序列，如果r 。和如中的碱基依次互补配对，即( r 。，r 。t = o ，1 ，k - 1 ) 满足定义2 中的性质，则称r ，和r ：在r 的二级结构中构成一段茎，记为s ( i ，j ，k ) ，并称r ，为茎的前段，r 。为茎的后段。s ( i ，j ，k ) 中的i 和j 分别表示茎在序列r 中的5 端起始位置和3 端结束位置，k 表示茎的长度，这里假定茎的长度k 3 ，因为一般认为少于3 对连续的碱基配对是不稳定的。2 3 子结构的定义堆积( s t a c k i n g ) 指包含连续的碱基对( i - k , j + k ) ，( i - k + ld + k 1 ) ，( i j ) 且( i - k l j + k + 1 ) ，( i + 1 j 1 ) 都不是碱基对，其长度为k + 1 ，( i - k j + k ) 为堆积的末端。e n d l 0 0 di n t e r i o ri 0r n u l t i b r e n g hl o o pe x t e r n a lv 6 _图2 2r n a 二级结构的子结构定义4 ：一个发卡环末端只含有一个碱基对；一个内环两端共含有两个碱基对；一个多分支环是边缘含有三个或多于三个碱基对的环；突环是只含有一个不配对碱基的环；未配对单链是不在任何环内的自由碱基；连续的堆积区称为茎。2 4 假结的定义r n a 二级结构中的碱基配对通常是以嵌套的模式( n e s t e df a s h i o n ) 出现的，即对于二级结构中的任意两对配对碱基i j 和i7 j7 ，它们的位置关系应当满足i i j j 或i j i j ( 假设i i ) 。当非嵌套情形或者说交叉现象出现时，此时i ( i j j ，那么就称之为假结( p s e u d o k n o t s ) ，见图2 3 ( a ) 。假结属于不规范的二级结构，有些文献也把它列为三级结构当中，相对于嵌套的碱基配对数来说，假结形式的配对数在总体数量上是相当少的，如在e c o l is s ur r n a 的一个权威二级结构模型中，4 4 7 个w a t s o n c r i c k 配对和g富硕士学位论文第二章r n a 二级结构及其数学模型一u 配对中只有8 个是以非嵌套模式配对的假结1 0 】。虽然假结在r n a 二级结构中出现的频率很小，但它却在r n a 的结构构成以及r n a 的功能活性中起着非常重要的作用，很多重要的r n a 中都存在假结。因此为了提高预测的准确性和向三级结构进军。r n a 二级结构预测算法必须能够预测假结。心、l 瀚黔cg c u 瀚：、g、i 、。、gi 、u a、j 、- i 、善图2 - 3 ( a ) 一个假结结构及其表示形式图2 - 3 ( b ) 假结结构序列拉直之后的形式图2 - 3 ( b ) 是一个假结结构在序列拉直后的形式，对于任何一个r n a 序列，碱基区( b a s er e g i o n ) 是指该序列的一段子序列。碱基配对区域( b a s e p a i r e dr e g i o n ) 指两个碱基区通过配对在空间上形成一段双螺旋结构。在这种情况下，我们称每个碱基区是有助于形成螺旋结构的。定义5 i ：对于一段r n a 序列s 和它的予序列t ，一个潜在假结区( p o t e n t i a lr e g i o n ) 是指t 中存在一个满足下列条件的碱基区：( 1 ) 它有助于在s 中形成螺旋结构；( 2 ) 但它不得有助于在t 中形成任何螺旋结构。定义5 2 ：如果t 中包含一个潜在假结区，我们就称t 是一个p 结构；并且，如果t 中包含的这个潜在假结区在两个碱基配对区域之间，我i l n 称t 是一个非平凡的p 结构，如图1 中t ，它包含的c 在两个碱基配对区域( b 和b ) 间。定义5 3 ：我们称r n a 序列s 构成假结结构当且仅当它含有两个非交迭的p结构( t l 和t 2 ) ，并满足( 1 ) t l 或t 2 是一个非平凡的p 结构；( 2 ) t l 和2 各自包含的潜在假结区形成螺旋结构( 称为交叉螺旋结构) 。定义5 3 精确定义了所有的r n a 假结结构。硕士学位论文第三章生物序列信息的语法学3 1 引言第三章生物序列信息的语法学从2 0 世纪9 0 年代初以来，对生物序列信息量及内涵的分析受到语言学的强烈影响1 1 1 1 4 。所谓生物序列是指：d n a ，r n a 和蛋白质序列。实际上，它们都可看成是一种语言遗传语言：蛋白质是用2 0 个字母书写的一种语言( 2 0种氨基酸) ，核酸则是用四种字母书写的( a ，c ，g ，和t 或u 四种碱基) 。遗传语言，同其他语言样，需要有一定的语法规则刁能具有一定的意义。而当前生物学研究的主要任务就是要弄清遗传物质的组织结构和功能。3 2 形式文法与随机文法自然语言是在人们认识世界和改造世界的过程中发展起来的。计算机理论的研究促进了语言学的发展。1 9 5 6 年，著名的语言学家n o a mc h o m s k y 首先对形式语言( f o r m a ll a n g u a g e ) 进彳t 了描述。关于语法学是一门理论十分完善的学科。这里只是介绍一些本文相关的知识。3 2 1 形式文法的定义“语言”是表示某个确定的字母表上的符号串的集合。对于字符集a 来说，a上所有长度有限的字符串构成的集合表示为a + 。巾表示空串。一种语言就是a +的子集。而语法，形象地说，则是生成一种语言的规则。对这种规则( 又称产生式) 的理解就是语义分析。c h o m s k y 定义了四类文法和相应的语言类，他把文法分成四种类型：既0 型，1 型，2 型，3 型。0 型的描述能力强于1 型，1 型强于2 型，2 型强于3 型。可以生成并且只能生成所有句法正确的串，其所遵循的规则集合称为形式文法。一个形式文法g 包含：一个字符集a ，称为终结符；变量的字符集v ，其中的变量称为非终结符；产生式规则p 组成的集合r ；在非终结符中有一个特殊的变量s 表示开始符。每个产生式规则包含一对位，) ，记为口j ，其中口和是( a u v ) + 中的元素。设定1 2 至少包含一个非终结符，给定g 和( a u v ) 上的两个串y 和d ，如果存在串的有限序列万= 口1 ，一，口。，使得硕士学位论文第三章生物序列信息的语法学y 专t 2 i 斗斗口。一万( 也写做y 寸。占) ，其中每一步都对应r 中的产生式规则的一次应用，那么就称占可由y 导出。对于r n a 二级结构模型，终结符指 a ，u ，g ，c 组成的字符集合。产生式规则p =s a s u u s a lc s g g s c iu s g ig s u( 配对生成规则)s a s ic s | g s lu s( 在左边生成不配对碱基)s s a is c is g is u( 在右边生成不配对碱基)s s s( 递归的回文：茎的侧面凸起了另一个茎)s - - ( 结束)该产生式规则可以缩写成如下形式：s a s a la s fs a ls s i ( 其中a 与a 代表相互配对的任何碱基)由文法g 生成的语言l = l ( 是可以从开始状态s 导出的全部终结符串的集合。正则文法是上下文无关文法的特例。上下文无关的意思是说使用表达式替换变量时，并不依赖于被替换的变量的上下文。准确地说，如果文法中所有产生式规则都是寸的形式( 要求左边只能是一个非终结符，而右边可以是除空字符外的任何字符或字符串) ，则文法g 是上下文无关的。如果一个语言可以由上下文无关文法来生成，则称其为上下文无关语言。上下文无关文法可以用规范的形式表述，称为范式( n o r m a lf o r m ) 。如果一种上下文无关文法的每个产生式规则都是以下三种形式之一：( 1 ) s 一垂，( 2 ) “一w ，其中“、v 、w 是非终结符，( 3 ) “一只则称其符合乔姆斯基范式【1 5 】。另外，如果s 一西在震中，则( 2 )中的v 和w 必须不同于s 。回文文法就是上下文无关的，上下文无关文法常常用于定义计算机语言的句法以及构造编译器。3 2 2 二义性和语法分析文法的一个导出过程可以被排列成一个树形结构，称为解析树( p a r s et r e e ) ，它反映了序列的句法结构。解析可以自上而下进行，也可以自下而上进行。如果序列拥有不止一棵解析它的解析树，则称它是二义性的，因此对一条序列的解析等价于找出从开始符到终结符之间正确的推导路径。二义性的概念对于编译器的设计很重要。二义性使得语法分析复杂化，这表现在两方面，一方面使分析算法复杂化，另一方面可能使分析树的数量随着被分析的字符串的长度呈指数增长。如果所有产生式规则的右边至多包含一个非终结符，那么就称该文法是线性的。对于线性的上下文无关文法存在快速的分析算法。本文中对r n a 建模的上下文无关文法采用c y k 算法求其最优解析树。一般来说，在乔姆斯基层次中，较高层语言的识别与序列文法分析需要更大的计算量。硕士学位论文第三章生物序列信息的语法学3 23 相关性和自动机其实还可以从生成模式和自动机这两个角度来考察文法。正则文法可以有整体的模式，例如形成c u c u c u c u 这样的交替字符串。正则文法不能处理字符串中的长程相关性。上下文无关文法可以对一定的长程相关性建模，例如嵌套相关性( n e s t e dd e p e n d e n c y ) 。如果所表示相关性没有相互交叉，那么它就是嵌套的。嵌套相关性是上下文无关语言的特征，例如回文，其中第一个字符必须和最后一个字符匹配，第二个必须和倒数第二个匹配，等等。如果相关性有交叉，例如复制语言，那么就需要用到上下文相关语言，因为在上下文相关语言的推导中必须自由移动非终结符，只有这样才能实现有交叉的相关关系。正则文法对应于有限状态自动机( f i n i t es t a t ea u t o m a t a ，f s a ) ，通常每个状态对应文法中的一个非终结符，像h m m 一样。在这种自动机中，除了状态自身外没有任何储存机制所有的信息都必须“硬编码”。上下文无关文法对应于下推自动机，它和有限有限状态自动机的区别在于它有一个存储栈。在每个时刻，只有栈顶是可以访问的。下推自动机可以通过每次对一个字符进行进栈或出栈操作实现回文，显然它不能处理交叉相关性，因为它在任何时刻只能访问栈顶。下面是文法与产生式规则，自动机对应关系的一览表。表3 - 1 文法、产生式规则及其等价关系一览表1 63 2 4 用c f g 对r n a 茎环结构进行建模的过程r n a 的茎环结构是r n a 序列结构中最常见的一种简单结构，由于它的序列完全遵循嵌套配对原则，所以很容易用上下文无关文法对它进行描述。在图3 - 1 ( a )中，序列1 和序列2 是两条不同的序列，但它们能折叠成相同的r n a 二级结构，因为它们拥有相同的碱基配对模式( a u 和6 - c ) 。而序列3 ，尽管它的前半段序列和序列2 的相同，后半段序列和序列1 的相同，但却根本不能折叠成和序列1硕士学位论文第三章生物序列信息的语法学或序列2 相似的结构，r n a 二级结构这种保守的碱基嵌套而互相关联的特性，类似于回文，只是从两端开始配对的字符并不相同，而是互补的。aac aca 广gagagai 阡二= 二习lg cu au cc aggaa acuga uc gc ug cugca aagcc gg cg egcu gca acu g序列l序列2序列3卜一_ 一：；!图3 - 1 ( a ) 三个r i q a 的茎环结构模型比较一- 一对序列1 和序列2 建模的上下文无关文法可以写成下面的形式：s a w u f c w 曙fg w t c f t t w l a ，w l a w 2 u lc w 2 9 ig w 2 c l u w 2 a ，w 2 一a w 3 u lc w 3 9 ig w 3 c l u w 3 a ，w 3 一g a a a ig c a a 图3 - 1 ( b ) 产生式规则s图3 1 ( c ) 产生式规则的解析树s 弋八3c gg ca ug cg cu agagaa aca图3 - 1 ( d ) 二级结构按照产生式规则，可以用解析树来直观的展示上下文无关文法对序列的解析过程，一棵解析树的根结点是开始符s ，叶子结点代表序列的终结符，内部结点是非终结符，一个父结点的所有子结点是该父结点对应的产生式右边所有符号的从左至右排列。一棵子树是解析树中一个以内部结点为根结点的集合，任何一棵子树都对应于序列中一段连续的子序列片断，这个性质很重要，我们可以设计一个算法为一条很短的序列构建解析树，然后递归的调用这个算法为越来越长的序列构建越来越大的解析树。从而使r n a 的整个序列得到解析。用来解析上下文无关文法的自动机称为下推自动机，与有限状态自动机不同，下推自动机需要占用一定的内存来保存它的存储栈。下推自动机从左至右解析一个序列根据如下的算法，初始时向自动机的堆栈推入一个开始的非终结符，然后将栈中的非终结符弹出，寻找该非终结符的解析式将其解析，再将解析后的解析式推入栈中，重复这一过程直到没有输入符存在，如果此时栈中为空则此输入序列被成功解析。硕士学位论文第三章生物序列信息的语法学对于上面的a p p l em o s a i cv i r u s ( a p m v - 3 ) r n a 茎环结构序列g c cg c aa g gc 用下推自动机解析的过程如下，捡虫推毯自动扭的攮在| q弹出，s 9 1 c ；_ c c g c a a g g css图c c g c a a g g c9 1 c弹出g ，接受g ；输入符右移。g 艮g c a a g g cl c弹山1 ，1 一e 2 9 ；g e # g c a a g g cc 2 9 c弹出c ，接受c ；输入符右移。g c 捌g c a a g g c2 9 c弹出2 ，2 一c 3 9 ：g c 幽c a a g g cc 3 9 9 c弹出c ，接受c ；输入符右移。g c c 囤i c a a g g c3 9 9 c弹出3 ，3 一g c a ag c c 图c a a g g cg c a a g g c弹出g ，接受g ；输入符右移。!( 接受若干个输入符)g c c g c a a g g 到c弹出c ，接受c ；输入符右移。g c c g c a a g g c j一栈为空，输入串为空，接受字符串。图3 _ 2 下推自动机解析r n a 序列的过程3 2 5 随机文法的定义随机文法是通过在每个产生式规则上添加概率结构得到的。它可以作为一种概率模型对序列进行建模。设一个随机文法模型0 产生不同序列x 的概率为p ( x 1 0 ) ，在随机正则文法或随机上下文无关文法中，由同一非终结符推导出的所有产生式的概率之和为1 ，即，p ( x 1 0 ) = l 。一个解析树( 推导过程) 的概率等于它每一步推导所使用的产生式的概率的乘积，b o p ( x i 目) = 丌p ( s ；x ) 。t f3 2 6 随机文法和h m m 的关系隐马尔可夫模型( h i d d e nm a r k o vm o d e l s ，h m m ) 可以看成是一个随机正则文法( s t o c h a s t i cr e g u l a rg r a m m a r ，s r g ) 的等价形式。只要把h m m 中由生成字符x 的从状态s 到s 的转换用s r g 中的概率，e ，的产生式规则s 斗施，替换就可以了。如图3 3 中，产生式x a y 的概率等于x 到y 的转移概率l x y = o 3和y 中a 的生成概率e y 口= o 9 的乘积。由此可见，随机文法是使生成过程基于状态转移而不是基于状态本身，这是随机文法与h m m 在形式上的区别。隐马尔可夫模型有两个缺点，首先，隐马尔可夫模型假设状态序列是一个马尔可夫链，无法使用序列的上下文信息；其次，隐马尔可夫模型中使用联合概硕士学位论文第三章生物序列信息的语法学率代替条件概率，显然，这些缺点使h m m 不适合对具有长程相关性的r n a 序列进行建模。而随机上下文无关文法( s t o c h a s t i cc o n t e x t f r e eg r a m m a r ，s c f g )构成了更一般的一类模型，它可以用于对r n a 序列的结构建模。q ：!-la0 2a0 9jlb0 8q ：三b0 10 7图3 - 3h m m 示意图3 3 并行通信文法模型对假结建模常见的r n a 茎环结构能被视为嵌套的碱基配对形式而使用上下文无关文法对其进行建模，但r n a 中还存在少量假结结构，它是以交叉的方式来进行碱基配对的，假结可以看成是交叉的而非嵌套的回文，假结的基本结构能用下面的语言来抽象的表示：l = l i lh a st h ef o r m 【( 】1 ) )( 其中【， 和( ，) 代表配对的碱基) 。这种语言可以用形式语言中的泵引理( p u m p i n gl e m m a ) 来证明它不是上下文无关的u ”】，实际上它是一种上下文相关文法描述的语言，等价于生物学复制语言，只要把定义式中的右括号全改为左括号就成了一般的复制语言。上下文相关文法是一种更加复杂的文法，一般认为对它的解析是一个n p 难问题，因此需要利用其他的文法模型来描述假结，如本节介绍的并行通信文法，这种文法的基本思想也是基于上下文无关文法的，它的计算复杂度和s c f g 相同。3 3 1 并行通信文法模型乔姆斯基的层次理论在自然语言和计算机语言的研究中都是非常重要的，但它并不是在形式语言的复杂性研究中唯一可用的理论。在动力系统的语言复杂性研究中，还需要另一类很不一样的语言理论，即并行重写系统，它是由生物学家林登梅耶( a l i n d e n m a y e r ) 建立的形式语言系统。回顾上一节中的生成语法g = ( 巧以，p , s o ) ，为了得到l ( g ) 中的字，要从开始符岛出发，不断使用p 中的语法规则进行重写( 即推导) ，直到符号串中不再含有v 中的变量为止。重写特征是每次使用一条规则，即一步派生。这样的重写过程称为串行重写。而并行重写系统的主要特征在于，在推导一个符合串时，同硕士学位论文第三章生物序列信息的语法学时使用多条规则进行重写，即多步派生。由于有多个产生式并行地进行重写，因此并行重写过程必须有通信协议使各产生式之间存在同步机制。实际上，并行重写系统包含许多子系统，分别生成各类形式语言。把这些形式语言遵循的规则集合称为并行通信文法( p a r a l l e lc o m m u n i c a t i n gg r a m m a rs y s t e m ，p c g s ) ”。本文中一个并行通信文法系统包含多个上下文无关文法( g o ，g l ，g k ) ，这些上下文无关文法被称为组件( c o m p o n e n t ) ，并规定g o 为主文法组件。这些文法能共享一套字符集a 和一套非终结符，另外，为了让各文法之问进行通信，还存在一些特殊的非终结符，称为询问符( q u e r ys y m b 0 1 ) 。像操作系统中的进程一样，通过主文法g 。的调度，组件之间就根据通信协议中的并行和同步机制进行重写，一个组件能询问其他组件产生的序列，而且几个组件