（控制理论与控制工程专业论文）离散数学中np完全问题的dna计算.pdf

摘要 摘要 从1 9 9 4 年至今，d n a 计算已成为数学、生物学、化学、计算机科学等领域 的一个研究热点，并解决了很多n p 一完全问题。如何减少编码量大的问题，即 解决“指数爆炸”问题，是d n a 计算面临诸多困难和主要技术问题之一。这就 需要我们对已有的算法进行改进或寻找新的算法。目前，d n a 计算在计算原理 可行性的论证上比较成熟，对于表面技术的研究还处在探索阶段，随着表面技术 的日益成熟，d n a 计算将会从理论走向实践。 离散数学是数学的一个分支，离散数学中有诸多的n p 一完全问题，如：求 主范式问题，图着色问题，求传递闭包问题，最大匹配问题，旅行商问题等等。 目前，d n a 计算是解决n p 一一完全问题最有效的方法，本文采用d n a 计算解决了 离散数学中具有代表性的三个难计算问题：命题逻辑中“求主范式问题”；图论中 “图着色问题 ；集合论中“求传递闭包问题 。 本文首先介绍了d n a 计算背景、现状、原理与基本模型。然后，解决了离 散数学中上述的三个问题。第一，根据d n a 发夹结构的突出优点，即不需要特 殊的生物操作，这样从很大程度上减少了生物反应时间，并且根据主范式的定义 与d n a 发夹结构的定义知，完全可利用d n a 发夹结构模型，求解离散数学中 命题公式的主范式；第二，利用d n a 计算机模型，采取合理编码使得解空间的 生成基于三进制，并采取逐步产生满足定义的d n a 链的方法，将离散数学中图 3 一着色问题的d n a 分子链数由0 ( 3 ”) 减少到了0 ( 2 ”) ，这样很好地解决了图 3 着色问题中的“指数爆炸问题，并给出了其应用；第三，利用a d l e m a n 试 管模型，借鉴h a m i l t o n 路径问题的思想，求解了难计算的传递闭包问题。 最后，总结了全文，讨论d n a 计算与数学的密切关系及其在数学领域内的 应用，并讨论了进一步的研究方向。 关键词：d n a 计算；可满足性问题；主范式；图着色；传递闭包 摘要 a b s t r a c t d n a c o m p u t i n gh a sb e e nat o u c h yp o i n tf o rr e s e a r c hi nm a t h e m a t i c s ，b i o l o g y , c h e m i s t y , a n dc o m p u t e rs c i e n c ef r o m19 9 4t op r e s e n td a y s i th a ss o l v e dm a n y p r o b l e m ss u c ha sn pc o m p l e t ep r o b l e m o n eo fm a n yd i f f i c u l t i e sa n dm a i nt e c h n o l o g y t h a td n a c o m p u t i n gf a c e si sh o w t or e d u c et h el a r g ec o d i n gq u a n t i t y , n a m e l y , t os l o v e i n d e xe x p l o s i o n p r o b l e m a sar e s u l t ，w es h o u l di m p r o v et h ee x i s t i n gc o m p u t i n g m e t h o d so rf i n do u tn e wc o m p u t i n gw a y s a tp r e s e n t ，d n ac o m p u t i n gi sd e m e n s t r a t e d r e l a t i v e l ym u t u r e l yi nc o m p u t i n gt h e o r yf e a s i b i l i t ya n di s s t i l le x p l o r i n gs u r f a c e t e c h n o l o g y a st h es u r f a c et h n o l o g yc o m e st om a t u r e ，d n ac o m p u t i n gs u r e l yt e n d st o t r a n s f e rf r o ml a b o r o t a r yt om a r k e t d i s c r e t em a t h e m a t i c sc o n s i s t so fs om a n yn pc o m p l e t ep r o b l e m s t h e ya r e p r i n c i p a ln o r m a lf o r mp r o b l e m ，g r a p hc o l o r i n gp r o b l e m ，t r a n s i t i v ec l o s u r ep r o b l e m ， m a x i m u mm a t c h i n gp r o b l e m ，a n dt r a v e lq u o t i e n t n o w a d a y s ，d n ac o m p u t i n gi st h e m o s te f f e t i v em e t h o df o rs o l v i n gn pc o m p l e t ep r o b l e m s t h i sp a p e rs o l v e st h r e e t y p i c a lp r o b l e m si nd i s c r e t em a t h e m a t i c sb ym e a n so fd n ac o m p u t i n g t h e ya r e p r i n c i p a ln o r m a lf o r mp r o b l e mi np r o p o s i t i o n a ll o g i c ，g r a p hc o l o r i n gp r o b l e mi ng r a p h t h e o r y , a n dt r a n s i t i v ec l o s u r ep r o b l e mi ns e tt h e o r y t h i sa r t i c l ei n t r o d u c e st h eb a c k g r o u n do fd n a c o m p u t e r i n g ，c u r r e n ts i t u a t i o n , p r i n c i p l ea n db a s i cm o d e la tf i r s t a n dt h e n ，i ts o l v e st h r e ec o r r e s p o n d i n gp r o b l e m s f i r s t l y , a st y p i c a la d v a n t a g eo fd n ah a i r p i ns t r u c t u r ei st h a tw ed on o tn e e ds p e c i a l b i o l o g i c a lo p e r a t i o n , w ec a nr e d u c eb i o l o g i c a lr e a c t i o nt i m ea tag r e a td e g r e e a n d a c c o r d i n gt ot h ed e f i n i t i o no fp r i n c i p a ln o r m a lf o r ma n dd n ah a i r p i ns t r u c t u r e ，w ec a n s o l v ep r i n c i p a ln o r m a lf o r mo f p r o p o s i t i o n a lf o r m u l ai nd e c r e t em a t h e m a t i c sb ym e a n s o fd n ah a i r p i ns t r u c t u r em o d e l s e c o n d l y , b ym e a n so fd n ac o m p u t e rm o d e l ， a d o p t i n gr e a s o n a b l ec o d i n gt op r o d u c es o l u t i o ns p a c eb a s e d o nt e r n a r yn o t i o n ，a n db y g r a d u a l l yu s i n gt h em e t h o dt h a tm e e t st h ed e f i n i t i o no fd n ac h a i n , w ec a nr e d u c e a m o u n to ft h ed n am o l e c u l ec h a i n sf r o mo ( 3 ”) t oo ( 2 4 ) i ng r a p h3c o l o r i n g p r o b l e m t h i sw a yc a nw o n d e r f u l l ys o l v e i n d e xe x p l o s i o n p r o b l e mi ng r a p h3 c o l o r i n gp r o b l e ma n dm a k ei t i n t oa p p l i c a t i o n t h i r d l y , b ym a k eu s i n go fa d l e m a n s t e s tt u b em o d e l ，c o n s u l t i n gh a m i l t o n sr o u t i n gp r o b l e mt h e o r y , t h i sp a p e rs o l v e s t r a n s i t i v ec l o s u r ep r o b l e mt h a ti sh a r dt od e a lw i t h i i 摘要 t os u mu p ，t h ep a p e rt a l k sa b o u tt h ec l o s er e l a t i o nb e t w e e nd n a c o m p u t i n ga n d m a t h e m a t i c sa sw e l la si t sa p p l i c a t i o ni nm a t h e m a t i c sf i e l d ；i ta l s od i s c u s s e si t sf u r t h e r r e s e a r c hd i r e c t i o n k e y w o r d s - d n ac o m p u t i n g , s a t i s f i a b i l i t yp r o b l e m ，p r i n c i p a ln o r m a lf o r m ，g r a p h c o l o r i n g , t r a n s i t i v ec l o s u r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方以外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得塞 邀堡王太堂或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：l 垒垫耋日期：兰翌年j 月e l 学位论文版权使用授权书 本学位论文作者完全了解塞邀理王太堂有保留、使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于 塞邀堡王太堂。学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权安徽理工大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解 密后适用本授权书) 学位论文作者签名：伍狙云签字日期：砰石月j 日 撇各似k 样魄彳乡昕 引言 引言 目前，计算困难问题最为流行的一种新方法就是d n a 计算，这种计算随着问 题规模的增大可以呈指数增长。d n a 计算的基本思想是：利用d n a 特殊的双螺 旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成d n a 分子链， 在生物酶的作用下，生成各种数据池，然后按照特定的规则将原始问题的数据运 算高度并行地映射成d n a 分子链的可控的生化过程。最后，利用分子生物技术 如聚合链反应p c r 、超声波降解、亲和层析、克隆、诱变、分子纯化、电泳、磁 珠分离等，检测所需要的运算结果。d n a 计算的核心问题是将经过编码后的d n a 链作为输入，在试管内或其它载体上经过一定时间完成可以控制的生物化学反应， 并以此来完成运算，使得从反应后的产物中能得到全部的解空间。现在许多研究 成果已经成功地提高了这种计算的性能，并增加了它的可行性。由于核苷酸杂交 的高度并行性，使得学者们对d n a 计算机产生了极大的兴趣。自从1 9 9 4 年，美 国a d l e m a n 博士首次开创性地在试管中用d n a 分子解决了一个7 个顶点有向图 h a m i l t o n 路径问题以来，国内外诸多学者用d n a 计算解决很多困难问题，尤其是 n p 完全问题。在过去的几年里，新的分子计算方法的不断产生，使我们对d n a 生物分子计算充满渴望与期待。 第1 章绪论 1 1d n a 计算产生的背景 1 绪论 1 9 4 6 年，世界上第一台数字电子计算机e n i a c 在美国的宾夕法尼亚大学诞 生。从此，电子计算机经历了从电子管、晶体管、集成电路到超大规模集成电路 四个发展阶段。和第一代电子管计算机相比，电子计算机的价格性能比和体积性 能比已经提高了成千上万倍。而且每过1 8 个月，计算机芯片的速度就将提高一倍， 尺寸减小一倍。但是，量子理论已经揭示出计算机芯片制造的物理极限正日益临 近。按照目前的发展速度，有人预言2 0 1 0 年芯片制造技术将达到极限尺寸0 0 8 微米。由于受经典计算机”串行”运作方式的限制，它也只能在复杂度为0 ( n c ) ( c 为常数，即解决问题的步骤与数据位数n 的c 次方成正比范围内解决问题，而对 复杂度为指数类型的o ( e x p ( n ) ) 及其以上的问题却束手无策。1 9 5 3 年美国生物学 家沃森和英国化学家克里克发现了d n a 双螺旋结构。1 9 5 4 年俄国籍的美国物理 学家伽莫夫提出核苷酸三联体的遗传密码。1 9 5 8 年克里克提出了遗传信息传递从 d n a 到r n a 再到蛋白质的中心法则。1 9 6 1 年法国生物学家雅各布和莫诺提出了 基因的功能分类和调节基因的概念。1 9 9 4 年，美国a d l e m a n 博士首次开创性地在 试管中用d n a 分子解决了一个7 个顶点有向图h a m i l t o n 路径问题( 如图1 ) 。 v v o u t 图17 个项点的有向图 f i g u r e1o r i e n t e dg r a p hw i t h7p e a k s 什么是h a m i l t o n 路径问题? 一个具有指定顶点v 加和的有向图，当且仅当 存在一个始于，终于可相容的单向边缘序列e 。，e ：，气，且进入每一个其它 顶点只有一次，则有一条h a m i l t o n 路径。 解此问题的非确定性的算法如下：( 1 ) 生成所有的有向路径。( 2 ) 保留所有 2 第1 章绪论 开始于起点v 加，结束于终点的有向路径。 ( 3 ) 保留经过图的每个顶点且每 个顶点只经过1 次的有向h a m i l t o n 路。( 4 ) 若有任何路径保留下来，则存在 h a m i l t o n 路；否则，不存在。 a d l e m a n 实验的第一步，先将图中每一顶点编码成一个随机的2 0 个核苷酸的 d n a 即2 0 个字母链。然后，对每一个有向的边缘线，建立d n a 序列，它由源 顶点编码序列的后一半和目标顶点编码序列的头一半组成。节点和边缘线的编码 方法如图2 所示。图中o l0 ：，0 。表示顶点，0 h 表示边缘线。利用顶点的补作 为中介，相应的相容边缘线的d n a 序列就连接起来。 0 2t a t c g g a t c q 疆丛幽卫丛 o ，匪亟亟亟亟亘巫圃 0 4g 簋型螋g 坠c c a g c a t g c t a d ：弓盟趔殴鳗缒亟煎区园 0 3 - 4 塑匹型丛垡鎏坐硷g 趟送适篮 d 3 c g a t a a g c t a g a a t r t c g a t 0 2 - 3 0 3 4 g t a t a t c c g a j g 。c 。1 。t 。a 。t 。i 。 。c 。g 。a 。g 。c 。t 。r 。a 。a 。a 。g 。c 。1 。t 。a 。j l g g c t a g g c u a l aa 讯：l a i aa i l l - l u u a l 。 q 图2 顶点和边的编码 f i g u r e2c o d i n go f p e a ka n ds i d e 由图2 可见0 2 ，0 3 ，0 4 都由2 0 个字符组成，0 2 3 和0 3 - 4 分别由0 2 的后一半和0 3 的前一半0 ，的后一半和0 。的前一半的字符串组成。路径d ：一，和0 3 - 4 所形成的连 接，其中间2 0 个字符串正好是以补。在适当的温度下，w a t s o n - c r i c k 补很容易 产生。因此，可用0 i 方便的构成路径0 h 和0 h 的连接。接合反应是a d l e m a n 实验 的重要阶段，它形成了图中随机路径编码的d n a 分子。 第二步，通过聚合酶链式反应( p o l y m e r a s ec h i n ar e a c t i o n , p c r ) ，将s t e p l 产生的结果繁衍扩充。而且，通过适当的酶操作，使得只有那些使于终于编 码的路径获得扩充。 第三步，利用凝胶电泳的技术，使得d n a 链按长度分离，由重复使用亲和 净化( a f f i n i t yp u r i f i c a t i o n ) 过程来实现。这个过程允许将包含一个给定子序列( 对 图中一个顶点的编码) 的单链从反应器中过滤出来。对n 个顶点依次过滤，即可 3 第1 章绪论 达到目的。 第四步，检查编码成h a m i l t o n 路径的d n a 分子是否存在。 a d d m a n 的研究结果，不仅给出一个数学问题的解，而且所解的问题是一个 困难的计算问题( n p - 完全问题) 。这就引起了数学、物理、化学以及生物界科学 家们的广泛关注，也开辟了d n a 计算这一崭新的研究领域。随后，来自各国的 2 0 0 多位有关专家探讨了d n a 计算乃至d n a 计算机的可行性，认为基因工程的 发展为d n a 计算及d n a 计算机提供了技术上的保证，人们将有能力按照实际需 要，组装成各种d n a 计算机。h d n a 计算机研制成功，其运算能力是传统计算 机望尘莫及的。d n a 计算机的出现有望成为人类科学史上的一个新的里程碑，它 有望解决当今在电子计算机上无法解决的许多问题，如密码破译、困难的n p 一 完全问题以及当今工程领域中的最大的难题一局部极小值问题等。此外，d n a 计 算的研究成果也会大大促进了数学、计算机科学和生物学相互结合与发展。 d n a 计算机有如下突出优点： ( 1 ) 高度并行性，参加生化反应的每一个d n a 分子都相当于一个纳米级处 理器，在目前技术条件下，常规生化试验所能处理的d n a 分子的数目很大，即 使考虑到单个生化反应操作的时间延迟，其计算速度也将比现有的超级计算机快 至少上千倍。 ( 2 ) 存储容量大，组成d n a 分子的4 个碱基的平均长度仅为0 3 5 n m ，按每 条d n a 链为1 0 0 0 b p 计算，其长度也仅有3 5 0 n m 。大约几十克d n a 分子就可以 存储目前全世界所有的信息。 ( 3 ) 耗能低，据估计，电子计算机每焦耳耗能可执行1 0 9 次操作，而相同的 能量可以完成2 x 1 0 4 1 个d n a 连接反应。 ( 4 ) 抗电磁干扰能力强，因为分子信息通路不靠电信号控制逻辑开关，所以 不受电磁干扰的影响，并且具有生物分子固有的自我修复能力，可靠性高。 1 2d n a 计算的研究现状 国际上，d n a 计算机的研究已经很“热 。美国、加拿大、英国、波兰、德 国、以色列等国家的著名研究机构和大学都相继开展了这一领域的研究工作，其 中包括s o u t h e r nc a l i f o r n i au n i v e r s i t y , c a l i f o r n i ai n s t i t u t eo ft e c h n o l o g y , w i s c o n s i n u n i v e r s i t y , d u k eu n i v e r s i t y , p r i n c e t o nu n i v e r s i t y , m i t , l i v e r p o o lu n i v e r s i t y , w a r s a w u n i v e r s i t y , t o k y ou n i v e r s i t y , m e m p h i su n i v e r s i t y 等。国内在此方面的研究工作也已 经展开，主要研究基地是华中科技大学许进教授领导的d n a 计算和分子计算机 4 第1 章绪论 研究所。下面对国内外研究的现状作一个简要的介绍。 1 9 9 4 年，美国a d l e m a n 博士首次开创性地在试管中用d n a 分子解决了一个 7 个顶点有向图h a m i l t o n 路径问题。a d l e m a n 的工作表明了采用d n a 进行特定 目的计算的可行性。它的新颖性不仅仅在于算法，也不仅仅在于速度，而在于采 用迄今为止还没有作为计算机硬件的生物工业技术来实现，并且开发了生物酶自 身潜在的“运算能力。最近也有学者开始将d n a 计算与遗传算法、神经网络、 模糊系统和混沌系统等智能计算方法相结合。目前，关于d n a 计算与d n a 计算 机的研究发展速度非常惊人，无论在理论研究上，还是实验方式的研究上都取得 了很大的进展。 1 9 9 5 年p r i n c e t o n 大学的l i p t o n 他在a d l e m a n 思想的启发下，通过构造一个 接触网络图g ，将s a t 问题的的解空间映射为通过接触网络图g 的始点a 和终点 b 的所有哈密尔顿路，然后对有向图中的顶点和边进行编码，其方法与a d l e m a n 的方法基本相同。 l i p t o n 给出下面一个简单的s a t 问题： ( 工lv x 2 ) ( v x 2 ) 其中而和而分别为布尔变量x i 和的而补。即五= 1 当且仅当暑= 0 。首先将该问 题对应于一个接触网络图，然后对图的顶点及有向边采用和a d l e m a n 相同的方法 进行编码，即顶点和边均用长度为2 0 核苷酸片断表示，对任一顶点f 用p ；口；表示， p ，和g ，分别为顶点的f 前1 0 个碱基和后1 0 个碱基构成的核苷酸片断；对任一有 向边f 专，用q ；p ，表示。将编码顶点和边的核苷酸片断放入初始试管t o ，经过充 分反应后就会形成代表图中的各种有向路的核苷酸片断。然后以p 嘶和p 如为引物 搜索出试管t o 中以a 。开始，以a ，结尾的有向路。再从试管t 0 中搜索出第一位为 1 ( 而= 1 ) 的核苷酸片断并放入试管t 中，剩下的放入试管t ：中；然后再从试管t ：中 搜索出第二位为l ( 而= 1 ) 的d n a 分子放入试管t ，中，将试管t 和t ，合并为t ，得 到满足第一个子句的核苷酸片断。从试管t ，中搜索出第一位为o ( 五= 0 ) 的核苷酸 片断，并放入试管t 。中，剩下的放入试管t ：中；然后再从试管中t ：搜索出第二位为 0 ( x 2 = 0 ) 的d n a 分子放入试管t s 中；将试管f 。和t ，合并为t 6 ，得到满足第二个子 句的核苷酸片断。最后检查试管t 。，如果有核苷酸片断，说明该问题是可满足的； 否则，该问题是不可满足的。 1 9 9 7 年，o u y a n g 等利用d n a 计算解决了另一个n p 一完全问题，图的最 大团问题。设g 是一个图，v ( g ) ，e ( g ) 分别表示图g 的顶点集和边集，s 是g 的一个顶点子集，如果s 的导出子图g s 】，我们称g s 】是g 的一个团。令h 是 5 第1 章绪论 g 的团，若对于任意g 的团h t ，有i v ( 日) l i v ( h ) l ，则称h 是g 的最大团。o u y a n g 利用一种巧妙的编码方法给出了利用d n a 计算求解图的最大团。他们的主要思 想是：首先把n 个顶点的图，每一个可能的团用一个n 位二进制数来表示。若 某一位的取值为1 ，表示该顶点在所求的团中，若某一位的取值为0 ，表示相应 的顶点不在团中。这样，把n 个顶点的图中所有可能的团的集合映射成了所有可 能的n 位二进制数的集合，称它为完全数据池。然后找出图中没有被边连接的点 对，利用图中的团在其图的补图中对应的是空图这一简单的结论可知补图中相邻 的两顶点在原图中是不相邻的，因此，它们不可能是同一团中的顶点。这意味 着相应的两个数位上的数字不可能都是1 。于是从完全数据池中剔除所有在补图 中有一条边相连的顶点对应的数字。最后将剩余的数据池分类，以找出含数字l 最多的数据，这些数据中的每个l 代表相应团中的一顶点。因此，元素1 的个数 最多的就是图的最大团，并且元素1 的个数就是最大团所含的顶点数。 1 9 9 8 年第一本关于d n a 计算机的学术专著“d n ac o m p u t i n g n e w c o m p u t i n gp a r a d i g m s 一书已由德国的s p r i n g e r 出版社出版问世。 2 0 0 0 年，w i s c o n s i n 大学的“u 等在n a t u r e 上发表了一篇文章，介绍了一种 表面方式的s a t 问题的d n a 计算模型。 2 0 0 1 年1 1 月，以色列的w e i z m a n n 研究所的s h a p i r o 研制出由d n a 分子和 酶分子构成的生物计算机，它实质上是一种半自动化的可编程的有穷自动机。 2 0 0 2 年2 月，s u y a m a 等研制出一台用于基因表达分析的d n a 计算机，它主 要由二部分组成：分子计算组件和检测部分组成；前者通过生化反应，筛选出正 确的结果，后者对所得到的结果进行分析。 期间许多作者给出了不同类型的图与组合优化问题的d n a 计算方法与结果， 如l i p t o n 给出了连接网络、电路及最大电路以及正规电路等的可满足性问题； 质粒d n a 分子是一种环状的超螺旋结构，h e a d 提出了用质粒d n a 分子来解决 可满足性问题；高琳，马润年，许进h 利用质粒d n a 分子结构给出了图的最大 匹配问题的d n a 计算模型；张连珍，许进幅给出了一种基于环状质粒d n a 计 算的新方法，这种计算质粒包含一个特殊的插入d n a 序列片断，每个片断定位 在匹配的限制性内切位点，通过剪切和粘贴实现计算过程，并讨论了0 - 1 背包问 题的质粒d n a 计算模型算法。c u k r a s 等人用r n a 代替d n a 给出了可满足性问 题一种实验性的计算模型，并讨论国际象棋问题的r n a 计算模型。 在目前这个探索阶段，国内d n a 计算方面主要还是一些介绍d n a 计算方 面的综述性的报道，利用d n a 计算解决实际问题方面的研究不多。许进和张雷 6 第1 章绪论 在“d n a 计算机原理、进展及难点( i ) ：生物计算系统及其在图论中的应用 文 章中讨论了d n a 计算模型在图与组合优化中的研究进展，提出生物计算系统的 理论体系。d n a 计算机还存在以下一些主要技术问题，需要研究者们去解决。 以下就d n a 计算面临的困难作一简要介绍。 1 3d n a 计算的应用领域和发展方向 d n a 计算当前主要集中在以下几方面： 1 d n a 计算当前己用于一些难的数学问题和某些n p 一完全问题，如 h a m i l t o n 路径、旅行商、可满足性问题、三色问题。 2 数据加密与解密。这是超级计算机应用的一个重要领域，美国的研究者提 出了用d n a 计算机破译数据加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 的方案。这 标准加密的信息，是众多密钥中的一个。d n a 计算机可以同时试验所有的密 钥，并找到正确的一个。预计，对于一个高度自动化的d n a 计算机，解决这个 问题只需2 个小时。 3 智能控制。利用生物d n a 和人工d n a 机制已开发出一种d n a 编码方法。 这种方法具有冗余和重叠的基因，可以选择输入变量和调节隶属函数。并在人工 d n a 中可应用病毒和酶操作，获取到有效的模糊规则。此外，d n a 序列己用于 神经网络的建模与学习，并大大简化了该网络的参数数目。 4 生物化学、组合化学和医学等。d n a 计算能促进和指导生物化学获得更规 则、灵活和可靠的操作和技术，并产生出可应用的具有特定性能的分子或“酶 飞o 5 布尔电路和数据流逻辑运算的仿真和实现。这对构作未来d n a 计算机有 重要意义。 随着生物技术和d n a 计算水平的不断提高，d n a 计算必将在更广泛的领域 中为人们所认识和应用，并正在向下列方面渗透和扩展。 1 继续探索其它新的d n a 计算及模型。 2 研究d n a 计算的复杂性、生物复杂性和可实现性的衡量尺度。 3 探索一种分子高级语言所必须的基本生物操作。操作必须易于实现，易于 自动化，易于消除或减少差错。优化完成操作的分子过程。 4 开发适合于分子生物计算新的问题求解工具和程序。构作基于d n a 求解 问题的装置并使之自动化。研究未来d n a 计算机的可行性。 5 研究d n a 计算与各种软科学的结合和集成。探索d n a 计算在工程和智能 7 第1 章绪论 控制中的应用。 6 开发可利用的各种d n a 芯片。以用于计算机、半导体和光化学合成等微 加工技术。 1 4d n a 计算面临的困难 目前d n a 计算面临诸多困难和主要技术问题，主要有以下几个方面： 1 存在运行上的障碍。极大规模操作的困难及复制过程中的错误。例如，以 处理h a m i l t o n 路径问题为例，当计算量增加时，出现错误的几率也越来与越大。 第一步，可能会偶尔出现代表两条不相邻向量的核苷酸被连在了一起，从而一些 代表着图中根本没有出现的“假路径 的核苷酸链。虽然这些不该有的核苷酸链 可能在第二步被扩充，又可能经过了第三步，但也许躲不过第四步的分离。无论 如何，计算结束时必须审慎地确定图中是否的确包含着h a m i l t o n 路径。在分离 第一步，编码着h a m i l t o n 路径的分子有可能没有被结合上而丢失掉，而代表“假 h a m i l t o n 路径的分子却有可能靠非特异性吸附而被保留了。当然，通过更合理 的设计和更高层次上应用这一技术可以解决大部分的问题，比如后一个问题通过 更严格的多次分离步骤来解决，前一个问题则通过在p c r 阔增中采用设计好的阔 增h a m i l t o n 路径的引物来避免。但总而言之，设计方案( 算法) 和生物技术能够 达到的层次还限制着d n a 计算机的实际运行。 2 存在逻辑上的障碍。即分子计算机所要解决的多面性及其对大量不同种类 计算问题的容纳性问题。电子计算机，也就是传统的无线计算机，它的一个最大 优点就是其所提供的大量丰富的操作和它在不同应用中表现出的灵活性。它可以 迅速地作出两个一百位整数的乘积，面对于分子计算机，就目前的方法和现有的 酶，恐怕是件很难处理的事。着眼于这些问题，d n a 计算这种大量低成本的操作 是否的确能够独立用于实际的计算问题中，目前还存在着一些争议。 3 在构造的现实性及计算潜力方面。d n a 计算机的核心思想在于将经过编码 后的d n a 链作为输入，在试管内经过一定时间控制的生化反应，以此完成运算。 反应的产物及溶液给出了全部的解空间。但是最优解怎样与其他解分离，怎样输 出，这是一个技术性极强的问题。尽管现代分子生物学提供了p c r 、高效电泳、 亲和层析等选择以及放大纯化技术，但所消耗的时间和空间复杂性远比在此前所 进行的反应过程复杂得多。特别是随着求解问题规模的增大，“输出技术瓶颈可 能成为d n a 计算机实现的主要障碍。有人甚至断言：当n 3 0 ，由于消耗、实验 室规模、实验错误、反应时间等原因，计算哈密尔顿这类问题似乎是不可能的， 8 第1 章绪论 其主要的原因是，随着问题复杂性的增加，计算所需要的核坩酸及酶的分子数成 指数增加。 4 运算过程中错误发生与传播。p c r 阔增是一种循环过程。耐热聚合酶有效 高的碱基错配率。理论上讲，每次p c r 循环中不仅前一循环后已带有错误碱基的 拷贝数量会增加，而且还会产生新的错误拷贝。随着循环次数的增加，d n a 双链 中不含任何错误碱基的拷贝比例在产物中会越来越少，另外，由于热力学和动力 学的原因把大量的d n a 链放在一起通过几百个过程步骤，偶尔会有一些非酶的 非受控制的支路反应发生，甚至包括d n a 链的动力分解。这样的错误会导致一 些“伪解”出现，并在整个解空间中传播，那么系统结构及程式中就必须有相应 的程序来纠错，这样就增大了最优解输出的难度。 5 人机界面。对于各种计算问题，怎样寻找一种直接的翻译方式，变换成d n a 计算系统，也即d n a 生物化学反应的运算途径，以至鉴别和输出最优解技术路 线，使得d n a 计算机适应广阔的问题面，并具有实用性。从目前来看，d n a 计 算机与传统计算机并不是决然隔离的，要构成良好的人机界面( 甚至包括d n a 生化反应运算过程) 和最优解输出过程的自动化控制都离不开传统计算机。所以 也有人认为，d n a 计算机至多只能起到一个运算器的作用，即使如此，我们认为 这种传统计算机与d n a 计算机互补所获得的计算也将产生巨大影响。 9 第2 章d n a 计算原理与操作 2d n a 计算原理与操作 2 1d n a 的计算原理 2 1 1d n a 的分子结构 沃森和克里克共同提出了d n a 分子的双螺旋结构，它是一种由脱氧核苷酸 组成的高分子化合物。每个脱氧核苷酸是由一分子磷酸，一分子脱氧核糖和一分 子含氮碱基组成。其中含氮碱基有4 种分别是腺嘌呤( a d e n i n e ) 简写a ，鸟嘌呤 ( g u a n i n e ) 简写g ，胞嘧啶( c y t o s i o n e ) 简写c ，胸腺嘧啶( t h y m i n e ) 简写t 。d n a 不仅具有一定的化学组成，还具有规则的双螺旋结构。这一结构的主要特点是： ( 1 ) d n a 分子是由两条平行的脱氧核苷酸长链盘旋而成。 ( 2 ) d n a 分子中的脱氧核糖和磷酸交替连接，排列在外侧。 ( 3 ) 两条链上的碱基通过氢碱连接起来，形成碱基对。 碱基互配对( w a s t o n c r i c k ) 原则是嘌呤配嘧啶，并且a 与t 配对，g 与c 配对。由于碱基对具有多种不同的排列顺序，这就构成了d n a 分子的多样性。 d n a 链有极性，它的两端是不同的，一条d n a 序列的两端分别记为3 和5 ，这 样就可以实现a t 、g c 之间的严格配对关系，利用这种配对关系，可组成互 补配对的d n a 双螺旋链，并导致d n a 分子具有自我变性与复制的功能。其中变 性指的是d n a 双链在一定的温度下解为两条d n a 单链，而复制指的是两条互补 的d n a 单链在一定的温度下结为一条d n a 双链。如果一条d n a 链所含的碱基 数目较少，则可称这条链为寡核苷酸。以下就是由碱基互配对组成的四条寡核苷 酸，以及这四条寡核苷酸变性与复制的实例。其中一条d n a 单链为 5 - t a g t c c g t - 3 ，则其互补链为3 一a t c g g c a - 5 ，由这两条互补的d n a 单链组成的d n a 双链为： 57 一刚g 脱粥一3 3 一a t c g g c 4 5 7 另一条d n a 单链为5 a a t t g c g 3 ，则其互补链为3 t t a a c g c 5 ，由 这两条互补的d n a 单链组成的d n a 双链为： 5 一朋阿g c g 一3 7 3 一冗翻爿c g c 一5 这样，上述的四条d n a 单链互补组成的两条d n a 双链变性与复制的过程结构图 如图3 。 1 0 塑! 主里垫堡蔓堕里兰塑堡 一一 f 留l 嚣) f ， 。龟 、 5 ，- 一 s c c - - 3 f 3 一0 3- - e 一 一e 一= 3 亨3 5 3 5 3 -5 图3d n a 分子职螺旋结构 f i g u r e3 d n a m o l e c u l e d o u b k h e l i xg h u c 2 12d n a 计算的数学模型 从数学上讲，一个d n a 单链可看作是符号集= ( a ，g c ，t ) 组成的串，就像 电子计算机中0 和1 一样，可用4 个字母的字母表= a ，g c ，t ，并按照d n a 双螺旋结构和碱基互配对原则对问题进行编码。如可认为a = 0 ，g 。1 ，t = 0 ，c = i ， 这样( o ，6 ) ，( 1 ，i ) 为两个互补关系。如上述的d n a 双链 5 - t d g c c g t 一3 可表示为0 0 1 1 1 1 0 。按照顺序的从上下两个序列中取字符串， 3 一a t c g g c a 一5 o o 1 i o 就可以得到字符串为万0 0 石l i h f l l i 60 。d n a 串可作为译码信息，生物酶可 看作是模拟在d n a 序列上的运算。不同的生物酶相当于作用在d n a 串上不同的 算子。 2 13d n a 计算原理 d n a 算法设计解决计算问题的基本思想是：利用d n a 特殊的双螺旋结构和 碱基互补配对的原则对问题进行编码，把要运算的对象映射成d n a 分子链，在 生物酶的作用下，生成问题的可能解即初始数据池，然后按照一定的规则将原始 问题的数据运算并行地映射成d n a 分子链的可控的生化过程。最后利用现代生 物技术如聚合酶链反应p c r ，聚合重叠放大技术p o a 、超声波降解、亲和层析、 分子纯化、凝胶电泳、磁珠分离等手段获得运算结果。 汐弋。 ，r 第2 章d n a 计算原理与操作 综上所述，d n a 计算的核心问题是将经过编码后的d n a 分子链作为输入， 再对d n a 分子进行生化操作，最后对结果d n a 分子进行萃取。d n a 计算主要 包括三个步骤：( 1 ) 编码。将所要解决的原始问题映射为一个d n a 分子的集合； ( 2 ) 计算过程。在相关酶的参与下，进行各种生化反应生成可能解空间；( 3 ) d n a 分子( 即待求问题的解) 的分离和读取。d n a 计算原理的基本步骤如图4 图4d n a 计算原理图 f i g u r e4d n ac o m p u t i n gs c h e m a t i cd i a g r a m 2 2d n a 计算中常用到的酶 生物酶是一种蛋白质结构，它可看作是模拟在d n a 序列上的运算，一个特 定的运算结果的获得则是通过对d n a 序列进行一系列连续的操作来实现的。这 些操作包括：依长度分离核酸链，合并，分离，溶解，退火，扩增，切割，连接， 检测等。对d n a 序列可进行的操作必须由生物酶来完成。酶蛋白与其它蛋白质 的不同之处在于酶都具有活性中心。酶可分为四级结构：一级结构是氨基酸的排 列顺序；二级结构是肽链的平面空间构象；三级结构是肽链的立体空间构象：四 级结构是肽链以非共价键相互结合成为完整的蛋白质分子。真正起决定作用的是 酶的一级结构，它的改变将改变酶的性质( 失活或变性) 。目前应用的生物酶主要 有以下几种：h 2 0 2 分解酶、靛蓝漂白酶( d e n i l i t e ) 、果胶酶、 限制性核酸内切 酶( r e s t r i c t i o ne n d o n u c l e a s e ) 等。 常用的生物酶主要有： ( 1 ) 限制内切酶( r e s t r i c t i o ne n d o n u c l e a