DNA计算在求解NP—完全问题的应用

龙源期刊网—完全问题的应用作者：周金凤来源：《科技视界》2012年第35期【摘要】基于生化反应的DNA计算模型越来越受到关注。DNA计算的研究已经成为一个热点。本文主要介绍了DNA计算在一些NP-完全问题中的应用。并分析了DNA模型存在的问题。指出未来国内DNA计算研究的重点可以在三个方面：解的检测，降低空间复杂度，生化实验研究。【关键词】DNA计算；NP-完全问题；最大团；最小顶点覆盖0引言电子计算机的快速发展，在很大程度上促进了优化计算问题的解决。但是，电子计算机运算速度不够快，存贮容量不够大。而且随着现代社会科学技术的不断进步发展，许多新的复杂疑难问题在不断出现，如一些非线性问题和NP-完全问题，特别是在一些工程领域内，电子计算机很难满足计算机发展的需要，为了可以更好的解决这类问题，一种新型的计算方法被受人们关注，即DNA计算。近些年来，DNA很受科学领域的关注。它的进步之处不仅仅在于其存储量和运算速度的改善，更重要的是他开发了本身潜在的计算能力。实践证明，DNA计算机在计算速度和存储容量等方面确实有很大的进展。DNA计算的基本思想是：利用DNA特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成DNA分子链，在生物酶的作用下，生成各种数据池，然后按照一定的规则将原始问题的数据运算高度并行地映射成DNA分子链的可控的生化过程。最后，利用分子生物技术如聚合链反应PCR、超声波降解、亲和层分析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需的运算结果。最早的计算机模式是由Alderman博士在1994首先提出的。而后，对于DNA计算机领域的研究引起了各科学等领域研究者的广泛关注。DNA计算研究的最终目的是构造出具有巨大并行性的DNA计算机。国内开始DNA计算的研究始于1996年。到目前为止，我国关于DNA计算的研究大致可以分为3个阶段，学习阶段、理论研究阶段、理论与实验研究阶段[1]。自2001年开始，国内关于DNA计算的研究基本上已经转入理论研究阶段。自2005年开始，开始进入实验研究阶段。为了克服DNA计算中的一些不足，一种将编码DNA序列固定在表面上进行操作的方法被广泛的研究。大部分DNA计算的出发点都放在解决古典的、非常复杂的计算问题上，特别是NP-完全问题。这里有三点原因：（1）NP-完全问题是现有计算机难以计算的。（2）NP-完全问题随着问题的变量、顶点的线性增加，计算时间是指数增加的；（3）可以说明DNA计算的高度并行性和超越电子计算机的潜在能力。NP完全性是计算复杂性理论中的一个重要概念，它表征某些问题的固有复杂度。一旦确定一类问题具有NP完全性时，就可知道这类问题实际上是具有相当复杂程度的困难问题。NP完全性的研究在实践中有重要指导作用。在算法设计和分析过程中，如果已证明某问题是NP完全的，这就意味着面临的是一个难于处理的问题。对于它，要找出一个在计算机上龙源期刊网可行的（即多项式时间的）算法是十分困难的，甚至可能根本找不到（因为很可能有NP≠P）。利用DNA计算模型解决了许多NP-完全问题，DNA计算是一种模拟生物分子并借助于分子生物技术进行计算的新方法，开创了以化学反应作为计算工具的先例，为解决NP-完全问题提供了一种全新的途径，DNA计算的实现方式可以分为3种：试管、表面、芯片，试管方式是DNA计算的初级阶段，目的是验证算法的可行性；表面方式是从试管走向芯片的过渡阶段；芯片方式是DNA计算最终成功的标志。下面几节中将较为详细的介绍国内关于NP-完全问题中的DNA研究成果。1NP-完全问题容易处理的问题属于P问题。至今既没有找到多项式的算法，又不能证明它不存在多项式的算法，这类问题成为NP问题，还有一类重要问题，只要其中任何一个问题能用一个多项式时间最坏情况算法来解，那么所有这些问题都能用多项式时间最坏情况算法解答，称其为NP完全问题，简称为NPC问题。因此，对于NP完全问题，最好是去寻找近似解法，或者针对该问题的某些有实用价值的特殊情况，寻找多项式时间算法。1.10-1规划问题的DNA计算模型对于0-1规划问题，2003年，殷志祥等人给出了表面DNA计算模型。通过观察荧光来排除非解，这种解读方法简单而有效且错误率低[2]。2007年，殷志祥等人又给出了基于分子信标芯片的0-1规划问题的DNA计算模型[3]。该模型将问题变量映射为分子信标探针，在芯片上制备可寻址的DNA分子信标探针，通过加入代变量的DNA链的互补链，DNA分子就会按照W-C互不原则进行杂交，从而并行地生成问题的所有可能解。随后通过对杂交后分子信标探针图像进行分析即可得到问题的最优解，和以往的DNA计算模型相比，该模型由于运用了分子信标芯片技术，具有高密度样品矩阵，有可能解决更多个变量的0-1整数规划问题。由于分子信标作为生物芯片可以充分利用自身的优点：编码简单；耗材低；操作时间短；技术先进。所以对于不同的组合优化问题，可以将标有不同荧光分子的信标、不同识别区长度的分子信标、不同茎杆长度的分子信标通过生物素的形式固定到硅片的表面上，制成分子信标片，利用所构造的分子信标芯片实现问题的自动化求解过程。其编码过程定在表面上，使之成为一行。（2）在每个不同行对应的分子信标探针的茎杆底部设置荧光。对应的算法步骤2，根据约束方程的各个变量，把它们中的各个变量对应的补链加到表面上，通过杂交使表面上的分子信标探针产生荧光，利用激光共聚焦显微镜观察到某一列分子信标探针对应的解是否满足该约束条件。（3）对应算法的步骤3，我们对步骤2的产物进行加热解开双链，冲洗掉与分子信标探针杂交的所有补链，（对于已经判断为不满足约束条件的不再考虑）。（4）对应算法步骤4，（我们重复步骤2，3的操作m次），我们就可以得到满足约束方程组的可行解。（5）对应算法的步骤5，我们对可行解所对应的目标函数值加以比较后，就可以得到问题的最优解。1.2最小顶点覆盖问题的DNA计算模型龙源期刊网=（V，E）的结点子集K？哿V，如果G的任意一条边都至少有一个端点属于K，则称K为G的一个顶点覆盖；若对任意结点V？哿K，K-{V}不再是顶点覆盖，称K为G的极小顶点覆盖；K是G的顶点覆盖，且G不存在另一顶点K′满足K′≤K，则称K为G的最小顶点覆盖；G的最小顶点覆盖的基数称为G的覆盖数，记做C（G），G的顶点覆盖常简称为G的覆盖。最小顶点覆盖问题是图论中一个著名的NP-完全问题。2004年，王淑栋等利用表面DNA计算的方法给出了最小顶点覆盖问题的DNA计算模型[4]。该模型的优点是结合了图论中的基本结论，增加了DNA计算的可操作性。但是该模型在编码介绍上不够清楚。2005年，董亚飞等人给出了最小顶点覆盖问题的粘贴模型[5]。在算法中设计了荧光淬灭的有关技术，利用观察荧光来排除非解，这种读解方法简单而有效且错误率低。由于检测方法的改变，省略了在试管计算中常用的酶切、磁珠分离、PCR扩增、凝胶电泳等步骤，避免了在这些步骤中可能出现的计算误差和数据丢失；并且我们使用的材料可重复使用，与在试管溶液中的DNA计算相比，更接近于工程实践。但是，自然界可供我们使用的荧光素种类有限，如果DNA计算的规模便得巨大，有可能造成计算材料上的困难，该方法是DNA计算粘贴模型利用表面技术的一种尝试。2009年，羊四清等利用基于表面的DNA计算，将图的最小顶点覆盖问题转化为特殊的0-1规划问题，将对应于问题解空间的DNA分子固定在固体载体上，利用荧光淬灭技术，通过对每一个约束方程进行判断，删除所有不满足条件的解，得到剩余解。最后比较剩余解中0的个数最多的解集都为该图的最小顶点覆盖[6]。1.3最大团与最大匹配问题的DNA计算模型最大团问题是图论上一重要的NP完全问题，而且它在理论和实践上具有重要的意义。设G=〈V，E〉是简单无向图，T？哿V，T≠Q，若T中任意两个顶点都相邻，则称T是图G的团。若T是图G的团，但是任意增加一个新顶点后，它就不成为团，则称T式图G的极大团。2004年，李源等给出了最大团问题的DNA计算模型[7]。该算法的主要思想是首先用一个n位的二进制数表示具有n个顶点的图的可能团，将问题转化为求解二进制数字串中含有1最多的数字串。然后设计算法，算法计算是从空网开始，对应的二进制数每一位都是0，然后让样本群体一代代演化。在每一代中，首先使各个二进制数的每一位以某一概率置1，然后从样本群体中删除在补图中相邻顶点对应位置均为1的数字串。算法的生物实现主要是先将二进制数编码到DNA链中，一个单链代表一个二进制数。为了编码一个n位二进制数，共用2*n+1种不同的DNA片段，分别用n+1种不同的DNA片段序列代表n+1个位置和n代表每一位置的片段，这里表示0，1值的序列分别用不同的长度；来区别。该算法在数值为1的位置不用任何DNA片段表示，而用酶切位点取代。通过酶切删除在补图中相邻顶点位置均为1的链，最后可以求出问题的解。该算法的最大优点在于将分子化思想引的入DNA算法中，而不是生成所有可能的解。因此使用了一个较小的样本空间可以对NP问题进行求解，随着图的顶点数的增加，算法所需的步骤也是线性增长的。龙源期刊网对于最大匹配问题，同样是一重要的NP完全问题。设G是无环图，M？哿E（G），M≠Q，如果M中任意两条边在G中均不相邻，则称M是图G的一个匹配。若对图G的任何匹配M′，均有M′顺序进行编码）二进制串来表示；若二进制串中的某位值为1，则其对应的边在匹配中；否则，则不在，具体的算法步骤如下：（1）对图G中的m位二进制串进行编码；（2）生成图G的满足条件的所有匹配。（3）找出其中含1最多的串，即为对应的最大匹配，并输出结果。本文主要思想通过表面上逐步生成解空间的过程，随时删除所生成的不可行解；最后，通过合适的编码，用PCR和电泳技术可以将解集中的不同解逐步分辨出来。1.4图的顶点着色问题图G的顶点集V（G）表示物体，G中的边表示边的来两个顶点所代表的物体不能在同一类中。用颜色C表示类，用着色α表示物体的划分：α：V（G）→C。如果C有k种颜色，则α被称为k着色。则称G是n可着色的。使得G是n可着色的最小值n称为G的点色数，或简称为色数，记为？掊（G）。图着色问题指的是给定一个n个顶点和m条边的图，？掊（G）是多少？图着色问题是NP-完全问题。2006年许进等人给出了一种图顶点着色的DNA计算模型[9]。给出了实现给出了实现20个顶点的图顶点的3着色的DNA计算机编码，拟以这20个顶点的图为例进一步研究此模型的DNA计算机。在前人工作的基础上，本研究针对性地提出了求解此类问题的专用型DNA计算机，不但给出了详细的理论说明及其基本原理，并且在此思想的指导下，利用杂交反应、磁珠分离技术以及PCR反应等生物实验技术，实现了具有5个顶点图的3着色的DNA计算，再一次验证了DNA计算的高度并行性，以及解决NP问题的可能性.同时从生物实验的角度出发，进行灵敏度实验，在此基础上通过预实验选择合适的杂交温度和杂交时间，确保PCR反应的有效模板浓度，并进行了重复实验，进而保证实验结果的可靠性。在以前的编码研究中，大多停留在理论研究水平，真正用于生物学实验的并不多。本文在前人研究的基础上，认识到编码的重要性的同时，综合考虑化学自由能、温度、生物酶、编码的相似性、DNA分子的组成等对编码的制约和影响，给出了8个约束条件，并在此基础上，给出编码的具体算法，并得到比较适合解决20个顶点的图的顶点3着色求解的DNA序列。5个顶点图的3着色的DNA计算所用的编码也来源于此。5个顶点的无向有限图的3着色的DNA计算的生物实验的成功，不仅丰富了DNA计算的理论，而且在实验过程中摸索到的实验条件都可以为进一步深入研究图顶点着色问题提供参考，甚至对其他问题的DNA计算都有很大的意义.但是本实验依然存在不足，实验过程耗时龙源