（运筹学与控制论专业论文）dna计算中的3—sat问题的自装配算法.pdf

摘要 在过去的1 0 年中，d n a 计算取得突飞猛进的成果，尤其是在s a t 问题卜， 咀l i p t o n ，a d l e m a n ，q i n g h u a l i u 等人为代表的科学家们纷纷在s a t 问题上， 取得了呵喜的成果。本文则在前人的基础上继续探索3 - s a t 问题的有效算法，并 给出了4 种方法的8 个算法 第种算法为自装配算法，根扼自装配的原理，设汁了链接力式，设汁的思 想非常简单明了，那就是首先在m 个试管中分别找到可以使m 个子句各自为l 的链，然后再将找到的这些链全都倒入同一个试管中，利用自装配方法一步找到 公共链，也就是公式的解。 第二种方法为荧光标记法，它足自装配算法的一种，j 不过他采用了荧_ ) 匕 ，】、 记的方式，它的设计思路与第一种方法基本相同，所不同的是，在第2 2 步将m 个试管中的链到入同一个试管中之后，用的是探针模板来找公共解，这也是一 步完成的，与算法一的效果是一样的，只是它的空问复杂度要比算法一要小一些。 第：一种算法为二二联接法，其实质上是算法的一种改进算法，卅；过所采 】的 方式比起算法一要巧妙的多，它同过三联接的设计，较好的解决了时吲复杂度的 问题。它主要通过三联管的设计，以三个试管为一个单位，进行自装配，也就是 分步白装配法，实现方法与第一种算法相同。 第四种方法为二：分法，这是一种分支策略，首先埘所有的变量通过其在j - 句中出观的数目进行变量重排，然后利用对斜率的算法求出第- 个分支点k ， 再根掘不同的情况确定第二个分支点，从而将所有的变量分成三部分，根掘这个 划分，相应得创建三个子库，对于三个子库相应的将所有的子句划分成四个部分， 从而将原束的公式划分成四个子公式。这样就将求原柬的公式解得问题划分成求 【j q 个子公式的公共解得问题。 这4 种方法的8 种算法，。前三种算法是本文的基小算法，它们的其f r i l 2 _ 处 在于，通过自装配模型来实现了算法的高度并行，从而将算法的时酬复杂度降低 到了n n e t 寸i b j ，而空| 日j 复杂度与其他算法相比却没有改进，而三分法则克服了 ： 述缺点，在将算法的时间复杂度降低到了常量的同时，也将空删复杂度降低到了 较小的水平。 关键词d n a 计算s a t 自装配 a b s t r a c t i nt h ep a s t10y e a r s ，al o to fa c h i e v eh a sb e e nm a d ei nt h ed n ac o m p u t i n g ， p a r t i c u l a r l yi nt h es a tp r o b l e m ，c u r r e n t l y ，l i k el i p t o n ， a d l e m a n ，q i n g h u al i ue t a 1 h a v em a d eg r e a tp r o g r e s si n t h i sf i e l d i nt h i sp a p e ric o n t i n u ew i t ht h ew o r ka b o u t 3 - s a tp r o b l e m se f f e c ta l g o r i t h mo fm yp i o n e e r s ，h e r eig i v ef o u rm e t h o dm a de i g h t k i n d so f a l g o r i t h m ： t h ef i r s tm e t h o di ss e l f - a s s e m b l ya l g o r i t h m ， i nt e r m so fs e l f - a s s e m b l yt h e o r y i d e v i c et h ef u n c t i o na e r a ，a n dd e v i c et h ea l g o r i t h mi t s e l f , t h ei d e ai ss i m p l e ，t h a ti st o f i n dt h o s es t r i n g sf r o mmt e s tt u b e sw h i c hm a ys a t i s f ye a c ho fc l a u s e sr e s p e c t i v e ，t h e n p u tt h i ss t r i n g st oo n et e s tt u b et o g e t h e r , t h e yw i l ls e l f - a s s e m b l yw i t he n z y m e s h e l pt o f i n dt h ec o m m o n a l i t ys t r i n g s ，t h a ti st h ef o r m u l a ss o l u t i o n t h es e c o n dm e t h o di sf l u o r e s c e n c es i g na l g o r i t h m ，i ti sak i n do fm e t h o do t s e l f - a s s e m b l yi nn a t u r e ，t h ei d e ai sj u s tl i k et h ef i r s to n e ，t h ed i f f e r e n c ei st h a t i tt o f i n dc o m m o n a l i t ys t r i n g sw i t hp r o b em o d e l ，a n di t ss p a c ec o m p l e x i t yi ss m a l l e rt h a n t h ef i r s to n e t h et h i r dm e t h o di st h r e e - l i n ka l g o r i t h m ，i ti st h ef i r s to n e si m p r o v ea l g o r i t h m ，i t a d o p tt h r e e l i n kw a y t od e v i c e ，a n dt a k et h r e et e s ta so n eu n i tt os e l f - a s s e m b l y , a n d u s et h es a m ew a yt oc a r r yo u t t h ef o r t hm e t h o di st h r e e s p l i ta l g o r i t h m ，t h i si sas p l i ts t r a t e g y ，f i r s tt or e s e ta l l v a r i a b l e si nt e r m so f t h en u m b e r so f t h ev a r i a b l ew h i c hi tt a k ep l a c ei nt h ec l a u s e t h e n b yt h ea l g o r i t h mo fs l o p et oe x a c tt h es p l i tp o i n to fk ，f u r t h e rt om a k es u r et h es e c o n d s p l i tp o i n t ，t h a ti st od i s t r i b u t ea l lv a r i a b l et op a r t s ，t h e ns p l i ta l lc l a u s et of o u rp a r t s ， t h a ti st os a yt h eb o o l e a nf o r m u l ai ss p l i ti n t of o u rs u b f o r m u l a t h i sf o u rm e t h o d sa n de i g h tk i n d so fa l g o r i t h m ，t h ef i r s tt h r e ea l g o r i t h mt h e b a s ea l g o r i t h mo ft h i sp a p e r , t h ec o m m o no ft h i st h r e em e t h o d si st o i m p r o v et h e p a r a l l e l i s mo fa l g o r i t h mb yt h em o d e lo fs e l f - a s s e m b l y , t h e nt or e d u c et h ec o m p l e x i t y o fa l g o r i t h m st i m et oc o n s t a n t ，b u tt h es p a c ec o m p l e x i t yo fa l g o r i t h mi sn ob e t t e rt h a n o t h e r s t h e1 a s tm e t h o do v e r c o m ef r o n ta l g o r i t h m sf a u l t a si tr e d u c et h et i m e c o m p l e x i t yt oc o n s t a n t ，s i m u l t a n e i t yi t r e d u c et h es p a c ec o m p l e x i t ym o r es m a l l e r t h a no t h e r s k e yw o r d ：d n ac o m p u t i n g s ar s e l f - a s s e m b l y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究j i 作及圾衔的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：趟丝浏醒慨妒s 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交沦文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 虢到仰新始他日期：跏疗7 第一章绪论 第一章绪论 1 1引言 在过去的几年中，能在单分子范围内执行计算步骤的分子计算机，已脱离了 科幻王国进入大众科学，8 年前，a d l e m a n 首次证明了小范围内的分子计算，从 这个打破实验促进了使用生物技术技术进行计算的d n a 计算或分子生物计算领 域的迅速演化。 早在1 9 5 6 年，理查德冯纽曼就曾经充满幻想的描述了构建一台“亚显微”f 3 5 】 计算机的可能性。目前，尽管各国科学家以极大的努力来不断提高计算机的速度、 容量和性能，并已经取得了巨大的进步，但是摩尔定律似乎已经走到了尽头，可 是“亚显微”计算机构想仍然是一个遥远的梦想，不过我们欣喜的看到各国科学家 已经认识到了它的广阔前景，不少人开始投入到这个领域的研究上来，虽然且前 仍然没有成熟的产品问世，但是在不少方面已经取得了可喜的突破，特别是在 d n a 计算方面尤为突出。 1 9 9 4 年，美国南加州大学的l e o n a r dm a d l e m a n 在美国著名杂志& 把 c g 上 发表了一篇划时代的论文p ”，这篇题为“m o l e c u l a rc o m p u t a t i o no fs o l u t i o n st o c o m b i n a t o r i a lp r o b l e m s ”的论文。提出了d n a 计算的概念，用人眼看不到的d n a 分子来做计算解决了一个n p 难题一有向哈密顿路径问题，借助生物实验向冯纽 曼的理想迈出了开创性的一步，指出了d n a 计算潜在的巨大并行性及待研究的 问题，开创了d n a 计算机的颓纪元。1 9 9 5 年，美国普林斯顿大学的r j l i p t o n 教授也在( s c i e n c e ) ) 上发表文章，利用d n a 计算的巨大并行性来求鳃n p 完备 问题可满足性问题( s a t 问题) ，从而开创了一个非标准计算研究的新领域。 它使人们对计算的本质产生了新的理解和认识。 1 2d n a 计算的显著特点： d n a 计算的核心问题是将经过编码后的d n a 链作为输入，在试管内经过定 时间完成控制的生物化学反应，以此来完成运算，使得从反应后的产物及溶液 中能得到全部的解空间。d n a 分子生物算法具有如下三方面的显著特点： ( 1 ) d n a 分子生物算法具有高度的并行性，运算速度快。在a d l e m a n 的 实验中【“i ，通过适当估计，d n a 串的并行操作数目可达1 0 ”，许多研究者认为， 北京工业大学理学硕士学位论文 用当前技术】0 ”到1 0 2 0 个串的并行操作是可以达到的，而目前最快的巨型机每秒 能执行l o ”个操作，虽然d n a 计算每个操作本身与电子实现相比非常缓慢，但 对于当前要求的巨型机或更强的计算挑战，d n a 反应的巨大并行性足以补偿； ( 2 ) d n a 作为信息的载体其贮存的容量非常之大，1 立方米的d n a 溶液 可存储l 万亿亿的二进制数据，远远超过目前所有电子计算机的总储存量； ( 3 ) d n a 分子生物计算所消耗的能量只有一台电子计算机完成同样计算 所消耗的能量的十亿分之一。d n a 计算的上述特性，即运算的高度并行性、 大容量、低消耗是目前计算机和并行计算机所无法比拟和替代的， 正因为d n a 计算具有上述突出的性能：运算过程的高度并行性、巨大的存 储容量、低能耗是目前的计算机和并行计算机所无法比拟和替代的，也是它能 够吸引世界各国科学家为之着迷的原因所在。从某种意义上说，1 9 9 4 年由 a d l e m a n 所开创的分子生物计算技术具有划时代的意义，从此以后，d n a 计算 机成为世界各国科学家们致力追求的目标，掀起了计算机革命的新篇章，一个 新兴的学科d n a 计算也随之诞生。 1 3d n a 计算的自装配 d n a 的自装配算法是目前最优越的算法之一，w i n f r e e 对d n a 自装配计算 的发展作出重要贡献，他的关于二维d n a 格的设计和自装配影响了后来d n a 计 算的发展方向。在他的工作基础上，d n a 计算的问题解决更具有简单性和仿真性。 后来自装配计算成为d n a 计算一个重要的研究方面，c h e n g d em a o 等人的论文 用d n a 三螺旋分子的自装配来实现加法和逻辑异或运算，a s h i s hg e h a n i 和 t h l a b e a n 等人把这种方法用于加密系统，提出了一种基于一次性密码本的d n a 加密算法。日本的k e n s a k u s a k a m o t o 等人提出的发卡状计算模型鳃决可满足性问 题，也是建立在分子自装配的基础上的。 基于表面的d n a 计算是早在9 7 年就提出的一种模型，他的优越性在于具有 实现自动操作的潜力，以及他的提升性。2 0 0 0 年n a t u r e 刊载了q i n g h u a l i u 的文 章，标志着表面上的d n a 计算正在逐步完善。 实现d n a 计算的自动化一直是研究者的一个目标，在这方面，比较突出的 工作是以色列著名的可编程生物分子自动机的提出。模拟t u r i n g 机的装置可以自 动并行的根据输入的程序执行不同的数据处理。日本人宣布制造出世界上第一台 d n a 计算机，它是专用来作基因分析的。 第一章绪论 d n a 计算中可满足性问题，也就是通常所说的s a t 问题，s a t 问题又可分 为三大类：溶液法，表面基法以及搜索算法。各自得代表人物分别是：a d l e m a n 和l i p t o n ，q i n g h u al i u ，m o g i h a r a 。s a t 问题是目前研究比较广泛的一个问题， 有许多世界著名的科学家涉足其中，也给它的发展注入了前所未有的动力，在 d n a 计算的研究中，s a t 问题是一个相对比较成熟的研究方向，研究成果也相 对较多，s c i e n c e 和n a t u r e 上有多篇论文发表，就是一个很好的证明。它从某个 方面告诉世人d n a 计算时可能实现的，去实现梦想只是个时间的问题。 1 4d n a 计算的发展现状 自1 9 9 4 年以来，d n a 计算以其独特的魅力，使得越来越多的科学家投身到 这个领域，它吸引了大量计算机，数学，生物分子学以及化学研究者的目光。在 这短短的十一年历史中，s c i e n c e ，n a t u r e 等顶级自然科学杂志上不断的有这门学 科的最新成果的论文发表，主要可分为理论模型的研究和应用性的研究，其中理 论模型所涉及的比较有代表性的研究方向有：d n a 计算的普遍性和通用性、算法 复杂性、编码理论、误差分析等，而应用性的研究，比如可满足性问题以及其他 n p 问题、代数运算、逻辑运算、加密机制等，其中a d l e m a n ，l i p t o n ，l i u q i n g h u a 等人作出了卓越的贡献。 d n a 的算法研究能分成两条路线：一条是理论路线，主要注重d n a 算法 的模型、算法和范例；第二条是实验路线，主要关注设计实验来验证理论思想的 再生化上的可行性。 d n a 计舁j 眸决n p 难题具有很大的优越性，科学冢们建互r 评多明计算模 型，已经解决了很多n p 难题，其中s a t 问题是研究最多的问题之一。 d n a 计算中的可满足性问题的最近进步可能导致不合理的期望，使用d n a 计算来解决超大型链和搜索问题，像s a t 问题不能被扩大到无限的范围。随着 陈述问题的大小截然不同的d n a 链的数量一般按值数增长，分子范围的数字存 储最终被大型问题所需要的d n a 数所吞没。有人预测对s a t 问题，可能的上限 是1 5 0 2 0 0 个布尔变量【3 2 】。 然而，适度大小的s a t 问题已经被用作d n a 计算技术的；一个有用的实验， 一般这些方法涉及到合成d n a 链的一个联合库的产生，包括与每个布尔公式相 联系的短d n a 词，大量的生物化学方法已被发展来接码布尔变量赋值并来分离 北京工业大学理学硕士学位论文 或鉴定这些链满足布尔公式的变量的一个真实赋值。 d n a 计算中的s a t 算法目前研究较多的是3 s a t 问题，3 - s a t 问题是一个 能最快知道连续算法所需要的指数时间的n p 完全计算问题，它是检验d n a 计 算机性能的基准。 在l i p t o n 3 】证明它能很好的适应利用分子计算机所提供的并行算法后，c o r n ， s m i t h 和其共事者已使用表面化学技术解决了s a t 问题一个4 个变量的例子，它 们嵌入d n a 链解码的布尔变量的赋值的所有可能到一个二维表面，并用限制性 内切酶去破坏不满足布尔公式的那些d n a 链，一个带荧光的光学读出器被用来 鉴定解码满足给定公式的赋值。 y o s h i d a 和s u y a m a 也使用一个d n a 程序执行了一个宽度的首次搜索解决了 一个含4 个变量的例子，s a k a r n o t oc ta 1 使用u 字形d n a 解决了一个含6 个变量 ( 6 4 种可能) 的例子。 l a n d w e b e r 及其共事者使用一个d n a 和r n a 联合技术来解决了一个与国 际象棋著名“骑士问题”相关的s a t 问题的一个9 个变量的例子，它们使用进化 论方法，来决定r n a 序列的一个集合用来清除哪些不满足布尔公式的链。 a d l e m a n l l 1 3 】【1 6 3 及其共事者的s a t 问题使用d n a 短链称为2 0 个布尔变量解 码器真实赋值的胶粘物，他们取得的最新突破可能是自动凝胶电泳的使用来分离 d n a 链拥有满足布尔公式真实赋值的凝胶解码的d n a 链。 上述规程需要许多付出巨大的努力与分离和侦测步骤，将只随着范围的增加 而增加，这些问题或只会通过使用d n a 计算自组的方法来克服，这种方法在没 有外部干扰的情况下能进行踱步计算，自主的d n a 算法首先被h a y g i a 和它的和 作者使用类似于p c r 扩张的技术和r e i fs c e m a n 及其合作者地用d n a 十亿分 之一的结构自装配技术通过实验证明最近s h a p i r o 及其合作者报道限制性内切酶 和链接酶的使用。 已知适度规模s a t 问题的解决方法的规程或许在分子生物领域【3 7 1 由有用的 应用，例如，他们可能被用于执行布尔补查询d n a 合成标签，在一个有巨大存 储的组成的一个“湿”数据库中。 d n a 链合成的每一个标签提供混合数据，比如样本中个体的鉴定技术，细 胞类型和采样日期。 第一章绪论 由b r a i c he ta l l l 7 1 发展的分离技术，对于它们s a t 问题实验或许被用作切底搜 索和抑制一小组的特殊分子从一大型联合分子集合中分离时错误，特别使用于 s a t 问题的分离技术，或许也有许多其他多种生物技术和安全应用，比如侦测和 跟踪大量毒素或暴露物质的测定时间。 除此之外，还有不少人在研究其他方面的s a t 问题，如q i n g h u al i u 等人研 究的表面基问题f 8 】，k e v i nt h e n 和v i i a yr a m a c h a n d r a n 等人研究的k s a 一2 6 ) f 3 9 】， m i s t s u om o t o k i 等人的最大可满足性问题【3 9 】等。 1 5 研究内容、意义及前景展望 我的研究方向是“d n a 的3 - s a t 问题”，主要研究d n a 计算中的各种s a t 问题，如：3 - s a t ，2 - s a t ，k - s a t ，m a x s a t 等问题，通过阅读大量的文献来了 解国内外有关s a t 问题资料，争取对可满足性问题有一个全面地了解和分析， 融会贯通各家之长，希望能找到一个更加有效的算法，这是一个初步的构想，不 过我的研究重点则放在寻找一个能实现对一般的s a t 问题的通用性解法，这个 难度要大一些。 不仅是n p 问题，甚至是通用问题，都有可能在d n a 分子计算机上得到有 效的d n a 算法，而这些问题在传统的电子计算机上，还没有找到多项式时间内 最佳解的有效算法d s 。研究s a t 问题的d n a 算法是寻找这些问题算法的有效途 径，因此深入研究s a t 问题必将促进d n a 计算的发展，促进d n a 计算机的研 发，为d n a 计算奠定坚实的基础。 国内外科学家已经在可满足性问题上取得了相当可观的成果，其中主要集中 在3 - s a t 问题上，利用使馆实验的方法依次解决了2 、4 、6 、8 、2 0 个变量的3 - s a t 问题1 6 1 ，找到一套比较好的算法模式和实验方法，然后不少人在此基础上对这些 算法作了些改进，把变量推广多达到1 2 0 ，不过没有脱离这些基本的方法，另 外还有一些科学家为了解决使馆操作的错误率过高的问题提出了表面基算法，也 取得了成功。但是不管是试管算法还是表面基算法，都存在着较大的误差，以及 较高的时间复杂度和空间复杂度，因此实际操作起来都比较困难。 对当前的发展情况作一个简单的分析：就像早期电子计算机产生以前一样， d n a 计算大量的计算模型数量要远远超过生化实验的数量。我们一步还不能踏 到d n a 计算机的门槛，在这条路上，生物化学反应的高误差限制着我们，可能 北京工业大学理学硕士学位论文 我们应该作一些能够适应当前这种情况的事情，可编程的自动机就是一个例子。 d n a 的并行是一个必然的目标，如果一个算法不存在并行，那建立一个d n a 计 算机是没有意义的。9 6 年g u a m i e d 只是实现了加法，他不是并行的，但l a b e 一6 】 用自装配的改进却实现了，可见生物化学方法的改进对d n a 计算的影响。能量 的消耗是生化反应的另外一个问题、凝胶电泳、p c r 、磁取【3 6 】等操作能量消耗的 效率都是很低的。信息的紧度曾经是我们值得骄傲的一点，但是不断的克服误差 使得信息的存储并不是多么的乐观。因此，表面方法是不是一种较好的方法呢? 它虽然降低了信息的紧度，但是操作是简单容易的。如果现实一点，实现表面上 的自动机是不是一条可行的道路呢? 如果必要的话，两者的结合可能会集中各自 的优点。 生物本质的方法是自装配【4 】，它从最底层来揭示d n a 计算的实质，被称为 “b o t t o m - u p 方法。自装配是让d n a 分子代替人做的部分工作，代替越多越好。 因此，自装配一定程度上也避开了频繁操作带来的误差累积，而且一次性生成产 物的过程也是容易控制的，所以自装配应当具有一定的可用价值。自装配的分子 设计是复杂的，自装配计算会更需要学科之间的交叉。 g i f f o r d 9 4 年在s c i e n c e 上提出“我们将能够认识一个自然的普遍计算系统”。 在自然界真的存在这样的一个系统吗? 假如能证明他存在的话，那我们有足够的 理由去寻找。假如不存在，研究会带来什么用处呢? 对这一点，我们也不会悲观。 d n a 计算给生物化学带来的冲击和影响使得它们不断的提高，这些技术性的工 作可以用于不同的地方。另外，正如a d l e m a n 所说，我们的目的是揭示计算和 生物的基本的方面。计算的实质揭示是要揭示并行的本质。 1 6 本章小结 这一章中简单介绍了d n a c o m p u t i n g 的知识背景，以及目前的研究现状， 说明了d n a 计算的优越性，以及研究的主要内容、意义和前景展望，另外，还 简单的介绍了d n a c o m p u t i n g 算中的s a t 问题和自装配算法。 6 第二章s a t 问题 曼量置曼曼置量曼舅目詈曼曼曼曼曼皇曼曼皇皇舅置一i i l l l m 鼍曼曼曼曼曼曼鼍曼曼兽 第二章s a t 问题 2 1 、可满足性( s a t ) 问题概念 2 1 1 定义 可满足性问题( s a t 问题) 是一个简单的组合搜索问题，它是最先得到的 n p 完全问题之。给定2 个或更多对象之间的关系的逻辑公式( 布尔公式) ， 通常我们假定公式已被转换为合取范式，一个s a t 算法能在有限的时间内， 判定任意给定的c n f l 3 9 l 形式的命题逻辑公式是否可满足，即找出所有变量的 赋值，使布尔公式的值为真。 2 1 2 布尔表达式 c n f ( 合取范式) ：设给定2 个或更多对象之间的关系的逻辑公式( 布尔 公式) 的合取范式为 f = c 1 八c2 八八c 。 2 1 其中c i = v i v v 2 v v v k 称为一个分句，v i 表示一个布尔变量或它的反。 它的三种运算： ( i ) 、c i 八cj = 1 当且仅当c i = c j = l ， ( i i ) 、 v i v v j = 0 当且仅当v 尸v j = 0 ， 0 i i ) 、v i = 0 则一v - l ，v i = i 则v i - o 举个简单例子： 布尔公式 f = ( x lv x 2v x 3 ) 八( x 】v 牙2v x 3 ) 八( x lv x 2v 牙3 ) 八( j lv 臂2v x 一3 ) 2 2 其中x ，工：，托是布尔变量，取值范围为0 或1 。0 表示“假”，l 为“真”。 “v ”表示逻辑“或”，“ ”表示逻辑“与”，夏表示x 取反：x = i ，则卫= 0 ，x = 0 ， 则j = 1 。当赋值为x ，= o ，x ：= 0 ，x ，= 0 时f 为真。 北京工业大学理学硕士学位论文 2 1 3s a t 问题的一般表述： 即s a t 问题的般表述为：寻找所有布尔变量的值，使2 1 每个子旬的值 为1 ，从而使公式f 为真。 2 2 、n p 完全问题 n p 完全问题是一个困难的算法问题，也就是说常规的电子计算机在多项式 时间内不能解决的问题。 一个问题是n p 完全的，即所有的n p 问题均能有效的变换到它。1 9 7 1 年， c o o k 证明了第一个n p 完全问题可满足性问题( 可满足性问题) ，可满足性 问题是n p 完全的，被称为是c o o k 定理。 2 3 、约束可满足性问题：( g s p ) 给定有限个变量以及每个变量的取值范围，要求找出所有变量得值，使得一 些给定的约束条件被满足。如果每个变量的取值集合都是有限的，这样的问题被 称为有限c s p 3 9 。s a t 问题可看成是c s p 的特例，其中每个变量取值范围都 是真假值集合，而要满足的约束条件就是所给的逻辑公式。 2 4 、3 一s a i 问题： 在个布尔表达式中，要求每个子句最多只有3 个文字，这样的问题称之 为3 - s a t 问题；若要求最多含有2 个文字则为2 - s a t 3 9 1 。l i p t o n 研究的问题属于 2 - s a t ，a d l c m a n 和q i n g h u ai i u 等人研究的问题都属于3 - s a t 。l i p t o n 采用的是 有向图法【3 】a d l e m a n 采用的是凝胶电泳法1 1 6 ，q i n g h u a l i u 则使用的表面基算法。 目前，对于3 - s a t 问题的研究已经达到相当高的水平，对它研究的方式也 多种多样，各种方法都得到了尝试，并且很多方法已经得到了试验的验证，能够 得到满意的解这对全世界的研究者来说是最大的鼓舞，本文则是在前人的研究 成果的基础上，主要对自装配方法和溶液算法进行了改进。 2 5 其他s a t 问题 当然3 - s a t 问题只是s a t 问题中的重要组成部分，它还包含许多其它问题1 3 9 如：2 - s a t ，唯一可满足性问题( q u i q u es a t ) ，s a t 问题的表面基算法，k s a t 问题，最大可满足性问题( m a x s a t ) ，发夹问题，d n a 计算的搜索算法等。 s a t 问题可以解决一些历史著名的实际计算难题如：八皇后问题、鸽笼问题、图 第二章s a t 问题 着色问题、最优购货规划、图的最短路经问题、布尔逻辑可满足性问题等。 2 6d n a 计算的操作原理 2 6 1d n a 计算的基本步骤 通常，d n a 计算主要包括三个步骤f 3 】： 1 、进行编码，即将所要解决的问题映射为一个d n a 分子的集合： 2 、计算过程，进行各种生化反应如杂交、链接及延伸等生成可能解空间： 3 、解的分离和读取( 如p c r 反应和凝胶电泳) 2 6 2d n a 链的互补原则 设d n a 链由口l ，t 2 2 ，口 序列构成，其中口 爿，c ，g ，t 。d n a 双链由 两条d n a 序列，口2 ，口i 和屈，履，反构成，它们满足w a t s o n c r i c k 互 补条件：对于f = 1 , 2 ，k ，口，和卢，必须互补即a + 碱g c 。互补序列 以逆平行方式粘接在一起，其中，5 端和3 端是指d n a 链的末端，如图2 1 5 一口 l 一口 2 一口 3 一 一3 一一0 一 $ 一0 3 、一8lp2 83 一5 、 图2 - 1 2 6 3d n a 计算的简单试管操作 在试管中可对d n a 链进行许多简单的操作【3 j ： 1 ) 合成大量短的单链的拷贝，这了短的单链至少要有2 0 位核苷酸。 2 ) 将互补的单链粘接成一条d n a 双链。 3 ) 给定一支试管，提取那些包含长为l 的连续模式的序列。假定d ，艿，4 a t ，c ，g ，对于i ，仅当 占i 。口，8 25 口，瓯= 口+ t 一1 时d n a 链口1 ，口2 ，口i 将被移去，此问题取l = 2 0 足够。 4 ) 给定一支试管进行“检测”操作，该操作只是测定试管中是否存在任何d n a 链，可由p c r 来完成。 5 ) 最后进行“放大”操作，对试管中所有的链进行复制。 北京工业大学理学硕士学位论文 2 7 d n a 计算的常用操作： d n a 计算在本质上属于生化反应，为了利用d n a 分子完成给定的任务， 我们必须借助对d n a 分子的各种操作技术。对d n a 分子的操作【3 5 】【3 7 1 1 38 1 ，既有 物理的，也有化学的。物理操作实质上是调控生化反应的外部条件，例如温度， 酸碱度等等。此外是来自各种生化实验手段，尤其是通过各种酶的操作。 ( 1 ) 重排：也称作初始化。这一步将产生所有需要生成的d n a 链。这些链可以根 据要求代表不同的数值。 ( 2 ) 合成：使游离的碱基形成寡核苷酸的过程。 ( 3 ) 混合：把两个试管中的溶液混合。 ( 4 ) 剪切：利用特定的限制性内切酶，在d n a 双链的某个位置切断形成带有粘 头的两条链的过程。 ( 5 ) 延长：这一过程需要一条已知单链模板和一条已存在的、并已与模板的- 4 , 段匹配的引物d n a 序列，要延长的d n a 序列根据模板给出的序列结构， 在聚合酶的作用下由5 端到3 端的方向不断延伸。 ( 6 ) 缩短：通过外切核酸酶从d n a 分子的末端去掉一个核苷酸而缩短d n a 分子。 ( 7 ) 熔解：通过加热溶液到某一特定温度，将双链d n a 分解成两条互补的单链 d n a 。加热破坏了互补链之间的氢键。 ( 8 ) 复合( 退火) ：使熔解的逆过程，把含有单链的溶液冷却，将两条完整的单链 d n a 序列，按w a s t o n c r i c k 互补原则配对且将缝隙修补好，重新连接起来 形成双链d n a 。 ( 9 ) 修复：在双链d n a 中，如果其中一条单链中有不连续部分，可通过d n a 连 接酶来修复。 ( 1o ) 杂交分离：早期d n a 计算模型的重要操作，可提取包含特定短序列的所有 单链。 ( 1 1 1 复制( 放大) ：通过聚合酶链式反应( p c r ) 将d n a 串复制，p c r 扩张是利 用d n a 聚合酶，将给定溶液中的特定d n a 序列快速的复制或放大。它包 含一系列温度循环的重复。每一循环由三个阶段组成：模板d n a 的变性分 解成链；冷却使引物与寡聚核苷酸的模板进行复合，以此来设计与感兴趣的 d n a 区域相接；由d n a 聚合酶使引物延伸。每一个反应循环都是目标d n a 0 第二章s i 问题 分子的数量加倍，因此该反应呈指数式增长。 ( 1 2 ) 分离( 凝胶电泳) ：是一种使d n a 按大小排序的重要技术，将d n a 链放在 湿的凝胶的顶部并对凝胶施加一电场，由于d n a 带负电，在电场的牵引下， 是d n a 链到达凝胶底部，由于短d n a 链的压力较长d n a 链要小，其移动 速度快，经过一段时间后，d n a 链就按各自的大小排列在不同的区域。 ( 1 3 ) 聚合：给一段短的寡核苷酸引物p ，引物p 可以是d n a 也可是r n a 但是引物 的3 末端核苷酸或脱氧核糖核苷酸的核糖的第三碳上必须是羟基，( 3 - o h 末端) ，当p 和一个长寡核苷酸模板结合后，在d n a 聚合酶的作用下，将脱 氧核苷酸一个个的往引物上添加，直到形成一个完整的互补双链结构为止。 ( 1 4 ) 提纯：使用亲和力，通过吸引将那些包含给定模式的d n a 链作为子链提取出 来。 ( 1 5 ) 破坏：利用外核酸酶破坏标识链，或用切割酶切断所有的标识链，或用凝胶电 泳移去所有完整的链。 ( 1 6 ) 删除：这一步操作是利用一些外切核酸酶选择表丽上的d n a 链的末端。外 切核酸酶具有一定的特性，可以针对单链，也可以针对双链。通过选择不同 的外切核酸酶，可以有选择的删除标记的双链或者非标记的单链。 ( 1 7 ) 绑结：用d n a 结合酶来粘贴d n a 链。 ( 1 8 ) 检测：若一只给定试管中至少包含一条d n a 链，则为“是”，反之则为“否”。 ( 1 9 ) 读出( c ，s ) ：需要把表面上的链分离出去。一些内切酶可以识别双链的短序 列中的限制性位点，并在这个位点把双链切断。当表面上的链含有这些位点， 当加入内切酶时所有表面上的链都可以被分离。然后利用溶液中读取d n a 链的方法进行读取。 2 8 本章小结 本章介绍了s a t 问题的基本概念，以及目前研究的几种s a t 问题，并着 重介绍了d n a 中的试管操作方法和d n a 计算的基本操作原理，也就是说本 章主要介绍了s a t 问题和d n a 计算的基础知识。 北京工业大学理学硕士学位论文 第三章：s a t 问题的综述 对于s a t 问题的研究可大致分为4 种方法：( 1 ) 试管溶液法：( 2 ) 表 面基法；( 3 ) 自装配法；( 4 ) 搜索算法。 3 1 试管溶液法： 3 1 1 l i p t o n 的有向图法： 3 1 1 1 算法设计思想： 1 ) 通过让d n a 链表示所有可能的解，在试管中产生所有的解空间： 2 ) 通过d n a 链的类型匹配，在另一个试管中提取真解； 3 ) 测试是否新试管中包含有d n a 链。 3 1 1 2 编码设计 对于公式 f = ( x v y ) 八( 肖v 】，) 3 一l l i p t o n 解码法：构造一个简单的有向图g 。，如图3 1 ： x v a 3 y 图3 - 1 a l ，一，墨，口2 ，x 2 ，2 2 ，口州为节点，从吼寸磁和曩以及从 以和瓦争吼+ l 为边。则可对所有从口l 一吼+ 结束的路径都对进行编码。若经 过不带”上标的结点，编码为l ；带“”上标的，编码为0 ，如路径口l i 口2 y c t 3 编 码为0 1 。 结点编码设计：前一半用p ，表示，后一半用矾表示，试管中d n a 单链为： 1 ) 5 一3 的d n a 序列：p ，q ( 第i 个结点) ；2 ) 3 _ 5 的d n a 序列：玩e ( 边 i 斗j ) 3 ) 长为1 2 ， y j5 的d n a 序列：磊；4 ) 长为l 2 ，3 斗5 的d n a 序列：玩。 第三章s a t 问题的综述 i i i 每条合理的路径对应于一条正确匹配的结点和边的序列，如图3 - 2 5 7 一， i 3 一5 ，) 1 5_札 图3 - 2 顶点v 的编码为p 。q ，边v u 编码为玩死。结点的粘性末端和边的粘性 始端互补，可以链接；同样，边的末端和下一个节点的始端也可链接。这样有向 图( 1 月所有可能的路径都可以全部编码了。 3 1 1 3 算法操作 假定所有d n a 链都为单链，用e ( t ，i ，a ) 表示在第t 个试管中所有第i 位等于a ( a 0 ，1 ) ) 序列，先建立一系列试管。如果a = l ，该操作检测x f 的序列： 如果a = 0 ，则检测薯的序列。 让第一支试管t o 包含所有可能的编码序列，操作如下： 提取e ( t o ，1 1 ) 放入t l ，剩下链放入t l ，然后提取e ( t l ，2 ，1 ) 放kt 2 ， 把t l ，t 2 倒在一起放入t 3 ： 提取e ( t 3 ，1 ，o ) 放入t 4 ，剩下的链放入o ，提取e ( t 4 ，2 0 ) 放入t 5 ， 把t 4 ，t s 倒在一起放入t 6 检测t 6 中是否存在任何d n a 链，如有就是所要求的结果，如表3 1 。 t 瞪tt u b ev a l u e sp r e s e n t 表3 1 】11 l 1 】0 0 1 o o 1 o l 1 j 地溉眦 吼； n 。 钆 0 0 00 幻“巧堙m“以瞎玲 北京工业大学理学硕士学位论文 试管t 3 中包含了所有满足第一个分句的序n ：o i ，1 0 ，1 1 。同样，试管t 6 包 含了所有从t 3 开始的满足第二个分旬的序列：o l ，1 0 。后者正好是给定s a t 问题的正确答案。 3 1 1 4 算法分析： ( 1 ) 提取操作l i p t o n 估计大约有9 0 的成功率，在试管数较多的情况下，每 做一步提取操作只有9 0 的成功率，若做n 次提取正确率只有0 9 “，当 n 很大时正确率就会很低，可能最后一步检测读取试管中有d n a 链时根 本就检验不到有链的存在； ( 2 ) 每一步转移操作，都会含有d n a 混合物碎片的残余液体存在，容易发 生错误： ( 3 ) 溶液中两个互补的单链序列很容易杂交，容易发生错误； ( 4 ) 最重要的问题在于，仔细分析l i p t o n 的算法发现他的算法是基本串行的， 虽然在每一步提取中有并行的因素，但它的并行性是很低的，而且这个算 法如果推广到大规模的算法问题，将需要大量的试管，操作比较复杂。 3 1 2a d i e m a n 凝胶电泳法 对一个6 个变量1 1 个句法的布尔公式： 0 2 ( x l v x 2 v - x 3