（运筹学与控制论专业论文）用dna分子自动机模拟有穷自动机.pdf

摘要 d n a 计算属于生物化学，数学以及计算机等学科的一个交叉领域，其研究 的内容涉及到数学，医学，计算机等各个领域。自从a d l v m a n 教授开创了这一 新的领域以来，d n a 计算的一些思想和方法被广泛的应用于解决一些图论，网 络，优化等问题。由于d n a 计算具有高度的并行性，因此，研究者也把目光 投向了用d n a 分子自动机来模拟电子计算机。 d n a 分子自动机模拟电子计算机是d n a 计算领域内一个重要的内容。研 究者已经提出了用d n a 分子自动机来模拟图灵机的一步转移规则，有穷自动 机的转移规则以及下推自动机的转移规则。d n a 分子自动机模拟电子计算机是 一个内容相当丰富的课题，目前所取得的成就与之相比还存在很大的差距。基 于这一现状，我们将继续探讨用分子自动机模拟电子计算机的思想，方法和意 义。 在d n a 分子自动机中，酶是分子自动机的硬件，输入分子和转移分子是 分子自动机的软件，同时还编码了检测分子。设计一个d n a 分子自动机的关 键在于选择合适的软件分子。我们对现有的用d n a 分子自动机模拟电子计算 机的思想和方法进行分析和研究，在此基础上提出了一些用d n a 分子自动机 模拟有穷自动机的新的方法。其中设计环形分子链来模拟有穷自动机的转移规 则是我们研究的核心部分。 虽然用d n a 分子自动机模拟有穷自动机在实验条件下的实现还受到一定 的限制，但这种思想将对d n a 计算领域的发展产生重大的影响。 关键词：d n a 计算；分子自动机；酶；模拟 a b s t r a c t d n ac o m p u t a t i o nf a l l si n t ot h ec r o s sf i e l do fb i o c h e m i s t r y , m a t h e m a t i c sa n dc o m p u t e r t h e c o n t e n ts t u d i e dr e l a e st ot h ef i e l d so fm a t h e m a t i c s m e d i c i n ea n dc o m p u t e r a f t e rp r o f e s s o r a d l e m a ni n i t i a t e dt h i sn e wf i e l d , t h ei d e aa n dm e t h o do fd n a c o m p u t a t i o nc a nb eu s e dw i d e l y t os o l v et h ep r o b l e m so fc h 吼n e t w o r ka n do p t l m i z a t i o n 。b e c a u s eo fi t sh i g 址yp a r a l l e l c o m p u t a t i o n , t h ei n v e s t i g a t o r s 啪d n am o l e c u l a ra u t o m a t o nt os i m u l a t et h ee l e c t r o n i c c o m p u t e r u s i n gd n a m o l e c u l a ra u t o m a t o nt os i m u l a t et h ee l e c t r o n i cc o m p u t e ri s8 ii m p o r t a n tc o n t e n t o fd n ac o m p u t a t i o n t h ei n v e s t i g a t o r sh a v eb r o u g h tf o r w a r dt ol 】3 cd n am o l e c u l a ra u t o m a t o n t os i m u h u eo n es t e po f t r a n s f e rm l e so f t u r i n gm a c h i n e t h et r a n s f e rr u l e so f m a c h i n e sw i t hf i n i t e s t a t e sa n dt h et r a n s f e rr u l e so fp u s h - d o w na u t o m a t o n u s i n gd n am o l e c u l a ra u t o m a t o nt o s i m u l a t et h ee l e c t r o n i cc o m p u t e ri sa ni m p o r t a n tt a s k c o m p a r ew i t hi t , t h ea c h i e v e m e n tw eh a v e g o t t e ni ss m a l l w ew i l lc o n t i n u et od i s c u s st h em e t h o do fu s i n gd n am o l e c u k 口a u t o m a t o nt o s i m u l a t et h ee l e a b r o i l i cc o m p u t e r a b o i l td n am o l e c u l a ra u t o m a t o n , e 1 1 巧m ei st h eh a r d w 口e ，i n p u tm o l e c u l e sa n d 椭m s f e r m o l e c u l e sa r es o r w a r e ，a n dw ea l s oc o d ed e t e c t i n gm o l e c u l e s t h ek e yo fd e s i g n i n gm o l e c u l a r a l l t o l 蝴i st oc h o o s ea p p r o p r i a t es o f t w a r em o o c h e s w eh a v es t u d i e dt h em e t h o d so fd n a m o l e c u l a ra u t o m a t o nu s e dt os i m u l a t et h ee l e c t r o n i cc o m p u t e r , a n dw ed e s i g n 翻d l n en e wm e t h o d s o f s i m u l a t i n g 锄i t o m 纰w i t hf i n i t es t a t e s d e s i g n i n gl o o ps t r a n d st os i m u l a t et h ea u t o m a t o l lw i t h f i n i t es t a t e si st h ek e yc o n t e n tw es t u d i e d a l t h o u g hu s i n gd n am o l e c u l a ra u t o m a t o nt os i m u l a t et l h ea u t o m a t o nw i t hf i n i t es t a t e sh a s s o m el i m i t si nt h el a b , t h i sm e t h o dw i l lb r i n ga ni m p o r t a n te f f e c ti nt h ef i e l do fd n a g o m p u t , 撕o i l k e yw o r d s ：d n ac o m p u t a t i o n ；m o l e c u l a ra u t o m a t o n ；e n z y m e ；s i m u l a t e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他入已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：互d ! 抱日期：砬 翌 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲碰导师签纰隰皿? 第1 章绪论 1 1 前言 第1 章绪论 1 9 8 7 年，h e a d 在剪接系统【2 】一文中就提出了用d n a 分子来执行操作的思 想。1 9 9 4 年，a d l e m a n 提出了如何用d n a 计算的方法来解决哈密顿路径的问 题 i i , 3 1 ，从而开创了d n a 计算这一新的研究领域。随后许多研究者就把目光投 向了d n a 计算这一新的领域。 分子计算用于解决传统计算机所能解决的普通算法问题及传统计算机所不 能解决的复杂性问题，而分子计算解决闯腿的方法完全不同于普通计算机解决 问题的方法。分子计算将成为计算科学中一种有效的新的方法。并且，分子计 算具有通用性。 1 2 d n a 的结构 d n a 是遗传的物质基础，基因是具有特定生物功能的d n a 序列。w a t s o n 和c r i c k 于1 9 5 3 年提出了著名的d n a 双螺旋模型，为合理的解释遗传物质的 各种功能，解释生物的遗传和交异，解释自然千变万化的生命现象莫定了理论 基础 4 1 。 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 n a 分子中， 磷酸和脱氧核糖是永远不变的，而含氮碱基是可变的，主要有四种，即腺嘌呤 ( a ) 和鸟嘌岭( g ) ，胞嘧啶( c ) 和胸腺嘧啶( t ) 。因此脱氧核营酸可分 别称为腺嘌呤脱氧核苷酸，鸟嘌呤脱氧核苷酸，胞嘧啶脱氧核苷酸和胸腺嘧啶 脱氧核苷酸。许许多个脱氧核苷酸经3 一5 磷酸二酯键聚合而成为d n a 链。 d n a 通常以线性或环状形式存在，绝大数d n a 分子都由两条碱基互补的单链 构成1 4 j 。 d n a 不仅具有严格的化学组成，还具有特殊的空间结构，它主要以有规则 的双螺旋形式存在，其基本特点是： ( 1 ) d n a 分子是由两条互相平行的脱氧核苷酸长链盘旋而成的； ( 2 ) d n a 分子中的脱氧核糖和磷酸交替连接，排列在外侧，构成基本骨 架，碱基排列在内侧； 北京工业大学理学硕士学位论文 ( 3 ) 两条链上的碱基通过氢键相结合，形成碱基对。 碱基对的组成有一定的规律，这就是嘌呤与嘧啶配对，而且腺嘌呤一定 与胸腺嘧啶( t ) 配对，鸟嘌呤( g ) 一定与胞嘧啶( c ) 配对( 汀= 丁，虿= c ) ) 。也就是 说，一条链上某一个碱基是a ，则另一条链上与它配对的碱基必定是t ；一条 链上某一个碱基c ，则另一条链上与它配对的碱基必定是g 。反过来，与t 配对 的必定是a ，与g 配对的必定是c ，碱基之间的这种一一对应的关系叫碱基互 补配对原则。从d n a 的分子结构可以看出，碱基在长链之间的排列顺序是千 变万化的。组成d n a 的碱基虽然只有四种，而且这四种碱基的配对方式只有 两种，但由于碱基可以任意顺序排列，构成了d n a 分子的多样性。例如，某 d n a 分子的一条多核苷酸链有1 0 0 个不同的碱基组成，它的可能排列方式就是 4 ”。实际上，每条多核苷酸链中的碱基总数远远超过1 0 0 个，所以，它们的 排列方式几乎是无限的1 4 。 1 3 d n a 计算 1 3 1d n a 计算的特点 d n a 计算具有以下优点： ( 1 ) d n a 计算具有大规模的并行性。d n a 分子每秒的计算速度比当前的 最快的计算机的计算速度还要快的多。 ( 2 ) d n a 分子具有紧密性，因此在d n a 链上能编码大量的信息。a d l e m a n 给出了一个合理的分析：在一个合理的实验时间内，d n a 分子能执行 1 0 ”个操作，这远远超过了当前计算机的计算能力f 1 1 ，因此d n a 计算 就有可能解决更复杂的重要问题。 ( 3 ) 在d n a 计算过程中用到了酶的作用( 酶可以为计算提供能量) 这就 降低了m 怆计算所需要的能量。 但d n a 分子计算存在的问题如下： ( 1 ) 分子之间的反应都有一些固定的法则，这些是实验人员无法控制的。 ( 2 ) 分子计算提供正确答案的可信度的大小。 ( 3 ) 分子在反应过程中利用率的高低。 ( 4 ) 分子计算方法的可交性和通用性如何? 2 1 3 2 目前d n a 计算的发展状况 1 2 年以来，d n a 计算这一新的研究领域得到了蓬勃的发展，研究者们在 这一领域取得如下成果： ( 1 ) 1 9 9 4 年，a d l e m a n 用d n a 计算的方法成功的解决了含有6 个顶点的 哈密顿有向路径问题【l 】oa d l e m a n 用d n a 单链分子对哈密顿有向路径 问题中的顶点和边进行了编码，采用了一定的生物操作技术和独特编 码方式，让这些单链分子进行任意的互补杂交反应，从而根据一定的 约束条件，提取满足条件的d n a 分子链，找到哈密顿有向路径问题 的解。这种方法用到的生物操作步骤为d ( 帕。用到的d n a 链为疗! 。 ( 2 ) 1 9 9 5 年，l i p t o n 提出了用d n a 计算在d ( 功次实验操作步骤内解决 3 - s a t 问题 5 1 ，吼 7 1 。在这种方法中所使用的分子链的条数为2 “。 ( 3 ) 1 9 9 5 1 9 9 6 年，a d l e m a n 提出了用分子算法解决3 一可着色问题，该问 题的空间复杂度为d ( 3 ”) 。1 9 9 6 年，b a c h 提出了用d n a 计算解决独 立集问题，该问题的复杂度低于0 ( 2 ”) 。 ( 4 ) 1 9 9 5 年，l i p t o n 提出了用d n a 计算破译d e s 的方法阮【1 4 1 ( 5 ) 1 9 9 7 年，o u y a n g 用分子实验成功的解决了含有6 个顶点和1 1 条边的 最大团问题【1 5 1 。 1 3 3 常用的生物操作技术 ( 1 ) 提取：利用给定的分子链提取所需要的d n a 分子链。 ( 2 ) 凝胶电泳技术：分离( s e p a r a t i n g ) ：将d n a 分子置于一有凝胶的电场 中，由于d n a 分子带负电，在电场中会向正极移动，长度大的分子 链受到凝胶的阻力大，移动速度慢，因此可用此技术去获取一定长度 的d n a 分子链，也可分离，提取不同长度的d n a 分子链。 ( 3 ) p c r 技术：将d n a 分子链成千上万倍的放大，并能特异的扩增任何 所希望的e l n a 片段。 ( 4 ) 荧光标记技术：对d n a 分子链进行荧光标记，以便提取所需的d n a 分子链。 ( 5 ) 合并：将含有分子链溶液的两个或多个试管合并成一个试管，而不改 变原有d n a 分子链的特性。 北京工业大学理学硕士学位论文 ( 6 ) 粘接：将互补的d n a 单链分子或带有互补粘头的d n a 双链分子混 合，使其发生互补反应，形成双链分子的过程。 ( 7 ) 剪切：利用限制性酶对含有识别位点的d n a 分子链进行剪切的过程。 1 4d n a 计算的应用 ( 1 ) n p 问题。目前，还有许多的n p 问题是普通计算机无法解决的。a d l e m a n 用d n a 计算的方法解决了哈密顿有向路径问题，这为研究者们提供了 一种设想：能否用d n a 计算来解决普通计算机所无法解决的复杂性问 题，如n p 问题【5 】，1 6 1 。目前，许多研究者正努力寻找合适的d n a 分子算 法来解决复杂性问题，并取得了可喜的成果。 ( 2 ) 密码的设计和密码的破译。研究者们早就建立了p l a y f a i r 密码体制的 d n a 加密和解密方法。a d l e m a n 和l i p t o n 又先后提出了用d n a 计算 的方法来破译美国的数据加密系统( d e s ) 。因此，可用d n a 算法解决 其它的密码问题。 ( 3 ) 基因治疗。2 0 0 1 年y a a k o v 提出了用分子自动机来诊断并治疗疾病的 设想【1 6 1 。此后，许多研究者把目光投向了基因治疗这一领域：如何用分 子的方法来诊断和治疗医学上的一些疑难病症。 ( 4 ) 用分子自动机来模拟电子计算机。分子计算作为计算科学中的一种 新的计算方法，并且具有传统计算机无法比拟的优点，因此，用用分子 自动机来模拟电子计算机是d n a 计算这一领域的又一发展方向。 1 5 研究内容及研究意义 自a d l e m a n 开创了d n a 计算这一研究领域以来，研究者们就提出了用d n a 分子的算法来解决问题的种种设想，并取得了可喜的成绩。这些问题中也包含了 如何用分子自动机来模拟电子计算机的设想。 在分子自动机中，酶是分子自动机的硬件，输入分子和转移分子是分子自 动机的软件，同时还编码了检测分子。设计一个分子自动机的关键在于选择合 适的软件分子。当输入分子，转移分子，所需的酶混合后，分子自动机将会通 过一系列的杂交，链接，提取，剪切等生物操作来处理输入分子，最终是否产 生编码自动机终结状态的检测性输出分子，从而判断该自动机是否接受某个输 入字符串。 目前，在分子自动机来模拟电子计算机方面已经取得了一些成果。但这比计 4 第1 苹绪论 算机理论知识的丰富性还差很远，并且这些设想都会受到某些条件的限制，通用 性差。 针对上述问题，本文提出了几种用分子自动机来模拟有穷自动机的模型，以 丰富分子自动机模拟电子计算机这一方面的理论知识。 1 6 本章小结 d n a 计算是一门新兴的交叉学科，在很多领域都有着潜在的应用。本章首 先对d n a 计算这一领域的发展背景作了简单的介绍，其次对d n a 计算的载体 - d n a 分子的结构进行了简单的介绍，随后阐述了d n a 计算的特点，发展状况， 生物操作技术及其d n a 计算的应用，最后介绍了本课韪的研究内容及研究意 义。 第2 章现有的有穷自动机及其分析 第2 章现有的有穷自动机及其分析 近几年来，在分子自动机模拟电子计算机方面取得的成就如下： ( 1 ) 1 9 9 5 年，r o t h c m u n d 提出了用分子算法来模拟图灵机的一步转移 规则，【3 3 】，但无法模拟图灵机的多步转移规则。 ( 2 ) 1 9 9 9 年，j a r o s e 提出了有限状态自动机的d n a 分子算法圈。 ( 3 ) y a s u b u m is a k a k i b a r a 提出了用d n a 算法来模拟有限状态自动机的另一 种方法嘲。在这种方法中，对输入字符串的编码中包括了对状态的编码 ( 长度取决于所模拟的自动机的状态的数目) ，这就对d n a 链的长度 提出了一个挑战。 ( 4 ) m g i y a 提出了另一种模拟自动机状态转移的方案嘲捌，但这种转移方 案需要一步一添加粘头，并且错配的机率高。 ( 5 ) m a t t c oc a v a l i c r e 提出了用生物分子来模拟下推自动机的方法【4 l 】。 2 1 最简单的n f a 的应用 在这里我们不考虑含有空串的正则语言，对于任何一个d f a ，都存在相应 的n f a m 满足： ( 1 ) m 有唯一的终结状态g ， ( 2 ) 没有进入起始状态g 。，也没有从终结状态g ，出来的转移。 一个简单的n f a 的分子应用称之为n f ap o t 2 6 l ，如图2 - 1 所示 n p n tj t r l 蜩 盛要蜀已墨 n f ap o c t o xm 图2 - i n f a p o t 的应用 它有下列的优势 ( 1 ) 用d n a 链编码m 的每个状态转移，不需要特殊的编码技术，每个d n a 链的长度是很重要的。 ( 2 ) 互补d n a 链的杂交是唯一的技术。 7 北京工业大学理学硕士学位论文 ( 3 ) 对于m 的一个输入w ，如果有一个完全的双链【c ( 忉，；丽被检测出来， 说明m 识别字符串w 。 2 1 1 实例 b q m - il ， 每个转移规则占( f ，a k ) = _ ，的编码为5 ，石积氤蠡矗衙i o i 3 ， 后代表在上述转移中的字符在字母表中的位置。8 ( j ，口掣) = 歹7 的分子编 m j 霉 i i 和嗥5 - 5 赢# a g g 蔗g g a a a i 3 7 码为a 从 a 3 ， 将上述两种转移分子结合起来得到 啊一； k讯 t 5 - 赢斧天氤乏 毛赢才洒i 舌_ 忑赢东i 一3 对上述m 的转移规则编码的转移分子为 a a g l o 量_ 1 ) nl 工h 啼2 i g g 2 j l 呻1 ) k g a t 1 基3 ) 8 第2 章现有的有穷自动机及其分析 输入字符串的编码为3 t t t c t 订c c 口t c c 韵盯c 锄汀5 将转移分子和输入字符串混合到起发生如下反应，如图2 - 3 所示 ，一 3 m c m c c 即c c t t t c 咖 _ ，妒o g 睁 5 m g a j ，。一4 3 ，_ t t r c 田t c c t r t c c 饿c 册 毒一一， 5 。 g a j q 母a 。 。 3 ，t t t ct t tc c 唧哪c t t t l ， ，强o u 3 5 ，- 崭罢擗c g c g 搿髭梅c 瞅 ； 三：ja k a 皂a a a 鳗a a - a a - a a o 枞 3 一t t t c t t t c c ? t r 云云t t t 云j 而滢 图2 - 3 自动机m 的分子链的反应过程 如果能提取出完整的双链分子就能判断出该自动机是否识别某个字符串。 2 1 2 将n f a 中的一个接受状态推广到多个接受状态 确定的有穷自动机m 是一个5 元组( q ，巧，冒。f ) ( 1 ) q 是有穷状态集，q = q o ，q 1 ) 。 ( 2 ) 是有穷的字母表，= 口l ，a 2 q ) 。 ( 3 ) 8 ：q x 妒( 9 是转移函数。 ( 4 ) g o q 是起始状态。 f q 是接受状态。 对于一个不含有空字符a 的正则语言，必有这样一个n f a 识别它。 下面我们如何设计一个分子自动机，来识别不含空字符五的正则语言 2 1 2 1n f a 的d n a 的实现方法我们用c 和t 对输入字符串进行编码，用a 和g 对状态转移进行编码。对输入字符串的编码方式如下： 9 北京工业大学理学硕士学位论文 要生a 一臭一、要 r 刀c 。c r rc c c r r m 为( 状态数1 ) ，t 表示输入字符串中的第i 个字符在字母表中的位置是 第后位。 ( 1 ) 如果一个状态既是接受状态，又有从它出发的转移，假设这个状态是 g ，( 接受状态) ，并有转移函数万( 吼，口七) = q j ，对此转移状态的编码 有两种 型苎= ! 要 么么g g 彳么和彳彳g g 4 彳 ( 2 ) 对于其它情况的状态转移8 ( q j ，q ) = 巳的编码只有一种 m - j t r ，- - 、- - - - - _ j 、- _ - 。- 、_ 么爿g g 么彳 将转移分子和输入字符串的分子混合杂交，经过足够长的时间后，如果能提 取出完整的双链，则说明此自动机m 识别该字符串。 证明：对字符串的编码方式确定了输入字符串中的字符及位置。因为t 中 的f 决定了字符在输入字符串中的位置，j i 决定了字符在字母表中的位置，从 而确保了输入字符串的唯一性。 对转移规则的编码，七个g 表示字母表中的第七个字符。 _ 一f t， z ：j 瓦：瓦j 表示在状态g f 下读到字母表中的第后个字符进入状态g ，。 z ：j 忘：赢j 表示在状态q i 下读到字母表中的第j 个字符进入接受状态 g ，。 转移分子中左边a 的个数( m - o 与相邻的上一步转移分子中的右边a 的个 数( i ) 之和为肌个。 如果n f am 识别该字符串，我们以下面的方式来阐述n f a m 是如何识别 该字符串的。 当n f am 读到输入字符串的第一个字符时，将会有相应的转移分子 肘if 一 、r 。 y ，、。v 。，l - b ( q o ，d 1 ) = 吼a a g g a a 和输入字符串中的相应部分发生互补反 l o 第2 章现有的有穷自动机及其分析 应。 当n f a 在状态g f 下读到输入字符串的第二个字符时，将会有相应的转移分 子万( g j ，口o ) = 乃 _ 彳- g 。g 。和输入字符串中的相应部分发生互补反 应。 依次进行下去 当 在状态，下读到输入字符串中的最后一个字符气。时，将会有 竺z 苎。要 相应的转移分子烈毋，吁) = 彳和输入字符串中的相应 部分发生互补反应。 如果的某个状态g f 下读到该输入字符串中的某个字符( 不是终结字 ! = ! 主 。三 符) 进入一个接受状态g ，时，转移分子万( 吼，哝) = 。 4 和输 入字符串分子中的相应部分发生互补反应，并为下一步转移提供了可能。 型。要 转移分子万( 吼，啄) = ，： 一4 和输入字符串分子中的相应部 分发生互补反应，这将阻止下一步转移的进行，此种情况下不可能形成完整的 双链分子。 最后，提取完整的双链分子，此双链分子所代表的字符串为该所识 别的字符串。 实际的例子下面举一个识别某些字符串的例子。 以为非确定自 动机，如图2 4 所示 。 站 图 非确定性自动机鸩 q = ，3 ) ，= 4 ，妨，万( o ，口) = ， ，6 ) = 2 ，万( 1 ，6 ) = 北京工业大学理学硕士学位论文 a ( 2 ，6 ) = l 。状态0 为起始状态，状态2 和状态3 为接受状态。 输入字符串为= a b ，w 2 = a b b b 。 对w 1 = a b 的编码分子为1 7 t c t i t c c t t t 对m ，2 = a b b b 的编码分子为t i t c t i t c c t i t c c t i t c c t i t 对a ( o ，口) = 1 编码的转移分子为a a a g a ， 对万( 1 ，6 ) = 2 编码的转移分子为- 4 , 4 g g a 4 和允4 g g j 4 , 4 两种， 对j ( 1 ，6 ) = 3 编码的转移分子为a 4 g g a j a ， 对a ( 2 ，6 ) = 1 编码的转移分子为彳g | 鳓。 n f a 如识别字符串= a b 的过程如图2 - 5 所示： ，月月月g 诅 丁玎t 力c ，7 丁 i 帆4 甜一一以蝴 7 竹口丁力c z 7 丁 l ； 4 4 a g 强a 4 g g 纠4 月 丁玎，e 丁丁7 c c 7 7 丁 图2 - 5 i w am 识别字符串的过程 n i a 如识别w 2 = a b b b 的过程如图2 - 6 所示： 1 2 第2 章现有的有穷自动机及其分析 ，一五a d g 4 t r t c t r t c c ! t t c c l t t c c r t t ； ，一，a a c 粥a a a a a g a j 哩1 7 c t t t c ( 骶t c 鼍t t c c r t t ； ，一a c - g a 。伽g 爿月月g g 丝月 i t ! ? t 誓t t c c ! t ! c c - 喱t c c 翟t t | t 。，a a c , g a a a a a a g a a a g g a a a c - - g a t f l l c tt t c c ? f t c c 霓t c c f t i l a 从g d4 g g 。44 a g g a a i g g a a a 疆! c f t t c c t t t c c t t t c c t t l 图2 - 6 n f a 鸩识别字符申w 2 的过程 2 1 3 结构特点 在这种方法中编码的都是单链分子，包括状态转移分子和输入分子。输入 分子链中间隔编码了输入字符串中的字符及状态的数目。用t 来编码状态，t 的个数代表状态的总个数减1 。用c 来编码字符。 输入分子链的结构如下： 其中( 1 ) ，( 3 ) ，( 5 ) 和( 7 ) 为( 状态的总个数减1 ) 个t ，( 2 ) 为读到的第1 个字符，( 4 ) 为读到的第2 个字符( 6 ) 为读到的第一个字符。 字符串中的每个字符都用c 来编码，比如用来编码第i 个字符的c 的个数 表示第i - l 字符在字母表中的顺序，因此这种编码方法就确定了输入字符串中的 字符及顺序。 对转移规则万( 吼，口) = q j ( 假设该自动机的状态为q o , q i , q 2 q 。) 转移分子链的结构如下： i ( n 朴al 字符a 的补链ij 个a 1 北京工业大学理学硕士学位论文 2 1 4 功能分析 此方法的编码技巧在于将输入字符串和转移规则都编码成单链，并利用状态 数目为定值这个条件，巧妙的设计了转移规则的编码。用于编码当前状态的a 的个数和用于编码下一个转移规则的起始状态的a 的个数之和为状态的数目减 1 。 按照上述的编码方式来设计分子自动机，当接受状态的个数增多时，错误杂 交的概率也会增大，这是因为当有从接受状态出发的转移时，那么对进入这个 接受状态的转移分子的编码有两种，这就增加了错误杂交的概率。此外，当状 态的数目比较多时，输入分子链的长度将变得很长，这将增大分子链因过长而 破裂的概率。 2 2w h i p l a s hp c r 方法 w p c r l 2 6 1 使用的方法是一个d n a 单链可以和它的一部分粘接，形成一个发 卡结构( 形成发卡结构是分子内部的反应) 的特点来模拟状态的转移。 2 2 1w p c r 的过程 ( 1 ) 设计转移规则( 占( p ，口) = 鼋，6 固，参) = ，) 。w p c r 采用的是d n a 单链的编码设计( 如图2 - 7 所示) ，矩形部分的d n a 链为阻止部分，状态 p ，g 及输入字符口用c ，g ，t 进行编码，阻止部分为a a a 。p 为p 的 补链。 ( 2 ) 粘接分子形成发卡结构。通过粘接，p 和p 发生互补杂交反应，然后 进行引物延伸，延伸到阻止部分停止，( 延伸缓冲液中不含碱基r d 这使得 阻止部分a a a 停止引物延伸。最终形成发卡结构。 ( 3 ) 分解。d n a 分子重新变为单链d n a 分子。d n a 链的一端为当前状态 q 的补链万。 ( 4 ) 进行下一步转移。重复( 1 ) ( 3 ) 的过程，进一步模拟m 的状态转移。 虿表示当前状态的补链，并为下一个转移占国，多) = ，做好了准备。 操作过程如图2 7 所示： 1 4 第2 章现有的有穷自动机及其分析 ( 1 ) 8 白矽= q 2 2 2 结构特点 图2 - 7 w p c r 的过程 该方法将自动机所有可能的转移路径编码成d n a 单链的形式，并利用了 单链d n a 分子中互补的部分发生互补杂交反应而形成发卡结构这一特点。并 且在此过程中需要一步一添加读入字符的d n a 编码链的补链，如果存在相应 的转移规则，单链d n a 分子就形成发卡结构，然后对发卡结构的d n a 分子链 进行解链，并进行下一步转移。 此方法存在下述缺点 ( 1 ) 生成所有可能的转移路径的复杂度较高。 ( 2 ) 需要一步一添加对读入字符进行编码的补链的粘头，而添加粘头是一个 比较复杂的操作，这也提高了该方法的复杂度 ( 3 ) 状态补链及读入字符的补链与状态链及字符链发生互补杂交反应，形成 发卡结构的过程中发生错配的概率较高，并且当状态数目比较多时， d n a 分子链将变得很长，容易导致d n a 分子链的破裂。 这种方法的最大特点是用到了分子内部反应形成发卡结构。我们可以采用 北京工业大学理学硕士学位论文 发卡结构的编码方式来设计其它方案的分子自动机。 2 3 两个状态的分子自动机 2 3 1s h a p i r o 用d n a 模拟d f a 我们用图2 - 8 所示的例子【2 q 来描述如何用d n a 分子来编码确定性有穷状态 自动机m 的状态转移规则的。 图2 - 8 自动机m 及其转移规则 首先介绍一下限制性内切酶f o l d 是如何作用在d n a 双链上的。f o l d 的识 g g a t gg g a t g 别位点为c c t a c ，它遇到剪切位点c c t a c 时，将从其后数起，在上面数9 个 d n a s ，下面数1 3 个d n a s 处进行剪切，如图2 9 所示 。船。j i r 川 船9 专删 ，- - o 、 l 磷寇蕊一缆l c c 誓a c lx 2 盆醚2 xy y ) 0 凸谨鼬 嗡 图2 - 9 酶f o k i 的剪切方式 表2 1 字符a b t 的编码方式 口 矗 r ( t e r r a , i n t o n t s4t s 每， c s , 4 ， 锄 髭高沁 穑( ；c t s 目l蕊， k 。、，一 l s4 ， 1 6 第2 章现有的有穷自动机及其分析 对于字符口的编码，前四个碱基代表( 墨，口) ，后四个碱基代表( & ，口) ，对于 字符b 的编码，前四个碱基代表( s ，6 ) ，后四个碱基代表( & ，6 ) ，f 是编码的终 结字符。转移分子的编码包括三部分 ( 1 ) 酶f o k i 的识别位点 t a c ( 2 ) 状态转移标识。( 如f o l d 识别位点后的三个碱基长度的d n a 双链a r g 代 a c g a c 表状态未发生改变。f o l d 识别位点后的五个碱基长度的d n a 双链t g c 瓢 代表由状态瓯进入状态墨。 ( 3 ) 代表( 状态，字符) 的d n a 链的补链。 其中的两个转移分子如图2 1 0 所示 移禹黜c 泓滔s c e n t e r 图2 1 0 自动机m 的两个转移分子 同时还要编码接受状态的检测分子，如下： m t e r 其次将对d f a m 识别的字符串进行编码，比如对d f a m 识别的字符串曲 进行编码 丽爵甬丽笛积磊衙历乐器罚惫翮 c - - r a cx z 麟x ko e c o o t c o a c a o c o m 其中7 个长度的碱基对x _ 和3 个长度的碱基对y 代表任意的碱基。 下面判断d f a m 如何来识别字符串西的。如图2 1 1 所示 1 7 北京工业大学理学硕士学位论文 加入够s 酒甄话t a c 幽t g c c c , a i i 生成 v 加a l f 搠孙弹 + 。a c a a c 0 1 岍 l 髑砣翮 二净a c a o c ：g f f f 俯 图2 - 1 1d f a m 识别字符串口6 的过程 x 掇o q c 蛋：m x x x o c o ? 憎 1 8 摭。 ：一 酶 u h uu巍幽u 第2 章现有的有穷自动机及其分析 2 3 2b e n e n s o n 的两个状态的分子自动机 对于输入字符口 6 及终结符t 的编码【3 8 】如表2 - 2 所示 表2 2 输入字符的编码 对于两个状态的，两个字符的自动机有8 种可能的状态转移分子如图2 1 2 所示 图2 1 28 种可能的转移分子 其中1 2 代表1 2 个任意的碱基对，深灰色的部分代表酶f o k i 的识别位点， 露出的粘头代表( 状态，符号) 标识，中间的代表状态转移标识，o 个碱基长度的 代表由状态墨到状态s o ，一个碱基长度代表状态不发生改变，2 个碱基长度代 表由状态岛进入状态墨，对输入字符进行如下的编码 下面举一个例子说明自动机坞如何来识别字符串a a b 的，如图2 1 3 所示 图2 1 3 自动机的转移规则 对输入分子进行如下的编码 1 9 北京工业大学理学硕士学位论文 下面是自动机识别字符串a a b 的过程。如图2 1 4 所示 图2 - 1 4 自动机坞识别字符串a a b 的过程 2 0 第2 章现有的有穷自动机及其分析 通过凝胶电泳对试管中的分子进行电泳，找出含有终结字符t 和接受状态 瓯的d n a 分子链，从而检测出上述自动机识别字符串a a b 。也可编码一个检 测分子来判断上述自动机识别字符串鲫6 。 2 3 3 结构分析 b e n e n f l o n 模型的转移分子自动机的结构 曰习k 其中( 1 ) 为1 2 个碱基长度，( 2 ) 表示酶f o k i 的识别位点，( 3 ) 表示状态 转移标识，( 4 ) 表示当前的状态及读到的字符。 输入字符串分子的结构： 其中( 1 ) 表示起始状态及读到的字符的补链，( 2 ) 和( 4 ) 为3 个碱基长 度的间隔( 3 ) 表示读到的第2 个字符，( 5 ) 表示读到的第3 个字符，( 6 ) 表示终 结标识，( 7 ) 为1 5 个碱基长度。 转移分子链中的状态转移标识的长度不同，长度为1 个碱基长度表示状态 未发生变化，长度为0 个碱基长度表示状态由状态s 进入状态岛，长度为2 个碱基长度表示状态由状态瓯进入状态墨。同时编码了所有可能的转移分子。 字符的编码中包含了状态的编码，也就是状态和字符一起编码。 2 3 4 功能分析 此种编码方法的优势在于状态和字符一起编码，关键在于字符与字符之间 的长度间隔及转移分子链中状态转移之间的长度间隔。当转移分子和输入字符 串分子发生正确的互补反应后，酶f o l d 将对此双链分子进行剪切，产生下一个 状态( 包括读入的字符) 的粘头。同时编码了一个检测分子，如果自动机识别 某个字符串，那么最后切出的输入字符串分子链中的粘头分子链将和检测分子 发生互补反应，从而产生一个正确的输出。 此方法的缺点在于：当状态数目比较多时，字符和状态一起编码会遇到很 大的困难，同时状态转移之间的间隔长度及字符之间的间隔长度会变得很复杂。 2 4j a r o s e 用分子自动机来模拟有穷状态自动机 2 4 1 实例 不 下面以三个状态的自动机为例吲来说明d n a 如何模拟自动机，如图2 1 5 所 图2 1 53 个状态的自动机 d n a 模拟自动机首先得对每个状态进行编码。 状态o ：t t 吼 状态l ：g e t s 状态2 ：c t c a c 托g g g a t c t 七a t c t t d , 对起使分子进行编码( ：c c c t c t j t g 为了正确的模拟状态的转移，每个状态需要编码带有一个环的d n a 双链， 其中一部分是未杂交的d n a 单链。假设状态为0 ，l ，2 ，输入字符为0 和l 。 那么就有6 种不同的连接：0 0 ，1 0 ，2 0 ；0 1 , 1 1 , 2 10 0 ，1 0 ，2 0 ；0 1 ，1 1 ，2 1 代表状态0 ，1 ，2 输入的字符分别为0 和l 。 第2 章现有的有穷自动机及其分析 0 0 ： a ? mii c c c g g g g a ga t c t t a a g a g c a a t a 丘u l t r g g g c c c c t ct a g a a t t c t c o l ： ? g 白t c c c c a a 七a t t g g g c c c c g t 七g c t t 直 g 直gc 一 c g t t c t c 我们发现0 1 中的g c a t g c g c t g 代替了o o 中的g a g a t c t t a t 。上述两种分子 编码了在状态0 输入字符0 进入状态0 的分子和在状态0 输入字符1 进入状态 1 的分子。其中g a g 编码的是0 ，g c a 编码的是1 。 1 0 ： 。 cc。i c c c g g g g a gc a c t t a a g a gc c g a c g a a t t g g g c c c c t c g t g a a t t c t c 1 1 ： ?mtt c c c g c - g g c ax t c t t a a g a g c c g 矗c m 削1 陷g g c c c c 田 一t a g a a t t c t c 我们发现1 l 中的g c a a t c t t & t 代替了l o 中的g a c ；c a c t t c a 上述两种分子 编码了在状态1 下，输入字符为0 时进入状态2 的分子和在状态1 下，输入字 符为1 时进入状态0 的分子。 r 口句e c c c g g l 量g g a g t g a a t t g g