（系统工程专业论文）四类DNA计算模型中一些理论与应用的研究.pdf

华 中 科 技 大 学 博 士 学 位 论 文摘要 本文对四类d n a 计算模型中的一些理论及其应用进行了研究和讨论，具体工作如下: 粘贴系统是建立在粘贴运算基础上的语言生成器，也是一种遵循 w a t s o n -c ri c k 互补性质进行退火操作的d n a计算抽象模型。 本文将线性串的 粘贴系统拓展到带有发夹结构的双向复杂结构粘贴系统， 使粘贴系统的纯理论研究向实际生物操作技术研究迈进了一步。给出了双向复杂结构粘贴系统的定义及其基本运算;提出了双向复杂结构粘贴系统的分类;讨论了双向复杂结构粘贴系统的生成能力和计算能力;最后，通过双向复杂结构粘贴系统的弱编码刻画了递归可列语言，这表明双向复杂结构粘贴系统与递归可列语言族有相同的计算能力。 粘贴模型有一个随机存取存储器，所使用的 d n a链具有固定长度，操作时不需扩展 d n a链，也无需酶的参与，并且它的材料在理论上可以重复使用。 本文给出了图顶点着色问题的d n a粘贴算法。在研究图顶点着色问题时，从问 题的本质出发，先把图的顶点着色问题分解成顶点独立集问题和顶点划分问题并给出 这两个问题的d n a粘贴算法， 然后调用这两个算法以解决图的顶点着色问题。 图的全着色猜想是由m . b e h z a d 和v i z i n g 于1 9 6 5 年提出的。 到目 前为止， 对于一般的图，全着色猜想仍然是一个公开的问题。本文从系列平行图的结构性质出发，利用双重归纳法和换色技巧确定了系列平行图的全色数。 剪接系统是将剪接运算当作基本算子的一种语言生成器，其中剪接运算是对在限制性内切酶、 d n a连接酶、 d n a聚合酶和外切酶作用下， d n a链进行重组过程的数学抽象。本文利用剪接系统的巨大并行性，首先设计了模拟有向哈密顿路问 题的剪接系统:然后通过此剪接系统所产生语言的性质对有向哈密顿路问 题进行分析，给出了有向图的若干结构性质以 及图中存在有向哈密顿路的充要条件。 图的最小顶点筱盖问题是图论中的一个n p 完全问题。它在分子生物学、调度问题、错误诊断和恢复集装线平衡、油轮行程安排及开关理论中有着广泛的应华 中 科 技 大 学 博 士 学 位 论 文用。本文利用 d n a表面计算模型对图的最小顶点覆盖问题进行了建模。构造了含有n 个顶点m条边的图的顶点集子集对应的数据池之后，循环进行了合成、杂交、清洗、变性等生物操作，得到所有覆盖对应的d n a序列，然后通过编址过程得到我们所要求的最小顶点攫盖。最后通过6 个顶点1 0 条边的图对所建模型进行了验证。关键词:d n a计算粘贴系统粘贴模型剪接系统最小顶点覆盖问题系列平行图华 中 科 技 大 学 博 士 学 位 论 文ab s t r a c t i n t h e t h e s i s , s o m e t h e o r i e s a n d a p p l i c a t i o n s i n f o u r t y p e s o f d n a c o m p u t a t i o nmo d e l s a r e s t u d i e d a n d d i s c u s s e d . t h e ma i n r e s u l t s a r e s u mma r i z e d a s f o l l o ws : t h e s t i c k e r s y s t e m i s a l a n g u a g e g e n e r a t i v e m e c h a n i s m b a s e d o n s t i c k i n go p e r a t i o n s a n d a d n a c o m p u t a t i o n a b s t r a c t m o d e l t h a t f o l l o w s w a t s o n - c r ic kc o m p l e m e n t a r i t y r e l a t i o n t o a n n e a l . i n t h i s d i s s e r ta t i o n , t h e s t i c k e r s y s t e m s o f l i n e a rs t r i n g a r e e x t e n d e d t o b i d i re c t i o n a l s t i c k e r s y s t e m s w it h c o m p l e x s truc t u r e s , w h i c hm a k e s t h e p u r e t h e o re t i c a l s t u d y s t e p f o r w a r d t o b i o l o g i c o p e r a t i o n t e c h n i q u e s . t h ed e f in it i o n a n d b a s i c o p e r a t io n s o f b i d i r e c t i o n a l s t i c k e r s y s t e m s w i t h c o m p l e x s t r u c t u r e sa r e g i v e n o u t . t h e c l a s s i fi c a t i o n s o f b i d i r e c t i o n a l s t i c k e r s y s t e m s w i t h c o m p l e xs t r u c t u re s a r e p r o p o s e d . t h e g e n e r a t i v e a n d c o m p u t a t i o n a l c a p a c i t i e s o f b i d i r e c t i o n a ls t i c k e r s y s t e m s w i t h c o m p l e x s t r u c t u r e s a r e d i s c u s s e d . f i n a l l y , t h e c h a r a c t e r i z a t i o n o fr e c u r s i v e l y e n u m e r a b l e l a n g u a g e i s p r e s e n t e d b y m e a n s o f w e a k c o d i n g o f t h e a b o v es y s t e m s , w h i c h m e a n s t h a t b i d ir e c t i o n a l s t i c k e r s y s t e m s w i t h c o m p l e x s t r u c t u r e s h a v et h e s a m e c o m p u t a t i o n a l c a p a c i t y a s t h e f a m i l y o f r e c u r s i v e l y e n u m e r a b l e l a n g u a g e s . t h e s t i c k e r m o d e l h as a r a n d o m a c c e s s m e m o ry a n d i t s d n a s t r a n d s h a v e a f i x e dl e n g t h . t h e o p e r a t i o n s re q u i r e n o s t r a n d s e x t e n s i o n , u s e n o e n z y m e s , a n d i t s m a t e r i a l sa re r e u s a b l e i n t h e o ry . i n t h e d i s s e r t a t i o n , d n a s t ic k e r a l g o r it h m o f v e rt e x - c o l o r i n gp r o b le m s i s g i v e n o u t . wh e n t h e v e r t e x - c o l o r i n g p ro b l e m s o f g r a p h b e i n g s t u d i e d , t h e ya r e d e c o m p o s e d i n t o v e rt e x - i n d e p e n d e n t s e t p r o b l e m s a n d v e rt e x - p a rt i t i o n p r o b l e m sfr o m t h e e s s e n c e o f p r o b l e m s a n d d n a s t i c k e r a l g o r i t h m s o f t h e t w o p r o b l e m s a r es h o w e d ; t h e n t h e v e rt e x - c o l o r i n g p r o b l e m s o f g r a p h a re s o l v e d b y t r a n s f e r r i n g t h ea b o v e t w o a l g o r i t h m s . i n 1 9 6 5 , m.b e h z a d a n d v i z in g p r o p o s e d t h e t o t a l c o l o r i n g c o n j e c t u r e o f g r a p h s .s o f a r , f o r a n y g r a p h , t h e t o t a l c o l o r i n g c o n j e c t u r e i s s t i l l a n o p e n p r o b le m . i n t h i sd i s s e r ta t i o n , t h e t o t a l c h r o m a t i c n u m b e r o f s e r i e s - p a r a l l e l g r a p h s o f m a x i m u m d e g r e ei n华 中 科 技 大 学 博 士 学 位 论 文g r e a t e r t h a n o r e q u a l t o 4 w i l l b e d e t e r m i n e d u s i n g t h e d o u b l e i n d u c t i o n s a n d t h et e c h n i q u e s o f e x c h a n g i n g c o l o r s fr o m t h e a s p e c t o f c o n f i g u r a t i o n p r o p e r t y . t h e s p l i c i n g s y s t e m i s a l a n g u a g e g e n e r a t i v e m e c h a n i s m b a s e d o n s p l i c i n go p e r a t i o n s , w h e r e s p l i c i n g o p e r a t i o n s a r e t h e m a t h e m a t i c a l a b s t r a c t i o n s o f d n as t r a n d s r e c o m b i n a n t b e h a v i o r s u n d e r r e s t r i c t i o n e x o n u c le a s e s , e n d o n u c l e a s e s , d n al i g a s e s a n d d n a p o l y m e r a s e s . i n t h i s d i s s e rt a t i o n , t h e i d e a s o f s i mu l a t i n g d i r e c t e dh a m i l t o n p a t h p r o b l e m s b y s p l i c i n g s y s t e m s a r e d e s i g n e d u s i n g t h e i r m a s s iv ep a r a l l e l i s m ; t h e n s o m e p r o p e rt i e s o f d i r e c t e d g r a p h s a n d s u f f i c i e n c y a n d n e c e s s i t yc o n d i t i o n s o f e x i s t i n g h a m i l t o n p a t h s i n g r a p h s a r e p r e s e n t e d b a s e d o n t h e a n a l y s i s t od i r e c t e d h a m i l t o n p a t h p r o b le m s a c c o r d in g t o t h e p r o p e r t i e s o f la n g u a g e s g e n e r a t e d b yt h e s p l i c i n g s y s t e m s . i n o u r c o n s t r u c t i o n , t h e s p l i c i n g s y s t e m s s im u l a t i n g p r o b l e m s r u na t m o s t n 一 2 s t e p s , w h e r e n i s the s i z e o f p r o b l e m s t h e m i n i m a l v e r t e x - c o v e ri n g p r o b l e m o f g r a p h i s a n p - c o m p l e t e p r o b le m o fg r a p h t h e o ry . i t m a y a p p l y w id e l y t o m o l e c u l a r b i o l o g y , s c h e d u l e p r o b l e m , e r r o rd i a g n o s i s , t h e b a l a n c e o f r e s u m e a n d c o l l e c t i o n , th e j o u rn e y p la n o f o i l t a n k e r a n ds w it c h t h e o ry . i n t h e d i s s e r t a t i o n , t h e m i n i m a l v e rt e x - c o v e r i n g p r o b l e m s a r e s t u d i e df r o m t h e p o i n t o f c o m p u t a t i o n a l m o d e l s b a s e d o n s u r f a c e . i n t h e d n a c o m p u t a t i o n a lm o d e l s o n s u r f a c e , a ft e r a d a t a p o o l b e i n g c o n s t ru c t e d c o r r e s p o n d i n g t o t h e s u b s e t s o f av e rt e x - s e t o f a g r a p h w it h n v e r t ic e s a n d m e d g e s , a s e r i e s o f b i o c h e m i c a le x p e ri m e n t s : s y n t h e s i s , h y b r i d i z a t i o n , c l e a n i n g a n d d e n a t u r a l i z a t i o n e t c a r e p r o c e e d e da n d t h e d n a s e q u e n c e s c o r r e s p o n d i n g t o a l l t h e c o v e r i n g s a r e o b t a i n e d ; t h e n a l l t h emi n i ma lt h e b u i l tc o v e r in g s a c c o r d i n g t o t h e e n c o d i n gm o d e l s a r e v e ri f i e d b y a g r a p h w i t h 6a d d re s s p r o c e d u re a r e l i s t e d . a ft e r a l l ,v e r t i c e s a n d 1 0 e d g e s .k e y w o r d s : d n a c o m p u t i n gs t i c k e r s y s t e ms t i c k e r mo d e ls p l i c i n g s y s t e mmi n i ma l v e r t e x - c o v e r i n g p r o b l e ms e ri e s - p a r a l l e li v独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。学 位 论 文 作 者 签 名 ;谁 4 ,?日 期 ，/ 三 月 丫学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、保密口缩印或扫描等复制手段保存和汇编本学位论文。在_年解密后适用本授权书。本论文属于不保密可( 请在以上方框内打 “1 / 1 1 )学 位 论 文 作 者 签 名 :福 条找 -日 期 :ja 0 ip , 。 月 14 9指导教师签名:,- y - -日 期 丫钾 产 理华 中 科 技 大 学 博 士 学 位 论 文1 绪论1 . 1 d n a计算产生的背景 众所周知，电子计算机为人类社会的发展起了巨大的促进作用。 然而，随着社会的不断进步，电子计算机在处理现实生活中的许多难题和复杂巨系统，形形色色的 n p 一 完全问题时， 都显得无能为力! 其主要原因在于:电子计算机的存储量小、运算速度慢、智能化低，这就迫使人们寻找一种能克服上述缺点的新型计算机，如人工神经网络计算机、量子计算机、光学计算机以及d n a 计算机等f 1 - 9 ,1 1 3 - 1 2 1 1 ， 其中 d n a 计算机在近十年来倍受科学界的关注。1 9 9 4 年， 美国 加利福尼亚大学的a d l e m a n 博士首次提出利用d n a( 脱氧核糖核酸) 对图论中的一个n p完全问 题一有向哈密顿路问 题进行编码，借助连接、变性、复性、 p c r 扩增、电泳等生 物操作解决了 这一问 题 1 1 0 1 。 这一 研究成果很快引 起了 计算机、 数学、 分子生物学等领域的科学家们的极大兴趣。它的重要意义不仅仅在于算法和速度，更在于采用了一种全新的介质作为计算要件，以生物技术来实现电子计算机无法解决的困难问题，并开发了d n a 计算潜在的巨大并行性。其后，wi s c o n s i n 大学、p r i n c e t o n 大学、s t a n f o r d 大学、加州理工学院 ( c i t )等相继开展了这方面的研究工作，并得到了美国国家科学基金会和五角大楼国防高级研究项目 局的支持。d n a 计算是以 d n a 和相关生物酶为基本材料、 利用某些生化反应进行计算的一种新型的分子生物计算方法。 它的基本思想是利用d n a 特殊的双螺旋结构和碱基互补配对规律进行信息编码， 把运算对象映射成d n a 分子链， 并在生物酶的作用下生成各种数据池( d a t a p o o l )， 然后按照一定的 规则将原始问 题的数据运算高度并行地映射成d n a 分子链的可控生化过程。 最后， 利用分子生物技术如聚合链反应p c r 、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等检测所需的运算结果。 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 计 算 机 19 1 和传统的电子计算机相比，d n a计算机有如下突出优点9 .11 1 . ( 1 ) 高度并行性，运算速度快，在一周内的运算量相当于所有电子计算机问世以来的总运算量; ( 2 ) 储存量大， d n a作为信息的载体其储存容量非常之大，1 立方米的d n a溶液可存储1 万亿亿的二进制数据，远远超过目 前所有电子计算机的总储存量; ( 3 ) 耗能低，d n a计算所消耗的能量只有一台电子计算机完成同样计算所消耗能量的十亿分之一; ( 4 ) d n a分子的资源丰富。 现在从植物和动物中提取d n a技术已经很成熟，而自 然界的植物和动物处处可见。 d n a计算机的上述优点及应用背景极大地吸引了不同学科、 不同 领域的众多科学家，特别是计算机科学、分子生物学、数学、物理学、化学以及信息学领域内的科学家们。 d n a计算机有望成为人类科学史上的一个新的里程碑， 因为d n a计算机有可能解决目 前在电子计算机上许多无法解决的问题，如密码破译、困难n p 一 完全问题以及工程领域中最大的难题一局部极小值问题等。目 前国际上d n a计算领域的研究成果层出不穷，大大促进了数学、计算机科学和生物学等的相互交叉与渗透。 d n a计算与d n a计算机的研究发展神速， 在诸如d n a计算应用于一些n p 一 完全问题解法、 d n a计算的运算问 题、 d n a计算在生物实 验方面的研究、 d n a计算机的语言系统、联想记 忆问题、d n a计算在密码学上的应用等都 取 得 了 不 少巨 大 的 进 展 2 a 气华 中 科 技 大 学 博 士 学 位 论 文1 . 2 d n a 计算的研究现状 1 9 9 4 年， 美国 加利福尼亚大学的a d l e m a n 利用现代分子生物技术， 首次提出了有向哈密顿路问题 ( d i r e c t e d h a m i lt o n i a n p a t h p r o b l e m， 简记为d h p p ) 的d n a计算方法，并在d n a溶液中 成功地进行了实 验11 0 1 。这在国际上引 起了巨 大的反响，也开创了d n a计算的 新纪元。1 9 9 5 年， l i p t o n 在a d i e m a n 思想的启发下，通过构造一个接触网络图g， 将s a t问题的的解空间映射为通过接触网络图g的始点a ， 和终点。 。 的 所有哈 密顿路1 1 。 他首 先利用d n a 链表示问 题的 所有可能 解，然后利用生化反应删除无效解。1 9 9 6 年，s a m r o w e i s 等人介绍了一种新的d n a计算模型一粘贴模型，并用此模型解决了最小集合覆盖问题和数据加密问题(1 8 .4 1 ,4 6 o 1 9 9 7 年， o u y a n g q i 等利 用d n a计 算解 决了 另 一 个n p 一 完 全问 题 一图的 最 大 团 问 题 9 1 0 2 0 0 0 年 ， 日 本t o k y o 大 学的s a k a m a t o 等 巧 妙的 运 用 单 链d n a分子的“ 发夹” 结构， 将逻辑运算的约束条件编码于d n a分子中， 通过d n a分子 的自 组 织 过 程 解 决 了 一 个3 一 可 满 足 性 问 题 2 0 e w i s c o n s in 大 学 的l iu q in g h u a等 介 绍 了 一 种 基 于 表 面 的s a t 问 题 的 解 决 方 法 2 1 -2 3 0 2 0 0 1 年 ， w u h a o y a n g 对 此方 法 进行了 改 进 2 4 ， 使d n a 计 算 机的 发 展向 芯片 化 方向 迈 进了 一 大 步。 同 年1 1月，以色列的w e i z m a n n 研究所的b e n e n s o n 研制出由d n a分子和酶分子构成的生物计算机， 该机器是一种可编程的、 可自 治地解决组合优化问题的有穷自 动机，这种有穷自动机由d n a和操作d n a的生物酶构成。 该自 动操作的硬件由限制核酸酶和连接酶构成，软件和输出由双螺旋输出编码，且编程相当于选择适当的软件分子。对这些成份的混合溶液，该自 动操作处理由限制、杂交和连接循环的阶式蒸发器的输入分子， 产生出可检测的输出分子，这种输出分子对于自 动操作的最 终 状态 进 行了 编 码， 这也 就 是 计算的 结果 【2 5 0 2 0 0 2 年， a d le m a n 小 组 采 用 一 种新的实验方法给出了半自 动化自 组装d n a计算模型， 并利用该模型解决了含有0 个 变 量的3 一 可 满足 性问 题 2 6 1 . 同 年2 月， s a k a k ib a r a 等 研 制出 一台 用 于 基因 表达 分析的d n a计算机，它由 两部分组成:分子计算组件和检测部分。 前者通过生 化 反 应， 筛选出 正 确的 结 果， 后 者对 所 得到的 结 果 进行 分 析 2 7 . e n g 提出了 一华 中 科 技 大 学 博 士 学 位 论 文种s a t 问 题的 活体d n a 计 算方 法 【2 6 1 , c tlk r a 3 等 人用r n a 代替d n a 给出了 可 满足性问 题的 一种实 验性的 计算模型， 并 讨论国 际 象棋问 题的r n a计算 模型 12 9 1 .o l i v e : 提出 布尔矩阵和正实数 矩阵 相乘的d n a计 算方法3 0 1 e t o m h e a d 提出了 用质 粒d n a分子 解决图的 最 大 独立 集问 题 3 1 1 。 高 琳， 马 润 年， 许进 利用 质 粒d n a分子结构给出了图的最大匹配问 题的d n a计算模型【3 2 。 殷志祥， 许进， 董亚非等人给出了工序问题、中国邮递员问题、简单的0 - 1 规划问题的 d n a计算模型1 3 2 .1 3 7 ,1 8 6 ,1 8 7 1 。 张 凤月， 殷志 杯， 许 进作了 基 于芯 片 上的d n a计 算的 研究 1 4 3 1刘文斌，王淑栋，许进等给出了哈密顿圈问题、3 - s a t问题、图的顶点着色问题和最大匹配问 题的d n a计算 模型和算法1 3 5 ,1 3 8 - 1 4 0 1 。 张连珍， 许进给出了 一种基于环状质粒d n a计算的新方法。这种计算质粒包含一个特殊的d n a序列片断，通过剪切和连接质粒 d n a实现计算过程，并讨论了0 -1 背包问题的质粒 d n a计算 模 型 6 7 1 。 另 外， 科 学 家 们 还 利用d n a 计算 方 法 研究了 有 界邮 政 通信问 题 1 4 9 1路 着色问 题 1 0 1 , d n a加 法 【3 9 ,1 0 3 1 ， 数 据 加密问 题 14 1 4 3 1 ， 计 算 机 代数问 题 11 0 4 l , p e t ri网 结 构 8 5 1和 有穷自 动 机 【3 3 等。 尽管 d n a计算机己经取得了很大的进展，但在理论上仍存在三个根本性的问 题 需 要 解 决 5 5 . ( 1 ) d n a计算机可以解决哪些问题?确切地说， d n a计算机是完备的吗?即d n a计算机能完成所有的 ( 图灵机)可计算函数吗? ( 2 ) 是否能设计出可编程的d n a计算机?即是否存在类似于电子计算机的通用计算模型一图灵机一那样的通用d n a计算系统 ( 模型)? ( 3 ) d n a计算机的计算能力能否超过图灵机或者超级计算机? 为了回答上述问题，科学家把 d n a计算模型划分为两类:1生物操作基础上的模型，并且这些操作都可以在实验室成功进行。2 ， 形式上的模型。首先把一种或多种生物操作技术抽象为算子，然后在这些算子基础上进行建模。这类模型研究起来比第一类模型容易，但在建模时却较为困难，它必须与实际操作结合起来。目 前，许多科学家都在潜心研究这两类 d n a计算模型。在我们看来，这就 类 似 于 在电 子 计 算 机 诞生 之 前的2 0 世 纪 三四 十 年 代 一理 论 计 算 机 的 研 究 阶 段 。一一 一一一一 一 一一 一一一- 一一 一一一州 一- a华 中 科 技 大 学 博 士 学 位 论 文近几年来， d n a计算理论一直是西方发达国家的一个研究热点。 科学家也提出了多种d n a计算模型， 都各有千秋。 但是公认的d n a计算机的 “ 图灵机”还没有诞生。下面我们就简要地介绍四种d n a计算形式模型及其国内外发展现状: 1 . 粘 贴 系 统( s t i c k e r s y s t e m ) 1 8 ,4 4 -5 3 ,7 3 ,7 8 ,7 9 粘贴系统是建立在粘贴运算基础上的语言生成器，也是一种遵循 w a t s o n -c r i c k 互补性质进行退火操作的d n a计算抽象模型。 1 9 9 8 年， l .k a r i 引入了粘贴系统的定义 4 4 ,4 5 ,7 3 1 ， 并讨论了 粘贴系统与d n a计算的 关系， 最后用形式语言的特征刻画了粘贴系统的一些性质。她把粘贴系统定义如下:粘贴系统具有结构y = ( v , p , a , d ) ， 其中v 是字母表，p c_v x v 是对称关系，a 是l r , ( v ) 的一个有 穷 子集， d 是叽( v ) x 叽( v ) 的 一个有 穷子集。 关系p 是v 上的 互补关系， a 的 元 素 称 为 公 理 。 从 公 理出 发 ， 应 用d 中 多 米 诺 骨 牌 对( u , v ) ， 得 到 w k p ( v ) 的 一 个 双 链序列集合，因此通过粘贴运算可以得到完整的分子。也就是说粘贴系统可以建 立与d n a分子类似的双链序列语言。 1 9 9 6 年， s a m r o w e i s 等 人 构 造了 一 种 新的d n a 计 算 模 型一 粘 贴 模型 1 8 , 4 8 1 此模型有一个可随机访问的存储空间，操作时不需要延伸 d n a链，也无需酶的 参与，并且它的材料在理论上是可以重复使用的。他们提出了用粘贴模型来设计 生物计算机的设想，该机器是分子计算中的一种并行机器人工作站，通过一个中 心可编程电子计算机控制其中的各种机器人、液流装置、加热器、制冷器以及一 些传统的电子设备。 对于模型中的每一步运算， 可以 选择特殊的物理过程来实现。 他们在这篇文章中还讨论了如何设计存储链来避免操作中d n a二级结构的形成， 这也是d n a计算中尚未解决的一个难题。 2 0 0 1 年， k a r l - h e i n z z i m m e r m a n 设计了一种粘贴模型的软件平台， 并用此平 台 下 的d n a 粘 贴 算 法 研究 了 二 进 制 线 性 编 码 4 7, 4 8 1 。 同 年 ， y s a k a k i b a r a 用复 杂 结 构分 子 给出 了 一 种 粘贴 系 统的 变形 4 9 1 。 从 原 始的 粘 贴 系 统定 义 来说， 这 种 系 统 可 以看成是单向粘贴系统。2 0 0 2 年，b r a i c h 和l e o n a r d a d le m a n 等人将粘贴模型和 表 面 技 术 相结 合， 解 决了 一个 具 有2 0 个 变量的3 - s a t 问 题 2 s 1 ， 这 是 非电 子 技 术一 一一一 一一一 一门 一一一一 一- 5华 中 科 技 大 学 博 士 学 位 论 文 中规模最大的一个算例。同年，k a r l - h e i n z z i m m e r m a n 利用粘贴模型给出了图的 子图求解，图的所有k 一团，k 一独立集，哈密顿路与圈以及s t e i n e r 树等问题的 d n a计算模型及其实现算法 (5 0 1 。 他用小 规模数 据库代替通常用到的 大 规模数 据 库，然后在解决实际问题时再反复调用小规模数据库和己有的程序块。这些算法 不仅确定了解的存在性而且产生了所有的解，并且对于具有n 个顶点m条边的无 向图g，这些算法的运行时间是在n 十 ，线性时间内。高琳和许进给出了图的顶 点 覆 盖问 题d n a 粘贴 模型 及其实 现算 法 5 1 1 。 文 献 5 2 1 对d n a 计算 粘贴 模型 给 予 较为详细地讨论， 诸如基本模型、在粘贴模型基础上建立起的粘贴系统、k 一 进制 粘贴模型理论及其应用、粘贴模型在图与组合优化上的应用等，并建立了图的顶 点着色问 题k 一 进制粘贴模型(5 3 1 d n a粘贴算法也有其局限性:1 . 存储链的长度问题。在倾倒和混合试管中 的溶液时，长于1 5 0 0 0 个碱基的核昔酸就会断裂。所以，随着实际问题的规模增 大， 存储链的设计和长度问题也是一个有待于解决的问题。 2 . d n a操作的速度问 题。 在适合的条件下，已 经分离的互补链由 于碰撞又退火形成双链分子。 3 . d n a 操作的易出错性。所以，上述 d n a粘贴算法的真正实现还需分子生物技术的进 一步发展。 2 . 剪 接 系 统( s p l i c i n g s y s t e m ) 5 4 -8 8 ,7 3 -7 8 ,8 8 .8 9 ,1 5 ， 一 ， 5 2 ,1 9 0 1 剪接系统是将剪接运算当作基本算子的一种语言生成器， 其中剪接运算是对 在限制性内切酶、外切酶、d n a连接酶和 d n a聚合酶的作用下，d n a链进行 重组过程的数学抽象。 即: 给定字符集e 及其上的两个字符串x . y ， 利用剪接规则 ; 剪接x 和y 的过程可以分为: ( 1 )剪 接规则r 决定的 位置上切割x 和y ; ( 2 ) 分 别 将 结 果 中 二 的 前 段 和 ， 的 后 段 、 ， 的 前 段 和 二 的 后 段 连 在 一 起 。 艺 上 的 剪 接 规 则 : 是 形 如 a , # 乃 $ a 2 # 八的 词 ， 其 中 a , , 八 、 a s . 八 是 艺 上 的 串 ， “ 和 $ 是 艺 外 的 标 记 符 。一一一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 - 一 - 一 一 一 一 一 一 6华 中 科 技 大 学 博 士 学 位 论 文我 们称: 和， 是根据剪 接规则r = a , # 八$ a 2 # 几剪接x 和v 的 结果， 当 且 仅当存 在艺 上 的 x 1 , x , , y z y z 使 得x = x ,a ,a ,x , ，y “ y z a a 八y 2且: = x ,a ,几y 2 ，w= y z a 2 a x i并 记 作( x , 力- ( z , w ) o 剪 接 规 则; 决 定 了 切 割的 位点 和 位 置 : 第 一 项 在a ， 和a , 之 间， 第二 项 在a 2 和几之间。 当 然位点a ,戏和a , 几会 分别 在x 和y 中 出 现多 次， 位 点 的 选 择 也 是 不 确定 的 。 因 此， 对x 和， 的 剪 接 结 果 就 形 成了 令 , w ) 的 一 个 集 合 。 给 定 一 个 字 符 串 集a ,a 二 艺 ， 其 中 艺 是 字 符 集 艺上 由 连 接 操 作 生 成 的 字符串集合，所生成的语言由如下方法得到的串组成:从公理集a开始，在a 和 已 获得的串 上重复使 用剪接规则。 通常剪接x 和y 得到: 和、 后， 仍可以 将x 和y 当 作剪接项，同时，对新生成的z 和w 也没有数量上的限制。至此，可以给出剪接 系 统 的 一 个 简 洁 而 又 严 格 的 数 学 定 义 : 剪 接 系 统 是 一 个 四 元 组 ; 一 ( 艺 ， t , a , r ) ， 其 中 艺是 一 个 字 符 集 ， t 二 艺是 终 结 字 符 集 ， a 是 艺 上 的 多 重 集 ， * 是 剪接规则的集合。 1 9 8 7 年， t o m h e a d 引入了剪接系统的概念， 并利用形式语言理论分析了d n a 分 子 重 组 模型的 生 成能 力 5 4 ,7 3 1 . 1 9 9 2年， 他又 利用 形 式 语言 技术( l in d e n m a y e r 系 统) 给出 了 生 物分 子 计算的 抽象 模型一 剪 接模 型 15 i a h e a d 的 剪接 模型 是 将d n a 链表示成一个有穷字母表的串，并且将对这些串的编辑操作集合指定为诸如切割 和追加的d n a重组操作模型。之后， 有关剪接系统大部分工作重点还是试验技 术 基 础 上的 形 式 语言 理 论。1 9 9 6 年， e .c s u h a j - v a rj u , l .f r e u n d , l .k a r i , g h .p a u n 在 夏威夷举行的第一届生物计算讨论会上做了 剪接基础上的d n a计算的报告 15 8 1 。 同 年， g h .p a u n 和a .s a l o m a a .从 递归 可列 语言 族 的 特点出 发， 进一 步 论 证了一， 一- 一-一川 一 一一一一， 一一.-一一一卜 一一 7华 中 科 技 大 学 博 士 学 位 论 文基 于 剪 接 运 算 基 础上d n a 计 算的 可 能 性 159 】 。 1 9 9 9 年 ， r 万 re un d ， l kari 和g p 汕论 述了 剪 接 系 统 上 的dna计 算 ， 并 证 明 了 通 用d na 计 算 机 的 存 在 性 160 。 2 o 01年， 丫b e nens on等人通过剪接系统模型构造了 一台可编程的有穷自 动机， 这充分说明了剪接系统是计算完备的， 也就是说每个pas c a l 程序都可以 通过合适的剪接系统来模拟，反之亦然。另外， 他还证明了通用剪接系统的存在性，即剪接操作基础上的 通用可编程的d n a计算机的存在性【25。 到目 前为止， 剪接系统的 研究 主要集中在它所产生的形式语言性质( 如封闭性) 及其与乔姆斯基文法体系中其它形式语言族之间的关系 154一73 一781。 在文献仁 6 6中， k 如n e rk利用剪接系统的高度并行性，将布尔电路作为剪接系统的词进行模拟，在有穷的时间内得到了布尔 电路的值。 3 . 插入一 删除 系统 ( i n s e rt io u 一 d e l e h o n s y s te m ) 16 7 72 ，7 8 ， 5 0 1 9 96年， k ari和t hi e rr l n 引入了 插入一删除系统的定义168 。 它是建立在上下文插入和上下文删除基础上的d n a计算抽象模型，其中上下文插入和上下文删 除都可以在实验室用分子生物标准技术来实现。插入一删除系统是一个五元组id 一 区， t ， a ， 1 ， 句 ， 其 中 艺是 一 个 字 符 集 ， : 是 id的 终 结 字 符 集 ， ， 是 公 理 集 ， 1 是插入规则集，d是删除规则集。 1 9 98年， q p 五 un利用 上 下 文 插入 文 法刻画了 递归 可 列 语言 169 。 19 99年， l k an，g h . p 如 n ， g thie 币n 和5 .yu.利用建立在插入一 删除系统基础上的递归可列语言 的特征， 研究了形式语言和d n a计算的交叉性。 他们证明了 单个字母的 插入一 删除系统是计算完备的， 并且存在通用的插入一 删除系统170 。 2 0 0 2 年， 在日 本札幌市举行的 第8届国际d n a计算机会议上， a.1 a k ahar a. 阐述了 插入一 删除系统的计算能力汇7 ， 。 4 . d n a 等 量 检测模 型( d n a e q u a l ityc h e c 址 n g ) 17 2 7 3 1 yoko m o