（系统工程专业论文）基于有限状态机的分子生物学系统建模研究.pdf

原创性声明 l l i lleii lrle i ii i it i u l y 17 9 0 5 5 6 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：勤蒸 日期：塑! 里：兰! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：必垄导师签名： 山东大学硕士学位论文 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 研究背景和意义1 1 2 分子生物学概论3 1 3 本文主要内容安排5 第二章氨基酸极性的f s m 模型分析7 2 1 有限状态机7 2 2 预备知识9 2 3 氨基酸极性判断的f s m 模型1o 2 4 本章小结15 第三章基因突变的f s m 算法分析1 7 3 1 引。言17 3 2 预备知识1 7 3 3 基于有限状态机的基因突变类型的算法分析1 9 3 4 本章小结2 9 第四章蛋白质超二级结构的f s m 分析3 l 4 1 引言3l 4 2 预备知识3 2 4 3 基于f s m 的蛋白质超二级结构的分析算法3 3 4 4 本章小结4 1 第五章总结与展望4 3 参考文献4 5 致谢 山东大学硕士学位论文 山东大学硕士学位论文 c o n t e n t s a b s t r a c t ( c h i n e s e ) i a b s t r a c t ( e n g l i s h ) 1 i c h a p t e r1 i n t r o d u c t i o n 1 1 1r e s e a r c hb a c k g r o u n d 1 1 2i n t r o d u c t i o no f m o l e c u l a r b i o l o g y 3 1 3m a i nr e s u l t s 5 c h a p t e r 2t h em o d e lo ft h ea m i n oa c i dp o l a r i t yb a s e do nf s m 7 2 1f i n i t es t a t em a c h i n e 7 2 2 p r e l i m i n a r yk n o w l e d g e 9 2 3 t h em o d e lo f t h ea m i n oa c i dp o l a r i t y 10 2 4 c o n c l u s i o n s l5 c h a p t e r 3 a n a l y s i so fg e n e t i cm u t a t i o n sb a s e do nf s m 1 7 3 1 i n t r o d u c t i o n 1 7 3 2 p r e l i m i n a r yk n o w l e d g e 17 3 3t h ea l g o r i t h ma n a l y s i so f g e n e t i cm u t a t i o n s 1 9 3 4c o n c l u s i o n s ：1 9 c h a p t e r4a l g o r i t h ma n a l y s i so ft h ep r o t e i ns u p e r s e c o n d a r ys t r u c t u r eb a s e d o nf s m 3 l 4 1 p r e f a c e 31 4 2 p r e p a r ek n o w l e d g e 3 2 4 3 a n a l y s i so f t h ep r o t e i ns u p e r s e c o n d a r ys t r u c t u r e 3 3 4 4 c o n c l u s i o n s 4 1 c h a p t e r5 c o n c l u s i o na n de x p e c t a t i o n 4 3 r e f e r e n c e s 4 5 山东大学硕士学位论文 a c k n o w l e d g e m e n t 4 9 山东大学硕士学位论文 摘要 分子生物学中心法则是继d n a 双螺旋结构发现之后生物学领域中的又一 重要成就，它揭示了编码基因信息的传递方向和途径。分子生物学是从分子水 平上研究生物的结构和功能的科学，自2 0 世纪5 0 年代开始，分子生物学已经 成为生物学的热点研究领域，其中d n a 携带的编码基因序列的研究是分子生物 学的重要研究领域。然而，现有研究成果大多还集中在实验室中的生化实验水 平，随着计算机和信息技术的发展，先进的计算控制方法被应用到这一研究领 域，但目前仍面临理论模型缺乏和d n a 计算高出错率的问题。 蛋白质是生命活动的物质基础，蛋白质的功能与其结构紧紧相关，因此知 道一个蛋白质的结构对了解其生物功能是非常关键的。目前，生化实验的方法 仍然是获得的蛋白质结构序列的主要手段，然而这种速度远远落后于蛋白质序 列的测序速度，因此理论预测蛋白质结构势在必行。 本文对蛋白质合成过程中的氨基酸极性模型进行了研究，将该离散事件动 态系统的建模分析方法用于氨基酸极性分类的数学建模与分析上，给出了 氨基酸类型的判定条件并给出了实际算例与分析；然后论文给出了基于有限状 态机的基因突变分类的模型分析算法，按照基因结构改变的类型可将基因突变 分为碱基的置换突变、移码突变、缺失突变和插入突变4 种。本文给出了两种 情况下，即两条等长d n a 链和两条不等长d n a 链的算例和分析，在判定基因 突变类型的同时还可以得到该链的基因突变率；最后论文的第四章首次给出了 基于有限状态机的蛋白质超二级结构分类的模型分析算法。蛋白质的超二级结 构是介于二级结构和结构域之间的结构，其可以分为四类：全口类蛋白质、全口 类蛋白质、口类蛋白质和口+ 类蛋白质。本文分别讨论了四种结构的模型 算法，在判定蛋白质超二级结构分类的同时还得到了该蛋白质的口螺旋以及 折叠的含量的计算公式。 最后章是本论文的研究工作总结，说明了研究中存在的问题，对下一步 的研究目标进行了展望。 关键词：蛋白质结构分析；有限状态机；氨基酸极性；基因突变 山东大学硕士学位论文 山东大学硕士学位论文 a b s t r a c t t h ec e n t r a ld o g m ao fm o l e c u l a rb i o l o g yi sa ni m p o r t a n ta c h i e v e m e n ti n b i o l o g ya f t e rt h ef i n d i n go ft h ed o u b l eh e l i xs t r u c t u r eo fd n a i ti l l u m i n a t e st h e t r a n s i t i o nd i r e c t i o no ft h eg e n e t i ci n f o r m a t i o n t h em o l e c u l a rb i o l o g yi sas c i e n t i f i c w h i c hr e s e a r c h e st h es t r u c t u r ea n df u n c t i o no ft h eb i o l o g i c a li nm o l e c u l a rl e v e l a f t e r19 5 0 s ，t h em o l e c u l a rb i o l o g yh a sb e c o m et h e h o tr e s e a r c hf i e l d ；e s p e c i a l l yt h e s t u d yo fd n a i sa ni m p o r t a n tf i e l di nm o l e c u l a rb i o l o g y h o w e v e r , m o s to ft h e e x i s t i n gr e s u l t sa r eg e tb yb i o c h e m i s t r yl a b o r a t o r y a l o n gw i t ht h ed e v e l o p m e n to f c o m p u t e ra n di n f o r m a t i o nt e c h n o l o g y ，s o m ea d v a n c e dc o n t r o lm e t h o dh a sb e e nu s e d i n t h i sf i l e d b u t ，i th a sn om a t u r et h e o r e t i c a lm o d e s l ，a n dt h ee r r o ro ft h ed n a c o m p u t a t i o n i sh i g h t h ep r o t e i ni st h em a t e r i a lb a s i so fl i f ea c t i v i t i e s t h ef u n c t i o no fp r o t e i ni s c l o s e l yr e l a t e dt oi t ss t r u c t u r e ，s oi fw ek n o w t h es t r u c t u r eo fap r o t e i nw ec a nr e a l i z e i t sf u n c t i o n r e c e n t l y ，t h ee x p e r i m e n t a lm e t h o di sa l s ot h em a i nm e t h o dt og e tt h e p r o t e i ns t r u c t u r e b u tt h i sm e t h o di ss l o w l y s o ，g e t t i n gt h ep r o t e i ns t r u c t u r eb y t h e o r yi sab e t t e rc h o i c e i nc h a p t e r2 ，t h em o d e lo ft h ep o l a r i t yo fa m i n oa c i db a s e do nf s mi sg i v e n f s mi sam e t h o dw h i c hi s p o w e r f u l i nd i s c r e t ee v e n td y n a m i cs y s t e m s t h e e x a m p l e si l l u s t r a t et h em a i nr e s u l t sa tt h ee n do f t h i sc h a p t e r a na l g o r i t h mo fg e n e m u t a t i o n sb a s e do nf s mi sg i v e ni nc h a p t e r3 a c c o r d i n gt ot h ec h a n g eo ft h e g e n e t i cs t r u c t u r e , t h eg e n em u t a t i o n c a l lb ed i v i d e di n t os u b s t i t u t i o n s ，r e m o v e m u t a t i o n s ，m i s s i n gm u t a t i o n sa n di n s e r t i o n a lm u t a t i o n s t h ee x a m p l ea n da n a l y s i si n t w oe q u a ll e n g t hd n aa n dt w od i f f e r e n tl e n g t hd n aa r eg i v e n a st h es a m et i m e ， w ec a nc a l c u l a t et h er a t eo ft h eg e n em u t a t i o n i nc h a p t e r4 ，t h ef s mm o d e lo ft h e s u p e r - s e c o n d a r yp r o t e i ns t r u c t u r ei sg i v e n t h es u p e r - s e c o n d a r yp r o t e i ns t r u c t u r e i sa s t r u c t u r ew h i c hi sb e t w e e nt h es e c o n d a r ya n ds t r u c t u r ed o m a i n t h ep r o t e i nc a nb e d i v i d e di n t oa l ia p r o t e i n ，a l l8p r o t e i n ，o c 8p r o t e i na n do c 七9p r o t e i n w e l 山东大学硕士学位论文 d i s c u s st h ea l g o r i t h mo ft h ef o u rs t r u c t u r e s ，a st h es a m et i m e , w ec a l lk n o wt h e c o n t e n to ft h eo ch e l i xa n dpf o l d f i n a l l y ，ac o n c l u s i o no ft h ed i s s e r t a t i o na n d s o m ef u t u r er e s e a r c ht o p i c si nt h ef i e l da r eg i v e ni nc h a p t e r5 k e yw o r d s ：p r o t e i ns t r u c t u r ea n a l y s i s ；f i n i t es t a t em a c h i n e ；p o l a r i t yo f a m i n oa c i d s ； g e n em u t a t i o n 山东大学硕士学位论文 1 1 研究背景和意义 第一章绪论 随着基因组测序计划的展开和分子结构测定技术的发展，分子生物学的研究重 点从数据的积累渐渐地转向数据的分析，在这种情况下，一门新的学科生物信 息学便应运而生。生物信息学【l 】是以计算机为工具对生物信息进行存储、检索和分 析的科学，它综合利用生物学、计算机科学和信息技术来揭示复杂的生物数据所包 含的生物学奥秘。目前，其研究重点是( 2 j 从核酸和蛋白质序列出发，分析序列中表 达的结构功能的生物信息。这些将有助于我们了解生命本质和进化过程，同时对新 药和新疗法的发现具有重要的意义。 蛋白质是一切生命的物质基础，生物体中的每个细胞和所有重要组成部分都有 蛋白质的参与，它是与生命及与各种形式的生命活动紧密联系在一起的物质。蛋白 质的生物作为在生命活动中起重要作用的生物大分子，它在生物体内的各种功能都 由它的空间结构决定。对于蛋白质空间结构的研究不仅有利于认识蛋白质的功能， 也有利于认识蛋白质的生物功能以及蛋白质与蛋白质之问的相互作用。 基因组测序计划产生了大量的蛋白质大分子氨基酸序列，给我们提供了丰富的 蛋白质一级结构资源。迄今为止【3 】，已经有超过6 , 0 0 0 ，0 0 0 条蛋白质序列被储存蛋 白质序列数据库当中，且其增长速度同益加快，如图1 1 所示。蛋白质的三维结构 主要依靠实验手段如x 射线晶体学方法或者核磁共振方法测定，目前存储在蛋白 质结构数据库p d b 中的数目超过了5 0 ，0 0 0 个，且其速度还呈现逐年增加的趋势， 如图1 2 所示，但蛋白质三维结构数量增长的速度还远不能与其序列数量的增长速 度相比，这主要因为基因组大规模测序比蛋白质三维结构的测定容易得多。x 射线 晶体学方法【4 】是至今为止确定蛋白质结构最有效的方法，但它的缺点是蛋白质的晶 体难以培养，晶体结构测定的周期较长。近年来发展的多维核磁共振方法可以直接 测定蛋白质在溶液中的构象，但由于对样品的需要量大、纯度要求高，通过实验方 法确定蛋白质结构在目前仍显得非常复杂，且代价高昂。因此，实验测定的蛋白质 结构比已知的蛋白质序列要少的多。而且随着基因自动测序方法的发展，蛋白质序 山东大学硕士学位论文 列与结构的数量差距将会越来越大。因此发展一种不需要复杂实验手段，简单、易 行的蛋白质结构确定方法就显得十分迫切。基于氨基酸序列的蛋白质结构预测方法 就是应这种需要发展起来的，表1 1 给出了几个常用的蛋白质序列和结构数据库的 网址。 5 e + 1 2 4 e + 1 2 3 e + 1 2 2 e + 1 2 1 e + 1 2 0 1 9 9 81 9 9 92 0 0 02 0 0 l2 0 0 22 0 0 32 0 0 42 0 0 52 0 0 62 0 0 72 0 0 82 0 0 9 图1 1 蛋白质序列数据库u n i p r o t k b 厂i r e m b l 中收录序列的增长趋势图 2 0 0 9 2 0 0 7 2 0 0 5 2 0 0 3 2 0 0 1 1 9 9 9 02 0 0 0 04 0 0 0 06 0 0 0 0 图1 2 蛋白质结构数据库( p d b ) 中收录结构的年度增k 图 山东大学硕士学位论文 表1 1 常川的蛋白质序列和结构数据库 名称 网址内容 p d b h t t p ：w w w r c s b o r g p d b 蛋白质二维 结构 p d b s u m h t t p ：w w w b i o c h e m u c l a c u k b s m p d b s u r r d p d b 数据库 综合信息 s c o p h t t p ：s c o p i r e - l m b c a m a c u k s c o p 蛋白质结构 分类 c a t h h t t p ：b i o c h e m u c l a c u k b s m c a t h 蛋白质结构 分类 d s s p h t t p ：s w i f t e m b l - h e i d e l b e r g d e d s s p 二二级结构门 属数据库 f s s p h t t p ：c r o m a e b i a c u k d a l i f s s p 蛋白质家族 数据库 h s s p h t t p ：w w w s a n d e r e m b l h e i d e l b e r g d e h s s p 同源蛋白质 数据库 s w l s s p r h t t p ：w w w e x p a s y c h s p o r t 蛋白质序列 o t 数据库 p i r h t t p ：w w w n b r f g e o r g e t o w n e d u p i r p i r _ p s i h t m l 蛋白质序列 数据库 e m b l h t t p ：w w w e b i a c u k e b i _ d o c s e m b l _ d b e b i t o p e m b l h t m l 核酸系列数 据库 o 、v l h t t p ：w w w b i o c h e m u c l a c u k b s m d b b r o w s e r o w l o w l h t m l 非冗余蛋白 质序列 s w i s s 3 d i h t t p ：w w w e x p a s y c h s w 3 d 二维结构图 m a g e示 1 2 分子生物学概论 1 核酸、蛋白质和遗传信息 脱氧核糖核苷斟6 d n a ( d e o x y r i b o n u c l 6 ca c i d ) 大分子是由四种核苷酸聚合 成的高度有序的一维分子链。遗传信息就编码在这些核苷酸的不同排列次序上。 d n a 分子由两条呈双螺旋结构的脱氧核糖核苷酸链盘绕而成，依靠嘌呤和嘧啶之 间的氢键连接在一起，a 和t 配对，c 和g 配对，这样配对的一对碱基称为一个 碱基对。d n a 在复制期间以解旋的单链为模板严格按照碱基互补配对原则，即a 和t 配对，g 和c 配对，合成两条新的d n a 序列，尽可能地减小了发生基因突变 的概率，基因突变往往造成生物体自身或后代性状的改变【7 】。 3 山东大学硕士学位论文 细胞中还有另一种核酸r n a 8 l ( r i b o n u c l e i ca c i d ) ，它也能够携带遗传信息，与 d n a 类似也具有配对能力，它的作用是：携带来自于d n a 的遗传信息到核糖体， 并最终转录到蛋白质中。 蛋白质是一种复杂的有机生物大分子，是构成生物体最直接的元素。它是生命 活动的直接参与者，生物体之间的差异也是直接友蛋白质的不同造成的【9 1 。 氨基酸是蛋白质的基本组成单位，生物体的所有蛋白质都是由2 0 种标准氨基 酸组成的【1 0 】。氨基酸通过相邻的氨基和羧基缩水形成多肽链，进一步再形成更复杂 的结构。表1 2 给出了氨基酸的标准符号。 表i - 2 氨基酸标准符号表 a m i n oa c i d三字母符号单字母符号 丙氨酸 a l aa 精氨酸a r gr 天冬酰胺 a s nn 天冬氨酸 a s pd 、l ，胱氨酸 c y sc 谷酰胺g l n q 谷氨酸 g l ue 甘氨酸 g l yg 组氨酸 h l sh 异亮氨酸 i l el 亮氨酸 l e u l 赖氨酸 l y sk 甲硫氨酸m e tm 苯丙氨酸 p h ef 脯氨酸 p r o p 丝氨酸 s e rs 苏氨酸 t h rt 色氨酸 t h pw 酪氨酸 t y ry 缬氮酸 v a l v 2 蛋白质的结构 蛋白质的结构【1 3 1 分为一级结构、二级结构、三级结构和四级结构；二级结构和 三级结构之间又有超二级结构和结构域。 蛋白质的一级结构：指的是蛋白质分子中，由肽链连接起来的各种氨基酸的排 列顺序。 4 山东大学硕士学位论文 蛋白质的二级结构：指多肽链中主链原子的局部空间排布，是不涉及侧链部分 的构象。蛋白质二级结构是完整肽链构象( 三级结构) 的结构单元，也是蛋白质复 杂空间构象的基础，因此白质二级结构的预测通常被认为是蛋白结构预测的第一步 【1 4 】。常见的规n - 级结构【1 5 1 有口一螺旋、一折叠及转角等。 超二级结构：是介于二级结构和结构域之间的结构。最简单的超二级结构是两 个规则的二级结构单元被连接多肽连接形成具有一定几何排列的局域空间结构。 结构域：是介于超二级结构和三级结构之间的结构，是蛋白质折叠中的一个结 构层次。 蛋白质的三级结构：具有二级结构的肽链按照一定的方式再进一步卷曲、盘绕、 折叠成一种看起来很不规则，而实际上有一定规律性的三维空间结构。 蛋白质的四级结构：具有三级结构的蛋白质分子通过一些非共价键结合起来形 成的具有生物功能的蛋白质大分子。 1 3 本文主要内容安排 全文共分五章，主要工作及章节安排如下： 第一章介绍课题的背景和研究意义，简单介绍了本文中所涉及到的分子生物学 的基本知识，并简要介绍了本文的主要研究工作。 第二章给出了基于有限状态机的氨基酸极性判断的模型分析算法。本章将该 离散事件动态系统的建模分析方法用于分子生物学系统建模上，对氨基酸极 性分类的进行了建模与分析，给出了氨基酸类型的判定的流程和实际算例与分 析。 第三章给出了基于有限状态机的基因突变分类的模型分析，基因突变是生物体 不可避免的一种现象，按照基因结构改变的类型可将基因突变突变可以分为碱基的 置换突变、移码突变、缺失突变和插入突变4 种。本文给出了两种情况下，即两条 等长d n a 链和两条不等长d n a 链时的算例和分析，在判定基因突变类型的同时 还可以得到该链的基因突变率。对于两条不等长链的d n a ，本文用有限状态机给 出了序列对齐的方法。 第四章给出了基于有限状态机的蛋白质超二级结构分类的分析算法，蛋白质的 5 山东大学硕士学位论文 超二级结构可以分为四类：全口类蛋白质、全类蛋白质、口i p 类蛋白质和口+ 类蛋白质。本文分别讨论了四种结构的模型算法，在判定蛋白质超二级结构分类 同时还可以得到该蛋白质的口螺旋以及p 折叠的含量。 第五章对本论文的研究工作进行总结，并对下一步的研究方向进行展望。 6 山东大学硕士学位论文 第二章氨基酸极性的f s m 模型分析 2 1 有限状态机 1 有限状态机的基本概念 有限状态机( f i n i t es t a t em a c h i n e ，简称f s m ) ，也称为有限自动机，是为 研究有限状态的计算过程和某些语言类而抽象出的一种计算模型。一个有限状 态机包括一下几个部分1 6 1 ：一个有限状态集，用于描述系统中的不同状态；一 个输入集，用于表示系统所接收的不同输入信息：一个状态转移规则集，用于 表述系统在接收不同输入下从一个状态转移到另一个状态的规则。有限状态机 可由如下形式定义给出。 定义：一个有限状念机m 可用一个五元组表示如下【1 7 】： m = ( q ，6 ，q o ，f ) 其中： ( 1 ) = o r 。，盯：，盯。) ：表示非空的有限输入符号集合。在任一确定的时 刻，有限状态机只能接收一个确定的输入o r ，。 ( 2 ) q = q o , q 。，9 2 ，q 。) ：表示非空的有限状态集合。在任一确定的时刻， 有限状态机只能处于一个确定的状态g ，。 ( 3 ) 万：q 奉专q 是一个状态转换函数。如果在某一确定的时刻，有限状 态机处于某一状态q ，q ，并接收一个输入字符仃，那么下一时刻将处于 一个确定的状态g ，= 8 ( q ；，仃，) q 。在这里规定q = 8 ( q ，s ) ，即：对任何状态g ， 当读入空字符占时，有限状态机不发生任何状态转移。 ( 4 ) q 。q 是初始状态，有限状态机由此开始接收输入。 ( 5 ) f q 是终结状态集合，有限状态机在达到终态后不再接收输入。 2 f s m 的状态转移函数的表现形式 对于一个有限状态机而言，最关键的部分是状态转移函数。由定义可知，转移 函数万是从q 幸到q 的映射。也即，它是一个二元函数，第一个变元取自q 的 7 山东大学硕士学位论文 一个状态，第二个变元取自中的一个符号，函数值是q 中的一个状态1 8 1 。 下面给出一个具体的有限状态机如：m = ( g 。，g 。，9 2 ，g ，) ， 0 ，1 ) ，万，q 。，国。) ) ， 其中状态转移函数万具体定义为： 8 ( q o ，1 ) = q l ，8 ( q o ，0 ) = q 2 ， 8 ( q 2 ，1 ) = q 3 ，8 ( q 2 ，1 ) = q o ， 在这个状念机中，q 中有4 个状态， 8 ( q i ，1 ) = q o ，万( g l ，0 ) = q 3 ， 8 ( q 3 ，1 ) = q 2 ，万( 9 3 ，o ) = q i 。 中有两个字符，所以要列出8 个式子 才能给出万的完整定义。为了方面、直观起见，状念转移函数通常都采用关系矩阵、 状态转移表或者状态转移图的形式来表裂1 9 】。 状态转移矩阵 对于有限状态机m = ( q ，万，q 。，f ) 的转移函数万，用行表示状态机所处的当 前状态，用列表示将要到达的下一个状态，行列交叉处表示输入字符，称该矩阵为 转移函数艿的关系矩阵，或称为有限状念机m 的状态转移矩阵【18 1 。下图这个矩阵 给出上述例子m 的状态转移矩阵： 图2 1 有限状态机m 的状态转移矩阵 状态转移表 对于有限状态机m = ( q ，万，q 。，f ) 的转移函数艿，用表格的行表示状态机所 处的当前状态，列表示当前的输入字符，行列交叉处表示要到达的下一个状态，称 该表格为有限状态机m 的状态转移表【2 们。如上述例子中m 的状态转移表如2 1 所 示： 、liilliiillll， o 1 o 1 1 o l o ，。l 吼 吼 以 山东大学硕士学位论文 表2 1 有限状态机m 的状态表 状态输入 0l 口o 9 2 g l g i9 3口o 9 2g o9 3 9 3 口l9 2 状态转移图 对于有限状态机m = ( q ，万，g 。，f ) 的转移函数万，用圆圈( 节点) 来表示状 态，将存在转移关系的状念用有向弧连结，并在有向弧上标注相应的输入字符；用 标有箭头的节点表示初始状态；属于终结状念集合的状态用双圈表示。由上述规则 所建立的有向图称为状态转移图【2 l 】。图4 2 表示的是有限状态机m 的状态转移图： 丌始一 一：1 ，迥 2 2 预备知识 1 - j 1 、r 。一一一一 ( q 2 ) 、， s 5 s 6 ，由有向弧t k l 和t k 2 来保证，当s 7 中的 元素和等于l 并且s 4 中的元素为空时，s 4 才会向s 5 通过t k i 发出一个允许信号， 此时，状态s 5 才被激活，同理，当s 7 中的元素和等于1 并且s 5 中的元素为空时， s 5 才会向s 6 通过t k 2 发出一个允许信号以来激活状态s 6 。状态s 7 是存放一个初 始状态为四个零的单元，也即 0 ，0 ，0 ，0 ) ，每一个位置分别对应于状态氨基酸四个极 性中的一个，其中四个位置分别代表( 非极性氨基酸，酸性氨基酸，碱性氨基酸， l o 困闽圈圈 山东大学硕士学位论文 中性氨基酸) ，当某个位置为1 时表示含有该极性的氨基酸，为0 表示不含有该极 性的氨基酸。当所有元素之和为1 的时候，也即判断出某种氨基酸的极性时有向弧 t i o 被激发，将结果输出到终态s 8 。 ，1 念亟 图2 - 4 氨基酸二兀码极性分类的f s m 状态转移图 有向弧t 7 、t 8 和t 9 所代表的状念转移函数是整个自动机的关键部分。根据 图3 3 所示的氨基酸的极性表我们可以这样定义它们。 对于t 7 ，当s 4 = a ，也即输入为碱基a 时，s 7 中的内容将会由初始状态 o ，0 ，0 ，0 ) 变为 1 ，1 ，1 ，1 ) ；同理，当输入碱基c 时，输出s 7 = 1 1 ，0 ，0 ，1 ) ；当输入为碱基 g 时，输出s 7 = 1 ，0 ，1 ，1 ) ；当输入为碱基c 时，输出s 7 = 1 ，0 ，0 ，0 ) ，注意到当输入 为碱基t 时，输出的s 7 的四个元素之和等于l ，因此此时不必再读取s 5 和s 6 中 的内容，就已经可以直接判断出该氨基酸为非极性氨基酸。 对于t 8 ，它把已经读取了s 4 中碱基后所输出的s 7 的状态作为初始状态，根 据再次输入的s 5 中的字母对s 7 的内容进行更改。具体定义如下，当初始 $ 7 - - - l ，1 ，1 ，1 ) ，若此时的s 5 的输入为字母a ，则s 7 被更改为 o ，0 ，1 ，1 ) ；当s 5 = c ) 时， 输出s 7 = o ，0 ，1 ，1 ) ；当s 5 = g ) 时，输出s 7 = 0 ，1 ，0 ，0 ) ；当s 5 = t ) 时，输出 s 7 = 1 ，0 ，0 ，1 ) 。当初始s 7 = 1 ，0 ，0 ，1 ) 时，若此时的s 5 输入为字母a ，则s 7 被更改为 o ，0 ，0 ，1 ) ；当s s = c ) 时，输出s 7 = l ，0 ，0 ，0 ) ；当s s = c ) 时，输出s t = 1 ，0 ，o , o ) ； 当s 5 = t ) 时，输出s 7 = o ，o , o ，1 ) 。当初始s 7 = 1 ，o , 1 ，1 ) 时，若此时的s 5 输入为字母 爿，则s 7 被更改为 o ，o , 1 ，1 ) ；当s 5 = c ) 时，输出s 7 = o ，0 ，1 ，o ) ；当s s = g ) 时，输 出s 7 = 1 ，0 ，0 ，o ) ；当s 5 = 丁) 时，输出s 7 = l ，0 ，0 ，1 ) 。 经过转移函数t 8 我们可以看出，会有一部分s 7 的元素和为l ，也就代表此时 氨基酸的极性已经被判断出来。但仍有一部分s 7 的元素和不为l ，此时就要读入 山东大学硕士学位论文 最后一个字母。状态转移函数t 9 的定义与t 8 类似，也是基于现有s s 6 中的输入来再次修改s 7 的内容。 当输入的不是一组三元码而是一串三元码时，有限状态机的模型 所示。新增状态s o 用来存储该三元码串，当新增状态s 9 中的内容为 t 1 2 被激活，将状态s o 的元素进行取前三位的操作并存储在状态s 1 中，剩余的碱 基通过t 0 b 再返回状态s 0 。同时在每判断完一组三元码后也即s 7 中的元素之和为 1 时，有向弧t 1 1 被激活，将状态s 9 的内容更改为1 ，激活有向弧t 1 2 ，同时启动 清零操作，将状态s 1 、s 2 、s 3 、s 4 、s 5 、s 6 和s 9 的内容置零。 图2 - 5 含有若干三元码的氨基酸极性分类的f s m 状态转移图 算例与分析 为了更清楚的说明以上两个f s m 的运转过程，下面将给出两个例子加以说明。 例1 给出三元码t g a ，那么根据上节中给出的f s m 的模型可以用如下的表 格来表示整个f s m 的运作。 1 2 表2 - 2 例i 的f s m 中的状态变化 步数非空状态集合元素 被激活的有向弧 l s 1 t g a ) t i ；t 2 2 s 2 丁) ；s 1 g a ) ；c o u n t e r l = l 1 3 3 s i g a ) ；s 3 丁) ；c o u n t e r l = c o u n t e r 2 = 1 t 1 ；t 2 ；t 5 4 s 5 t ) ；s 2 g ) ；si 彳) ；c o u n t e r l = 2 ；c o u n t e r 2 = 1 t 3 5 s l 即) ；s 3 g ) ；s 5 t ) ；c o u n t e r l = c o u n t e r 2 = 2 t 4 ：t l 6 s 2 a ) ；s 4 g ) ；s 5 t ) ；c o u n t e r l = c o u n t e r 2 = 2 t 3 ；t 7 7 s 3 a ) ；s 5 n ；s 7 = 1 ，1 ，0 ，1 ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t 7 b ；t 6 8 s 5f ) ；s 6 a ) ；s 7 = 1 ，1 ，0 ，1 ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t k i ；t 8 一 山东大学硕士学位论文 9 s 7 1 ，1 ，0 ，o ) ；s 6 a ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t 8 b 1 0 s 7 1 ，0 ，0 ，0 ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t k 2 ；t 9 1 l s 8 1 ，0 ，0 ，0 ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 通过上表我们可以看出整个f s m 在运行中所有状态中元素的变化已经被激活 的有向弧。最终在状态s 8 中得到结果 1 ，0 , 0 ，0 ) ，这个结果表明三元码t g a 所代表 的氨基酸是属于非极性氨基酸。 例2 给出一组三元码g t a g a t t c a ，那么根据上节中给出的f s m 的模型可以 用如下的表格来表示整个f s m 的运作。 表2 - 3 例2 的f s m 中的状态变化 步北空状态集合元素被激活的有 数 向弧 1 s o g t a g at t c a ) ；s 9 1 ) t 1 2 2 s o g t a g a t t c a ) t 0 a ；t 0 b 3 s o g a t t c a ) ；s 1 g t a ) t 1 ；t 2 4 s o g at t c a ) ；s1 t a ) ；s 2 g ) ；c o u n t e r l = l t 3 5 s o g a t t c a ；s i i r a ) ；s 3 g ) ；c o u n t e r i = c o u n t e r 2 = 1 t 1 ；t 5 ；t 2 6 s o g at t c a ) ；s1 a ) ；s 2 t ) ；s 5 g ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 1 t 3 ：t l 7 s o g a t t c a ) ；s 3 t ) ；s 2 a ) ；s 5 g ) ；c o u n t e r l = c o u n t e r 2 = 2 t 4 ：t 3 8 s o g at t c a ；s 4 n ；s 3 a ) ；s 5 g ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t 7 ；t 6 9 s o g ai t c a ) ；s 7 1 ，0 , 0 ，0 ) ；s 5 g ) ；s 6 a ) ；c o u n t e r l = 2 ；c o u n t e r 2 = 3 t 1 0 ；t 1 1 1 0 s o g a t r c a ；s 8 “1 ，0 ,