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

周金凤

（安徽理工大学 安徽 淮南 232001）

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研究成果。

1 NP-完全问题

容易处理的问题属于P问题。至今既没有找到多项式的算法，又不能证明它不存在多项式的算法，这类问题成为NP问题，还有一类重要问题，只要其中任何一个问题能用一个多项式时间最坏情况算法来解，那么所有这些问题都能用多项式时间最坏情况算法解答，称其为NP完全问题，简称为NPC问题。因此，对于 NP完全问题，最好是去寻找近似解法，或者针对该问题的某些有实用价值的特殊情况，寻找多项式时间算法。

1.1 0-1规划问题的DNA计算模型

对于0-1规划问题，2003年，殷志祥等人给出了表面DNA计算模型。通过观察荧光来排除非解，这种解读方法简单而有效且错误率低[2]。2007年，殷志祥等人又给出了基于分子信标芯片的0-1规划问题的DNA计算模型[3]。该模型将问题变量映射为分子信标探针，在芯片上制备可寻址的DNA分子信标探针，通过加入代变量的DNA链的互补链，DNA分子就会按照W-C互不原则进行杂交，从而并行地生成问题的所有可能解。随后通过对杂交后分子信标探针图像进行分析即可得到问题的最优解，和以往的DNA计算模型相比，该模型由于运用了分子信标芯片技术，具有高密度样品矩阵，有可能解决更多个变量的0-1整数规划问题。由于分子信标作为生物芯片可以充分利用自身的优点：编码简单；耗材低；操作时间短；技术先进。所以对于不同的组合优化问题,可以将标有不同荧光分子的信标、不同识别区长度的分子信标、不同茎杆长度的分子信标通过生物素的形式固定到硅片的表面上，制成分子信标片，利用所构造的分子信标芯片实现问题的自动化求解过程。其编码过程为：首先合成3n种短的寡聚核苷酸。将它们分为3等组，第一组的n种寡聚核苷酸分别表示变x1，x2，…xn；第2组的 n 种寡聚核苷酸分别表示变量第 3 组的 n 种寡聚核苷酸分别是第一组对应的补链，并分别记为x1′，x2′，…xn′。 为了避免他们之间的错误杂交 ，我们选择前两组的寡聚核苷酸具有较大差异，至少有4个以上的不同（注意这里xi对应的寡聚核苷酸表示变量xi取值为1，而对应的寡聚核苷酸表示变量xi取值为0）。然后利用前2组的2n种寡聚核苷酸构造分子信标探针，对应的分子信标识别区分别为表示的寡聚核苷酸片段。

我们下面分五步来简单介绍基于分子信标的0-1规划问题的生物操作过程：（1）构造出2n种分子信标对应的探针，每个分子信标识别区包含n个变量对应的寡聚核苷酸，利用杂交的方法将它们固定在表面上，使之成为一行。（2）在每个不同行对应的分子信标探针的茎杆底部设置荧光。对应的算法步骤2，根据约束方程的各个变量，把它们中的各个变量对应的补链加到表面上，通过杂交使表面上的分子信标探针产生荧光，利用激光共聚焦显微镜观察到某一列分子信标探针对应的解是否满足该约束条件。（3）对应算法的步骤3，我们对步骤2的产物进行加热解开双链，冲洗掉与分子信标探针杂交的所有补链，（对于已经判断为不满足约束条件的不再考虑）。（4）对应算法步骤4，（我们重复步骤2,3的操作m次），我们就可以得到满足约束方程组的可行解。（5）对应算法的步骤5，我们对可行解所对应的目标函数值加以比较后，就可以得到问题的最优解。

1.2 最小顶点覆盖问题的DNA计算模型

对于图G＝（V，E）的结点子集K哿V，如果G的任意一条边都至少有一个端点属于K，则称K为G的一个顶点覆盖；若对任意结点V哿K，K-{V}不再是顶点覆盖，称K为G的极小顶点覆盖；K是G的顶点覆盖，且G不存在另一顶点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为图G的最大匹配。G中最大匹配中的边数称为匹配数，记作α′（G）。

2003年，刘文斌等人给出了最大匹配问题的表面DNA计算模型[8]。对于任意给定的 n 阶图 G=（V，E），令 G（E）={e1，e2，…，em}。 则其可能的匹配可以很方便的应用m位（按照边的顺序进行编码）二进制串来表示；若二进制串中的某位值为1，则其对应的边在匹配中；否则，则不在，具体的算法步骤如下：

（1）对图G中的m位二进制串进行编码；

（2）生成图G的满足条件的所有匹配。

（3）找出其中含1最多的串，即为对应的最大匹配，并输出结果。

本文主要思想通过表面上逐步生成解空间的过程，随时删除所生成的不可行解；最后，通过合适的编码，用PCR和电泳技术可以将解集中的不同解逐步分辨出来。

1.4 图的顶点着色问题

图G的顶点集V（G）表示物体，G中的边表示边的来两个顶点所代表的物体不能在同一类中。用颜色C表示类，用着色α表示物体的划分：α：V（G）→C。如果C有k种颜色，则α被称为k着色。对i∈C，集合α-1（i）被称为第i个色类。如果对G的边集E（G）的每一条边xy着色 α 满足 α（x）≠α（y），则称 α 是一个正常着色。 如果对于某个m≤n，G可以被m种颜色正常着色，则称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计算都有很大的意义.但是本实验依然存在不足，实验过程耗时较长，溶液中DNA链的损失较大，还应从选择更适用的实验方法和手段，以及寻找更具有普适性的编码方案等方面继续深入研究。

2 面临的问题

虽然，DNA计算有了很大的发展，但是还是存在一些不足之处，理论和实际操作方面都还面临着一系列的挑战。在生化反应操作的过程中容易出错。特别是在进行杂交时容易出错。计算精度不能够得到确保，因为核酸酶的降解效率不够高；DNA的计算规模还受到限制；所以对于DNA计算机来说，一些问题还需要及时进行解决。（1）怎样才能够把误差降到最低，因为在进行生物操作的提取和退火步骤中，会产生误差。（2）怎样更好的对获得的结果进行检索？大量DNA聚集在一起，因为发生退火反应以至于产生“伪解”。（3）怎样才可以尽量避免错误地杂交？（4）怎样才可以进行正确的编码？随着用于编码的寡聚核苷酸链长度的增加，编码的复杂度也随着增加，容易产生发夹结构。（5）在进行实际操作时，怎样才能够建立更好的模型，使问题得到有效解决？[10]。

3 进一步的研究方向

从1994年Adleman提出计算机模型以来，DNA计算的研究内容有了很大的发展：DNA芯片的研制、DNA计算模型的构造、DNA计算和纳米技术的结合，计算模拟和序列设计等。DNA计算可以分为大致以下几个研究方面：

（1）解的检测。如何将溶液状态下产生的众多解（DNA链）中代表所求问题最终解的DAN链分离出来，寻找合理、有效地分离方法。

（2）降低空间复杂度。由于表面（固体状态）计算是将时间复杂性转化为空间复杂性，因此如何降低时间复杂性转化时的空间复杂性就显得非常重要。而如何降低空间复杂性牵涉到算法设计和编码。因此进一步研究DNA计算中的算法是非常重要的一个研究内容。另外，结合其他相关算法如进化算法、遗传算法及神经网络算法等进行研究也是一个有效途径。最后，DNA计算中编码的研究也是一个非常重要的研究方向，因为好的编码方法不仅可以解决复杂性转化问题，而且它关系到DNA计算的各个方面，如生化操作的可行性，错配率的高低、伪解的产生以及生化实验的成败。

（3）生化试验的研究。DNA计算的研究的最终目标是构造DNA计算机，这就必须能进行生化试验。现有的DNA计算模型大部分都是理论研究，是否可以通过生化试验进行实现还有待进一步研究，生化试验不仅可以验证算法的优劣而且可以为进一步研究提供不断地改进方案。因此，我们认为即使对现有的DNA计算模型进行生化实验的研究都是有意义的。

虽然DNA计算现在还存在一些问题，但是DNA计算作为一个新兴的研究领域，已经得到了广泛应用，而且已用来解决了很多实际问题。现在科学家对DNA的研究和发展抱有很大信心。它使人们首次认识到生物中存在的基本算法，总之，DNA计算机和DNA计算有着巨大的发展潜力。

［1］高琳,许进,张军英.DNA 计算的研究进展与展望[J].电子学报,2001,29(1)：973-977.

［2］殷志祥,许进.分子信标芯片计算在0-1整数规划问题中的应用[J].生物数学学报,2007,22(3)：559-564.

［3］殷志祥,张凤月,许进.基于分子信标的DNA计算[J].生物数学学报,2003,18(4)：497-501.

［4］王淑栋,许进,董亚飞.图的最小顶点覆盖问题的面上DNA解法[J].小型微型计算机系统,2004,25(2)：242-244.

［5］董亚飞,张家秀,殷志祥,许进.最小顶点覆盖问题的改进粘贴模型[J].电子与信息学报,2005,27(4)：556-560.

［6］羊四清,李小龙,袁辉勇.图的最小顶点覆盖问题DNA表面计算模型[J].计算机工程与应用,2009,45(6)：69-72.

［7］刘文斌,高琳,王淑栋.最大匹配问题的 DNA表面计算模型[J].电子学报,2003,31(10)：1496-1499

［8］李源,方辰,欧阳颀.最大集团问题的 DNA计算机进化算法[J].科学通报,2004,49(5)：439-443.

［9］许进,强小莉,方刚,等.一种图顶点着色 DNA计算机模型[J].科学通报.,2006,51(4)：480-487.

［10］殷志祥,张家秀.图论中的DNA计算模型[J].系统工程与电子技术,2007,29(7)：1159-1163.

［11］李鲁华,吐尔根.依布拉音.DNA计算的原理及应用[J.应用技术,2005.

［12］殷志祥.图与组合优化中的DNA计算[M].北京：科学出版社,2004.