（计算机软件与理论专业论文）dna计算若干问题研究.pdf

摘要 1 9 9 4 年，a d l e m a n 用操纵d n a 分子的办法解决了一个经典的n p 完全 问题一哈密顿路径问题( 一个包含7 个顶点实例) 。自此以后，生物计算作 为生物与计算机科学的交叉学村迅速的发展起来。 本文探讨了生物计算中最受关注的d n a 计算中的一些算法及编码问 题。 在第一章中，首先介绍了一些相关的预备知识；其次，对生物计算， 特别是d n a 计算的不同研究方面及状况进行了简要的总结分析，例如 d n a 计算的模型，解决n p 完全问题的算法等。 在第二章中，提m 了把参数算法应用于生物计算，以减少生物计算的 空间复杂度的思想。这一章首先给出了顶点覆盖问题的参数算 盍，和这 个参数算法用d n a 计算模型实现的方法，并且得出这个算法以非常接近 于1 的概率的输出正确结果。 本章还利f l j 独立集和顶点覆盖问题的关系，得到了在输入参数很大的 情况下，降低解决顶点覆盖问题的所需分子数目的方法。相应的，也得到 了独立集问题的生物参数算法。 在第三章中，首先给出了在粘结模型下解决带有数值参数的n p 完全问 题一划分问题的生物算法，并分析了其正确性。在此基础上，给m 了背包 问题相应的算法。本章的最后，还给出了一个可以进行连续加法运算的， 主要使用剪切和连接操作的方法。 d n a 计算的另外一个重要的问题是什么样的编码能够减少操作所需 生化反应的错误。这个问题和d n a 序列的组成有密切的关系，要减少错 中文摘要 2 误的发生，除r 反应条件，最重要的就是如何选用合适的d n a 序列作为 问题编码。 第四章首先总结了两种判定编码是否是具有良好性质的标准。除了减 少错误发生的概率，还应该考虑什么样的码能够支持d n a 计算大规模并 行性的优势。在第四章中，定义了自由码子集的概念，并分析了自由码了 集能够并行处理，且不会发生错误的原因。进步的，本章把自由码子集 的概念扩展到任意的演化上，进而根据不同的演化，把码集分为层次结 构，每层包含的都是严格演化自由码子集。本章最后还给出了利用码集的 层次结构检测d n a 序列中的码字和生成d a 序列的方法。 在第五章中，对本文的工作进行了简要的总结，并展望丫进一步的研 究内容与问题。 关键词： d n a 计算，空间复杂度，数值参数，0 自由码子集，层次结构 中图分类号：t p 3 8 4 a b s tr a c t s i n c ea d l e m a ns u c c e s s f u l l ys o l v e da ni n s t a n c eo fh a m i l t o n i a np a t hp r o b l e mw i t h7v e r t e x e s ，w h i c hi san p - c o m p l e t ep r o b l e m ，b i o m o l e c u l a rc o m p u r a t i o nh a sb e c o m ean e wr e s e a r c hf i e l dw h i c hs e t su pab r i d g eo v e rc o m p u t e r s c i e n c ea n db i o l o g y i nt h i sp a p e r ，s o m ep r o b l e m so na l g o r i t h ma n dc o d i n ga r es t u d i e dw i t h i n d n ac o m p u t i n g ，w h i c hi st h em o s tp o p u l a rs u b f i e l d o fb i o m o l e c u l a rc o i n p u t i n g i nt h ef i r s tc h a p t e r ，s o m eb a c k g r o u n di sp r e s e n t e da tf i r s t ia n dt h e na s h o r to v e r v i e wo fd i f f e r e n tr e s e a r c h e si sg i v e n ，s u c ha st h em o d e l so fd n a c o m p u t i n g ，m e t h o d st os o l v en p c o m p l e t ep r o b l e m s ，e s p e c i a l l ys a t t h ei d e at ou s ep a r a m e t e r i z e da l g o r i t h mt od e d u c et h es p a c ec o m p l e x i t y o fd n ac o m p u t i n gi sg i v e ni nt h es e c o n dc h a p t e r i nt h i sc h a p t e r ，ap r o b a - b i l i s t i cp a r a m e t e r i z e da l g o r i t h mf o rv e r t e xc o v e ri ns t i c k e rm o d e li sd e s i g n e d t h ep r o b a b i l i t yt h a tt h i sa l g o r i t h ma l w a y sr e t u r nt h ec o r r e c ta n s w e ri sc l o s e t o1 b a s e do nt h er e l a t i o n s h i pb e t w e e nv e r t e xc o v e ra n di n d e p e n d e n ts e t ，a n o t h e rm e t h o df o rv e r t e xc o v e ri sp r e s e n t e dw h i c hs t i l lc a nd e d u c et h es p a c e c o m p l e x i t yg r e a t l yi ne a s et h ep a r a m e t e rki sb i g c o n s e q u e n t l y , t h ep a r a m - e t e r i z e da l g o r i t h mf o ri n d e p e n d e n ts e tw i t h i ns t i c k e rm o d e li sd e v e l o p e d i nc h a p t e r3 ，s o m en p c o m p l e t ep r o b l e mw i t hn u m e r i c a lp a r a m e t e r s a r ed i s c u s s e d ，i n c l u d i n gp a r t i t i o na n dk n a p s a c k t h em e t h o dt os o l v es u c h 3 英文摘要 4 p r o b l e m s & r eg i v e nw i t h i ns t i c k e rm o d e l ，a n dt h ec o r r e c t n e s so ft h em e t h o d i sp r o v e d a tl a s ti nt h i sc h a p t e r ，aw a yt op e r f o r mc o n t i n u o u sa d d i t i o ni s p r e s e n t e d ，i nw h i c ht h em a i no p e r a t i o n su s e da r ec u ta n dp a s t e i nd n a c o m p u t i n g ，a n o t h e ri m p o r t a n tp r o b l e mi sw h a ta r eg o o dc o d e s t h a tw i l lh e l pt od e d u c et h ep r o b a b i l i t yt h a tm i s t a k e sh a p p e nd u r i n gt h e c h e m i c a lr e a c t i o n i nc h a p t e r4 ，t w os y s t e m sd e v e l o p e dt oe v a l u a t e “g o o dc o d e a r es h o w e d i nb r i e la n o t h e rc o d i n gp r o b l e mi st h a tw h a tk i n do fc o d es u p p o r t st h e a d v a n t a g eo fb i o m o l e c u l a rt h es t r o n ga b i l i t yo fp a r a l l e l i s m t h ec o n c e p to f f r e es u b c o d ei sd e f i n e di nt h i sc h a p t e r ，a n dt h er e & q o nw h ys u c hc o d es u i t s f o rp a r a l l e l i s ma n dw o n tm a k em i s t a k ei sa n a l y z e d f u r t h e r m o r e ，t h ec o n c e p ti se x t e n d e dt oa n yi n v o l u t i o n ，w h i c hc o n c e r n s t h es p e c i a lp r o p e r t i e so fd n a m o l e c u l a r ，a n dt h eh i e r a r c h yd e r i v e df r o ma n y i n v o l u t i o ni sg i v e n t h em e t h o du s i n gt h eh i e r a r c h yd e r i v e df r o md i f f e r e n t s t r i c t l yi n v o l u t i o nf r e es u b c o d et od e c o d ed n as e q u e n c e si sp r e s e n t e di n t h i sc h a p t e r f i n a l l y ，i nc h a p t e r5 ，as h o r ts u m m a r yo ft h i st h e s i sa n dt h ef u r t h e r 1 w o r kr e l a t e da r ep r e s e n t e d k e yw o r d s ： d n a c o m p u t i n g s p a c ec o m p l e x i t y , n u m e r i c a lp a r a m e t e r 0f r e es u b - c o d e jh i e r a r c h y c l a s s i f i c a t i o nc 0 d e - t p 3 8 4 指导小组成员 朱洪 鲁道夫 阚海斌 教授 教授 副教授 y7 6 9 6 7 5 第一章 引言 计算机的发展有着悠久的历史。中国古代的算盘和欧洲的计算尺可以 看作是早期的计算机。第一台冯诺伊曼模型计算机的问世，给计算机的发 展带来了本质的飞跃一从过去的利用机械方法进行计算，过渡到电子方法 进行计算。这种改变极大的提高了计算机的能力，计算机能够处理问题的 范围得到了极大的扩充。而且电子计算机的发展使得计算机由单纯的计算 工具变成为人们日常生活的必需品。 自从电子计算机问世以来，它的处理器运算速度的增长几乎完美的遵 从摩尔定律一以刚间的指数速度增长。但这种增长并不是无限的，而是受 电子设备本身物理性质的限制。一般认为，不久的将来，计算的速度就会 达到电予设备物理件质所能承载的极限。 在传统计算机计算速度增长空间有限的情况下，如何进一步的提高计 算机的计算能力? 人们把目光投向新的计算模式或介质，其中量子计算和 生物计算受到了众多科研工作者的关注。这两种计算模型如果能够获得成 功，都将带来计算机发展的又一次本质的飞跃。本文所讨论的是后者，生 物计算中的口以计算。 冯诺伊曼模型计算机的计算模式是一个时段进行一个操作。只有当它 完成一个任务后，才能处理新的任务。而d n a 计算的计算模式是同时处 理许多的任务。因此，一些对冯诺伊曼计算机来讲是不可能完成或是很困 难的任务，用d n a 计算可能会轻而易举的得到解决。 1 1 d n a 的结构与d n a 计算中常用的操作 2 另外，d n a 存储数据的密度也远远大十电子计算机。d n a 分子上 的一个碱基大约足0 3 5 纳米，也就是说在一平方尺的面积上，d n a 分了 可以存储的信息可以高达上百万g ，而电子计算机在相同的面积上只能存 储几个g 的信息。 d n a 分子既是存储介质，又是计算介质，d a 计算可以看作是纳 米计算机的计算。 基于d n a 计算这些“与生俱来”的特点，很多计算机或生物领域的 研究者投入到生物计算特别是d n a 计算的研究中，希望这种新的计算模 式能够从理论及实验阶段过渡到现实应片j 阶段，以发挥d n a 分了巨人的 计算潜力。 1 1 d a 的结构与d n a 计算中常用的操作 1 1 1d a 的结构 d n a 是脱氧核糖核酸( d e o x y r i b on u c l e i ca c i d ) 的简称，是广泛存于 大部分生物体细胞内部的遗传物质。它在生物体内发挥着重要的作用：作 为蛋白质的模版，它决定了生物体的蛋白质结构；另外，d n a 能够严格 以自己的序列作为模版进行复制，从而把遗传信息传到下一代细胞中。 d n a 是由一系列脱氧核苷酸组成的，不同的脱氧核苷酸包含不同的碱基 一分别是腺嘌呤( a ) ，鸟嘌呤( g ) ，胞嘧啶( c ) ，胸腺嘧啶( t ) 。 简单起见，一般用这四种碱基表示相应的脱氧核甘酸。 1 1 2w a t s o n c r i c k 互补 脱氧核苷酸组成端有极性的d n a 链，一条d n a 单链的两端分 别记为3 端$ h 5 端。如果两条d n a 单链满足3 端$ n 5 端相对应，a 与t 相 对应，c 与g 相对应，就称这两条单链是w a t s o n c r i c k ：f f 补的。w t a t s o n c r i c k 互补的两条单链可以结合成为条d n a 双链。例如5 一a c c t g c 一 3 ，和3 ，一t g g a c g 一5 7 在一定的条件下，可以组成一个双链d n a 分子 1 1 d n a 的结构与d n a 计算中常用的操作 3 5 。a c 凹g 。7 。这种碱基互补的性质，在d n a 计算中发挥着重要的作 37 一7 。g g c g 一5 用。 d n a 可能有部分是双链结构，但靠近末端的序列是草链结构，这样 的末端在满足w a t s o n c r i c k 互补的条件下，可以和其它序列或序列的末端 连接形成双链结构。这样的末端被称为粘性末端。 含有碱基数目较少的d n a 链，也称为寡核苷酸。有一些d n a 分子 两端相连，组成一个闭合的结构，这样的d n a 分子称为环状d n a 。链 状d a 分子是有两个末端的d n a 分子，还有些d a 分子出现分支， 每个分支都有一个末端，因此这些分子可能有多个末端，例如有四个分支 的d n a 分子( d x ) 3 阳有六个分支的分子( t x ) 。 1 1 3d n a 计算常用的操作 用d n a 分子进行计算是通过在其上的一系列生化反应实现的，这样 的生化反应在d n a 计算中也称作操作。卜面列举一些基本的或本文用到的 操作，更多可用的生物操作，可参见 6 1 9 2 】。 熔解( m e l t i n g ) ：在一定高温条件下，d n a 双链熔解成两条w a t s o n c r i c k 互补的单链。 退火( a n n e a l i n g ) ：它是熔解的逆过程，通过缓慢降温，熔解得到的单 链将再次结合为双链。 合成( s y r l t h e 8 i 8 ) ：生成一个长度为多项式的特定序列的d n a 链。 杂交( h y b r i d ) ：不同来源的单链互补，形成双链( 或部分双链) 结 构。 抽取( e x t r a c t ) ：提取出含有特定序列的d n a 链。 1 2 d n a 计算的模型 4 剪切( c u t ) ：在特定位置上剪切d n a 链。这个操作用到限制性酶，这 类酶可以识别特定的序列，并剪切d n a 链。 分离( s e p a r a t e ) ：把d n a 链按长度不同分类。 连接( p a s t e ) ：两个粘性末端满足w a t s o n - c r i c k 功b 的d n a 链连接成 为一个更长的d n a 链。 检测( d e t e s t ) ：检测是否含有d n a 。 合并( u n i o n ) ：合并多组d n a 的集合，得到含有所有d n a 序列的集 合。 1 2 d n a 计算的模型 早在上世纪五十年代，物理学家r i c h a r df e y n m a n 就提出了用细胞和 分子来建立微型计算机的思想 3 9 】，他提出了控制纳米数量级介质的问 题，这是人类第一次产生把计算介质的尺寸缩小到分子级的想法。 本节回顾了手要的d n a 计算的模型。在阐述这些模型的时候，用 表示字母表。 1 2 1剪接模型 1 9 8 7 年，t o mh e a d 提出了第一个用d n a 分子的特有的操作来表示 形式语言的系统一“剪接系统” 4 5 。剪接系统的核心是剪接规则。 1 2 d n a 计算的模型 5 剪接规则：一个剪接规则r 用四元组( “1 ，u 2 ；饥，v 2 ) 来表示，其中“1 ，u 2 ；v 1 和 2 都是+ 上的字。( x ，y ) 辛，( z ，叫) 当日仅当 z= = z= w= z l u l ! 2 x 2 可l l 2 1 ，2 x l u l v 2 y 2 1 l 钍2 2 2 剪接系统：一个剪接系统用四元组a = ( e ，正a ，r ) 来表示。t 是终止 字符集，a 是+ 上的多重集，r 。弗+ $ + 弗+ 是剪接规则集。 剪接系统o - 定义了多重集的一个二元关系净。假设m 和m 7 是丽个 多重集，m 号，m 7 成立，当且仅当存在x 和是多重集m 的一个元素，z 和w 是m 的元素。人们深入的研究了剪接系统，及以其为基准的其它系统 与传统模型和形式语言的关系 9 1 】 2 9 8 9 】【9 8 9 7 】 7 7 9 5 4 。这此工作不仅 发现了不同剪接系统与各种自动机或语言的关系，而且也证明了剪接模型 的能力与图灵机等价，且存在通用的剪接系统。 1 2 2插删模型 早期类似模型的研究集中于只有插入操作的系统与形式语言的关 系f 8 6 ，在生物计算成为一个专门的研究领域后，k a r l 等人提出r 基于插 入和删除操作的插删模型f 6 0 1 。这个模型包含两个操作：上下文相关的 插入和上下文相关的删除。这两个操作都是实验室内可以实现的生物操 作。插删系统的核心是插入规则和删除规则。设u 和v 是+ t r 的串， ( x ，y ) 。e 。是规则的上下文。 插入规则： 扎j 扛，1 ) = - ( u x v y u 2 ，u 1 ，“2 e 4 ，u = u l x y u 2 1 2 d n a 计算的模型 6 删除规则 札j ( 。，) v = u l x y u 2 ，u l ，u 2 4 ，u = u l x v y u 2 插入和删除操作是在符合规则的上下文中间插入或删除一段序列，以得到 新的字符串。 插删系统：一个插删系统用五元组i d = ( e ，t ，a ，i ，d ) 来表示。丁是 终止字符集，a + 是系统初始串集合，j p ”是插入 规则集合，d + p + 是删除规则集合。 同样的，也证明了些插删系统是图灵等价的。而且对各种插删系统 与不同形式语言与自动机的关系也得到较为全面的研究 6 2 5 3 7 5 9 3 。 1 2 3 等同判定模型 等同判定模型是用生物操作来模拟等同自动村l ( e q u a l i t ym a c h i n e ) ，e m 机与图灵机类似，所不同的是它除了输入带外还有两条单向的只写输出 带。判定一个输入是否被接受是根据输入带读完，进入终止状态时，两条 输出带上的内容是否相同，如果相同，就接受输入串；否则不接受。非确 定的e m 机与图灵机等价37 ，而生物计算的大规模并行性使得j f 确定性的 操作很容易在合理的时间内得以实现。1 9 9 8 年，y o k o m o r i 等设计了e m 机 的生物实现方法 1 1 6 1 ，也就是用生物操作来模拟e m 机的状态转移，最后 通过判断是否有d n a 链存在来判断e m 机的两个输出是否相等。 d n a e c 模型的优点在于和图灵机一样，它是一个简洁的计算模 型，但它所需要的一些生物操作并不容易实现。 1 2 4 禁止与强迫模型 在一般的模型里，有一种默认的规则：即没有被许可的就是被禁止 的。但这种规则很不符合生物计算可以同时进行多种尝试的特性。因此， 1 2 d n a 计算的模型 7 根据生物计算的“非确定性”，人们提出来了一种“任何没有被禁止的都 是许可的”模型 a 6 5 7 1 。这个模型主要有禁止与强迫两类规则： 强迫规则：x ，yc + 足两个有限集。二元组( x ，y ) 是强迫规则。如果一 个语言l 满足xcl 蕴涵ln y 垂，则称三满足强迫规则( x y ) 。 e 是强迫规则集，如果l 满足e 中的每一个规则，则称l 满足强迫 规则集e ，记为ls a te ，所有满足强迫规则e 的语言的集合记为 l ( e ) 。 禁止规则：f 是+ 上的有限集。f 是禁止规则，如果一个语言l 满足 f 仁s u b ( l ) ，这里s u b ( l ) 是l e e 串的所有子串的集合，则称l 与 禁止规则f 一致，记为lc o nf 。如果，是禁止规则的集合，如果 l 与f 中的每一个规则都一致，则称l 与禁止规则集，一致，记为 lc o n 厂，所有与规则厂一致的语言的集合记为c ( 厂) 。 强迫禁止系统：一个强迫禁止系统用二元组( 厂，e ) 表示，它代表语言 类c ( f ，e ) = l + i fs a te 且lc o n ，) ，也就是c ( ，e ) = l ( 7 ) n c ( e ) 。 1 2 5自动铺砖模型 一个铺砖系统 1 0 8 ( 1 0 9 包含了有限种类的方砖，每个方砖有四条带标 记的边，且方砖不可旋转。只有标记相同的边才能够拼接到一起形成连 接。给定一些方砖和一些已经拼接好的种子方砖，当且仅当方砖与种子方 砖能够形成的连接大于一定数目时，方砖才可以拼接到种子方砖上，形成 新的种子方砖。铺砖系统是具有通用模型且与图灵机等价的模型f 1 1 4 1 。 自动铺砖模型可以用d n a 分子实现【1 1 1 【7 2 】【6 8 】【1 15 】。使用有四个粘 性末端的d n a 分子来表示方砖，只有w a s t o n c r i c k 互补的粘性末端才能 够结合形成连接。每种连接有一个确定的强度。而个d n a 分子只有在 连接强度不少于一定数值的情况下，才能与作为种子的d n a 形成稳定的 1 3 从理论到现实 8 结构。d n a 分子粘性末端在满足互补条件下形成双链结构是分子自发实 现的，而f 4 能够连接的分子可以同时完成连接，因此用d n a 分子能够实 现自动的非确定的铺砖系统 1 0 3 2 1 。 c h e n 等人还设计和讨论了减少自动铺砖系统错误积累的方法 2 5 2 6 f 1 1 4 。 另外，还有其它d n a 计算的模型，如端连接模型f 6 3 1 粘结模型 等 1 0 1 。很多文献对各种d n a 计算的模型进行了总结与分析 9 2 】 57 3 0 1 l7 。 1 2 6图灵机的实现 一个计算模型是否具有完备性是以图灵机的计算能力为标准的。一般 认为任何计算模型能够解决的问题，用图灵机也一定能够解决。以卜所列 的各种生物计算模型的图灵等价性一般是通过说明它能够产生递归可枚举 的语言来证明的。还可以用生物计算来直接模拟图灵机，从而得到“生 物图灵机”。其中代表性的工作有使用熔解和退火操作改变d n a 链的序 列，来模拟图灵机的格局转移f 1 2 1 ，和以环状d n a 上的剪切和连接为主要 操作米模拟图灵机的方法 1 0 2 1 。 这两种方法都是用d n a 操作来直接模拟图灵机的格局转移，并且都 利用了d n a 计算的大规模并行性的优点，能够在多项式时间内模拟非确 定图灵机。 1 3 从理论到现实 目前大部分的d n a 计算模型的计算能力都是在理论上证明了其讣算 能力，这些模型多是由计算机科学家和数学家提出的。而建立这些模型的 目标一般是它们的图灵等价性和通用性。这些模型对说明d n a 计算的能 力具有重要的意义，但d n a 计算的研究的目标是存实际应用中发挥其优 势。事实上，尽管早在5 0 年代就提出了分子可以计算的思想，但生物计算 只有在a d l e m a n 用实验的方法解决了7 个顶点的哈密而顿问题f 1 1 后，才得到 1 3 从理论到现实9 公众与众多研究者的关注，并且迅速的发展成一个独立的研究领域。其 理论模型绝大部分也是在这以后提出和证明的。k 女n k a r i 的评价6 1 1 f 6 5 1 ： 如果仅了解到生物和数学的相似性就可以进行d n a 计算的话，那我们早 就可以在d n a 便携机上玩电脑游戏了。事实上，把这两个过程结合在一 起，需要多种因素的成熟和如a d l e m a n 那样突破的创新思维。 1 3 1a d l e m a n 的实验 有向哈密顿路径问题：给定个有向图g = ( ke ) ，出发项点u m y , n 终止顶点y o u v ，是否存从顶点 i 。开始，到顶点y o u r 终止，经过且 仅经过图中每个顶点一次的路径。 从问题的定义可以看出，出发顶点不等于终止顶点。有向哈密顿路 径问题是n p 完全的 4 1 。对这个问题，a d l e m a n 给出了如下的非确定的算 法： 1 用d n a 串来表示图的信息。 2 随机的生成图中的路径。 3 仅保留那些从。出发，到y o u r 终止的路径。 4 去掉所有包含顶点个数不为n 的路径。 5 对图中每个顶点v ，去掉不包含 的路径。 6 如果还有路径，回答“是”，否则回答没有哈密顿路径。 卜述算法的每一步都可以用生物操作来实现。首先给每个顶点选择 个包含2 0 个核苷酸的d n a 序列。并给每一条有向边生成相应的序列它 的源顶点的后半部和目标顶点的前半部组成d n a 串。 l 3 从理论到现实 1 0 生成随机路径主要用到的是连接操作。因为每一条有向边由它的源顶 点的后半部和日标顶点的前半部组成，一个顶点的前半部和后半部是有互 补关系的粘性末端，冈此可以用连接操作来生成路径。 保留从顶点。m 发到顶点。终止的路径，是通过复制操作来实现的 一只复制那些从顶点 。出发到顶点。终止的路径。复制操作下分子数目 的增长是复制次数的指数函数，因而很容易使得那些没有复制的分子的浓 度达到可以忽略的程度。 第四个步骤通过分离操作实现，分离操作的原理是大小不同的分子在 胶体中运动的速度不同。 第五个步骤通过多步抽取操作完成。每一步抽取操作对应于抽取出包 含某个特定顶点的路径。 最后的判定也是通过复制操作来实现的。最后保留下来的d n a 串代 表了图的哈密顿路径。因此如果最后有d n a 串留下，通过复制操作使得 它的浓度大到容易检测的程度。反之，如果给定的有向图没有哈密顿路 径，那么不会有d n a 串留下来。因此，使用复制操作不会使d n a 串的 浓度增大。 在a d l e m a n 的实验结果发表不久，人们就发现用类似的思想和操作， 可以解决大类传统计算机似乎速手无策的问题7 0 1 ，尤其是组合问题。 其基本的思路分如下两部分： 1 用d 4 序列给问题的要素编码。 2 利用各种生物操作的生成初始解空间，并分离出合适的解。 l i p t o n 选用可满足性问题作为例子说明用d n a 计算来解决问题的这 一思想。下一，j 、节将简要介绍用这种方法解决可满足性问题的算法和其它 用d n a 计算来解决可满足性问题的研究。用l i p t o n 模式来统称这种大规 模生成问题实例要素的各种组合，然后从中挑选解的方法。 1 3 从理论到现实 1 3 2d n a 计算解决可满足性问题 在a d l e m a n 的实验结果发表不久，人们就发现生物计算适合用于解 决n p 完全这类对传统计算机来说是难以解决的问题。l i p t o n 首先给出了 用a d l e m a n 所用的操作，不仅能解决哈密顿路径问题，也能够解决可满足 性问题7 0 1 。 v = u l ，v 2 ，) 是一个布尔变量的集合，v 的真值赋值用函数 t ：v + t r u e ，f a l s e 来表示。对任意变量u ，如果t ( 1 2 1 = t r u e ，则称 住 t 下的取值为真，否则为假。d 的值为真当且仅当v n 值为假。d 与v 称 为y 上的文字。 y 上的一个子旬c 是y 上文字的析取，也就是对于y 上的一个真值赋 值，如果至少有一个c 中的文字在这个赋值下取值为真，子句c 的取值就 为真。反之，如果这个赋值使得所有的文字取值为假，那么整个子句取值 也为假。用g 表示子句的集合。 可满足性问题：给定变量集合v 和子句集合c ，是否存在v 卜的真值赋 值，使得g 中的每一个子旬的值都为真。 可满足性问题是n p 完全类中的一个重要问题，在理论上，它是第一 个被证明是属于n p 完全的问题2 7 1 ，且从其优化问题出发，人们发现了证 明n p 难问题不可近似性的规约f 9 1 0 1 ；在实际应用中，它被用作验证许多 方法是否有效的标准。 每个变量对应于两个d n a 序列，分别表示这个变量的赋值为真或 假，给变量任意排一个序v 1 ，v 2 ，v 。，再把变量依次的添加到表示赋值 的d n a 链上，任意一个d n a 链包含且仅包含变量的一种d n a 序列。 这样，最后每一条d n a 链都代表了变量集合的一个真值赋值，d n a 链 的集合就代表了v 的所有真值赋值可能的情况，共有2 ”种。 然后依次检查每一个子句，例如对子句口lv 观，首先抽取出含有”，的 d n a ，也就是表示仇赋值为真的子句，然后在从剩余的链中抽取出包含 1 3 从理论到现实 1 2 历的链，也就啦赋值为假的赋值，然后这两部分链就代表了全部使得子句 们v 吨为真的赋值。这样在检查完最后一个子句后，当且仅当有d n a 链 留下，存在使得所有子句为真的赋值。并且留下的d n a 链就代表r 使得 所有子句为真的赋值。 每个生物操作的花费被认为常数时间，尽管这个时间和电子计算机的 一个操作所用的时间比要长的多。因此，对生物计算，可以用汁算中生物 操作的个数来表示计算的时间复杂性，而计算的空间复杂度是指计算所需 分子数。 如果有礼个变量，生成代表可满足性问题各个变量的d n a 序列的 时间是0 ( n ) ，再由此得到所有可能解的时间是常数的。而如果有m 个子 句，且每个子句包含的文字为常数，所需的抽取操作也只要o f m ) ，然后 再需要一个检测操作来确定是否有可满足的解。因此，这种方法在多项 式，甚至足线性时间内解决了可满足性问题。但正如前文所说，这种方法 所需要的分子数是0 ( 2 “1 。 在这以后，用d n a 计算解决可满足性问题得到了众多的关注，人们 设计了多种解决可满足性问题的方法 1 0 7 5 1 3 3 1 1 3 5 6 】 5 5 3 6 5 0 4 6 【1 0 0 。 2 0 0 2 年，a d l e m a n 等人用l i p t o n 的方法成功的解决了一个含有2 0 个变 量，* f 1 2 4 个子句的可满足性问题的实例，为了使他们的实验更具说服力， 他们选择了只有一个真值赋值使得所有的子旬都满足的实例i 0 0 。这是 d n a 计算解决可满足性问题最好的实验结果。从理论上，d n a 计算同 时使用d a 分子个数不能超过2 的7 0 一8 0 次幂，而他们的实验是把实际向 这个理论极限的重要推进。 尽管可满足性问题的解决得到了众多生物计算研究者的关注，并且有 很多相关的研究成果，但用生物计算所能解决的可满足性问题的规模还无 法超过传统的计算机，方面是因为生物技术的水平或生物分子本身的特 性还不能使得生物操作具有高度的精确性，更重要的是尽管众多的解决方 案采用了各不相同的方法和实现手段，但基本的思想都是采用了大规模生 1 4 本文的结构与内容 1 3 成，挑选合适分子的模式。这种方式所需的分子个数往往是输入规模的指 数，因此使得即使在理论水平上，由于所需的分子个数随输入规模的增大 迅速增大，d n a 计算所能够解决实例的规模在这种模式下，不会优于普 通计算机【6 1 】。降低计算过程所需的分子数，是d n a 计算能够发挥其效用 的一个可能的重要前提。 1 3 3生物计算其它方面的应用 另外，生物计算还被用来模拟布尔电路 8 3 8 1 6 8 】 3 5 】【7 3 ，有限状态 自动机 1 4 f 1 5 3 】 1 1 1 1 1 2 ，动态规划 1 1 1 1 0 等a 人们还分析了不同操作 组合的计算能力 1 8 8 2 】，与复杂度类的关系 1 8 3 1 ，d n a 计算出错的情 况以及选择合适的操作以减少错误的方法 7 2 0 6 2 4 】 6 6 等。 另外，在信息安全方面，量子计算对公钥加密体制r s a 构成了潜在 的威胁 1 0 5 1 。尽管分析表明，生物计算也许不适合用r 解决整数分解问 题 1 3 但生物计算对d e s 加密系统的安全性提出了挑战 1 9 。 1 4 本文的结构与内容 本文的结构与内容安排如下： 第一章总结了d n a 计算的基本知识，以及研究状况。 第二章中，给m 了把参数算法应用于d n a 计算，使得d n a 计算中 的“瓶颈”一空间复杂度由一般的输入规模的指数降低为输入实例参 数的指数，这里主要讨论了顶点覆羲与独立集问题。 第三章q ，给出了在粘结模型下解决n p 完全类中带有数值参数的划 分和背包问题。 第三章还给出了一个能够实现数值连续相加的方法。 1 4 本文的结构与内容 1 4 在第四章中，简要总结了d n a 计算编码问题中衡量良好编码的两种 方法。 第四章还定义了自由码，并把自由码扩展到能够反映d n a 特性 - - w a s t s o n - c r i c k 互补的更一般意义下的演化自由码，得到演化自由 码的分层，这一章还讨论了分层结构的性质意义和应用。 最后在第五章对本义做了简要的总结，并展望了进一步的工作。 第二章 参数算法应用于d n a 计算 生物计算的一个重要的研究内容，就是为n p 完全问题寻找有效的基 于控制d n a 分子的算法。生物计算作为独立的研究领域发展起来，其起 点a d l e f n a n 的工作1 1 ，也正是解决了一个著名的n p 完全问题一哈密顿路径 问题。 大部分用d n a 计算解决n p 完全问题的模式，随着问题实例规模的增 长，所需要的d n a 分子数以输入规模的指数速度增长 7 0 5 】 2 1 4 6 1 。因 此，所需d n a 分子数目的快速增长，使得所能够解决的问题实例的规模 十分有限。 用传统的计算机解决n p 完全问题也存在类似的问题一传统计算机解 决n p 完全问题的平凡算法时问复杂度也是输入规模的指数函数。对可满足 性问题，s c h o e n n i n g 提m 了一个概率算法，在每个子句都只包含3 个文字的 情况下，也就是对3 可满足性问题，这个算法的时间复杂度是o ( ( 4 3 ) ”) ， 这里n 足实例包含变量的个数 1 0 4 。在这以后，提出了在生物计算模型下 实现这个算法的方法，如 5 1 】 3 3 】。这些方法把空间复杂度由原来的2 “降到 0 ( ( 4 3 ) “) 。 在降低生物计算的空间复杂度方面，还有许多其它的工作，例 如 7 9 8 4 8 5 1 1 4 6 等。 1 5 2 1 背景知识 1 6 另外一种以较低的时间复杂度来解决n p 完全问题的方法是为问题设 计参数算法。这种算法的时间复杂度不是输入规模的指数函数，而可能 是实例的某个参数的指数函数 3 4 5 4 2 3 】。本章把参数算法的思想廊用到 d n a 计算中，以降低用d n a 计算解决几个n p 完全问题的空间复杂度。 本章的内容如下： 茸先给出r 所用生物计算的模型一粘结模型。然后给出顶点覆盖问题 的参数概率算法，并在粘结模型下实现类似的算法，分析这种方法所需 的d n a 分子与通常的生成要素组合然后选出合适解方法所需分了数的比 较。然后我们结合独立集问题d n a 计算的参数算法，利用独立集问题与 顶点覆盖问题的关系，分别得到两个问题在参数较小，和参数规模较大， 但图的度数较小两种情况下，空间复杂度较小的算法。 2 1背景知识 2 1 1粘结模型 粘结模型是r o w e i s 等人提出的d n a 计算的一个抽象模型 1 0 1 。 一个粘结系统主要由两类d n a 序列组成： 类是较长的d n a 序列，用( n ，k ，m ) 来表示，其中n 芝k z ，序 列长度是n ，分为k 个不相交的区域，每个区域包含 t t l 个碱基。每 个这样的区域可以表示一个布尔变量，称作一个段。这种序列被称为 记忆串。 另外一类d n a 序列的长度为m ，这样的序列共有七种，分别对应于 记忆串的k # - 不同的段。这样的d n a 序列称为粘结子。每个粘结子 都能够并且只能够跟记v , m 的k 个记忆段中的某一个互补形成双链结 构。 2 1 背景知识 1 7 如果一个粘结子与记忆串相应的段粘结形成了部分双链结构，就称该 段处于开状态，台则称该段处于关状态。 也把一个( n ，k ，m ) 记忆串和粘结在其上的粘结子总称为记忆联合体。 这样，一个( n ，k ，m ) 记忆联合体表示的就是一个比特序列 o ，1 ) 。因此可 以用一个函数：口： 1 ，) 一 0 ，1 ) 来表示记忆联合体：口( i ) = 1 当且仪 当记忆联合体的第i 段的状态是开。通常也用a 来表示记忆联合体。 记忆联合体库：一个( p ，q ) 记忆联合体库，1sq p ，是由若干含有p 个段的记忆联合体构成。且 每个记忆联合体的前q 个段要么处于开状态，要么处于关状态， 而且对任意一个长度为q 的0 ，1 串，存在口，满足口为开兰j 且仅当串的第i 位为1 。 每个记忆联合体后p 一口段的状态都为关。 1 0 1 给出了有效生成记忆联合体库的方法。 在粘结模型中，记忆联合体的集合是多重集。以下是本文中将要用到 的一些在记忆联合体集合上的操作： 五u 噩：合并集合乃和正中的记忆联合体，以形成一个新的多重 集，包含丑和乃中的所有记忆联合体。 s e p a r a t e ( z i ) ：给定t 和一个整数i ，osi i y l a 。x 丁中每个记忆 联合体段的数目) ，该操作的结果是得到两个新的集合：+ ( e i ) 利 一( 7 1 ，i ) ，其中 一+ ( t ，i ) 包含t 中所有第i 段为1 的记忆联合体； 一一( 丁，i ) 包含丁中所有第i 段为0 的记忆联合体。 用( 丑，t 2 ) = s e p a r a t e ( t ，i ) 表示t 1 = + ( l i ) 和乃= 一( l i ) 。 2 1 背景知识1 8 s e t ( t ，i ) ：给定t 和整数i ，0 i m a x t 中每个记忆联合体的段 数目) ，s e t ( t ，把t 中每个记忆联合体的第i 段设为1 ，也就是每个 记忆联合体的第i 段粘结上相应的粘结子。 d e t e c t ( t ) ：给定t ，该操作检测t 中是否含有记忆联合体。如果丁中 没有记忆联合体，d e t e c t ( t ) 回答“否”；否则回答“是”。 2