基于DNA计算的最大权团问题设计

张喆++殷志祥

摘要：介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果；结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理，设计了新的用于解决最大权团问题的算法步骤，大大提高了算法效率，实现了最大团和最大权团的同步求解，对市场分析、方案选择等领域有一定的意义。

关键词：DNA计算；质粒；粘贴模型；最大权团；凝胶电泳

中图分类号：TP301.6文献标志码：A

文章编号：1672-1098（2015）01-0075-03

对于给定的无向图G=（V，E）。如果UV，且对任意u，v∈U有（u，v）∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。而最大权团，就是指权值最大的最大团。

1994年，文献[1]提出了用DNA分子解决7节点的Hamilton路径问题，这是有关DNA计算的开山之作。之后文献[2]在Adleman思想的启发下，通过构造一个接触网络图G，将可满足性问题（SAT）的解空间，映射成通过接触网络G的始点到终点的所有Hamilton路径，然后对有向图中的顶点和边进行编码，用DNA计算解决了3—变量的可满足性问题。1997年，文献[3]提出了用DNA计算求解最大环问题的方法，为DNA计算解决NP问题提供了又一佐证。2000年，文献[4]提出了在固体表面进行DNA计算的方法，改变了过去在试管溶液中进行DNA计算的生物操作的方法，进一步提高了DNA计算的可靠性和效率，近些年，文献[5]2009年解决了闭环求解最大团问题的算法；文献[6]于2010年解决了基于粘贴模型的最大团问题算法；文献[7]于2011年结合Aunp自组装聚合色变与DNA计算相结合，构建了系列基本逻辑计算模型；文献[8]于2012年设计出了结合DAE块的DNA自组装模型求解最大团问题的算法，并在2013年进一步改进，等等。本文将用图1所示的顶点图来进行实验，利用DNA计算的算法求出其最大权团。

图1顶点图

其中V1对应权重为ω1，V2对应权重为ω2，……，V5对应权重为ω5。

1DNA计算的原理

DNA计算的基本思想是以DNA链作为信息载体，将原始问题映射为DNA分子链（包括单链、双链、带有粘性末端的单双混合链），对设计出的DNA分子进行扩增，在实验室中对这些DNA分子进行诸如退火、杂交、连接[9] 等生化操作，最后采用电泳技术[10] 、层析分析技术、分子纯化技术[11] 、激光技术等方式检测DNA计算的最后结果。

比较经典的实验方式是在试管中进行DNA计算操作。计算过程中可能要用到一个或者多个试管，可根据需要在试管中加入引物、缓冲液、酶等反应物。本实验过程即是在试管中进行的。

2质粒及粘贴模模型

质粒是游离于染色体之外的具有自行复制子的DNA双链分子，实验中运用的质粒通常具有复制子、选择标志、克隆位点等特征。质粒最大的特点是质粒上任一子段不会重复出现在质粒的另一位置。这样，对于质粒的修改就只会在特定的位置进行，而不会在其他位置进行。

粘贴模型拥有一个由存储合成物构成的可以随机访问的存储区。每个存储合成物由存储链和粘贴链的DNA单链分子组成，存储链和粘贴链都是由不同的碱基构成，存储链含有K个不重叠的子链，而任一粘贴链按碱基互补配对原则恰于存储链中的任一子链配对。当粘贴链可以与存储链结合时，此位置视为“开”，在二进制中可以用1表示；反之，视为“关”，在二进制中用0表示。

利用质粒以及粘贴模型各自的优势，将二者结合起来用于解决最大权团问题。

3DNA算法步骤

以图1为例来说明算法的实现过程，设计的模型如图2所示。

图2新链

此模型结合粘贴模型以及质粒模型：由主链、辅链1、辅链2三个部分组成，其中辅链2与辅链1相连，辅链1与主链相连；主链表示顶点对应的DNA链，辅链1表示顶点间边的关系，顶点间有边相连设置为双链DNA分子，无边设为单链，辅链2代表权值，不同顶点对应的每个子链中都含有可以被限制性内切酶特异识别的DNA序列（这样可以被限制性内切酶所识别，进而进行剪切），同时根据权值的大小将各个子链设置成不同的长度。m1 是权值除以各个权值的最大公约数n得到的结果，即有ω1=nm1；对于整条链，将其插入质粒1中（质粒可选取pOK12质粒）。

将图2所示的DNA链进行扩增，并将其产生的质粒试管称为T0。对于一个图的顶点集V={V1，V2，…，Vn}，从中任取i≥2的顶点，如Vk1 ，Vk2 ，…Vki ，对于辅链1，保留位段（ Vr，Vt），其中r、t任取k1，…，ki中的任意两个，且取遍所有可能。对于辅链2，只保留Vk1，Vk2 ，…Vki 所对应的权值子段。

在图1中任取3点{V1，V2，V3}，经过上述操作，可以得到存储合成物（见图3a）。

在图2中任取3点{V1，V2，V5}，经过上述操作，可以得到存储合成物（见图3b）。

（b）图3存储合成物

由图3可以看出，图3a中的辅链1并不完全是双链，而图3b中的辅链1完全是双链，{V1，V2，V5}对应的完全子图就是图1的一个最大团。

i的取值不断增加（2≤i≤n），不断的复制T0 来进行上述操作，然后筛选出辅链1全为双链的合成物，其对应的顶点集即为图的最大团。对于图1来说，可以筛选出最大团为{V1，V2，V5}，{V3，V4，V5}。利用限制性内切酶切下筛选出的合成物各自的辅链2，由于各自的权值不同，所以各自的辅链2长度也不同，此时可以利用凝胶电泳筛选出长度最长的合成物，在利用探针照明技术确定顶点组成，此时即可求出最大权团。endprint

4小结

最大团以及最大权团问题是著名的组合优化问题，它在市场分析、方案选择、信号传输、计算机视觉、信息恢复、容错能领域都有着广泛的应用。另外，许多NP—完全问题都可以转化成为MCP，如可满足性问题、独立集问题、顶点覆盖问题等。而DNA计算具有纳米级、超强并行操作能力以及特异性杂交识别等天然优势，使其非常适合用来解决最大团问题。

本文运用DNA计算可以有效的解决最大权团问题，使得最大权团问题更好的运用于生产实践中，具有一定的实践意义。在解决最大权团问题中，还有一些待解决的问题，比如DNA的合成与编码、如何运用尽量简单的方式形成解空间等，同时如何剔除“伪解”和“错解”，筛选出最优解也是非常重要的。今后的研究将着重于以上几个方面。

参考文献：

[1]ADLEMAN L M. Molecular computation of solutions to combination problems[J]. Science，1994，266（5 187）：1 021-1 024.

[2]LIPTON R J.DNA solutions of hard computational problems[J].Science，1995，268（5 210）：542-545.

[3]OUYANG Q，KAPLAN P D，LIU S，et al.Solution of the maximal clique problem [J].Science，1997，278（17）：446-449.

[4]LIU Q， WANG L， FRUTOS A G，et al.DNA computing on surface[J]. Nature，2000， 403（13）：175-179.

[5]许进，谭钢军，范月科，等.论DNA 计算机模型[J].计算机学报，2007，30（6）：881-893.

[6]周康，刘朔.基于粘贴模型的最大团问题算法[J].华中科技大学学报：自然科学版，2010，38（9）：89-92.

[7]张成，杨静，许进，等.缩短法计算模型求解最大独立集问题[J].科学通报，2011，54（24）：3 913.

[8]周炎涛，李肯力，罗兴，等.一种基于DNA自组装模型求解最大团问题的算法[J].湖南大学学报，2012，39（9）：39-44.

[9]CHEN J，WOOD D H.Computation with biomolecules[J].Commentary，2000，97（4）：1 328-1 330.

[10]许进，李三平，董亚非，等.粘贴DNA计算机模型（II）应用[J].科学通报，2004，49（4）：299-307.

[11]殷志祥， 张凤月，许进.基于分子信标的DNA计算[J].生物数学学报，2003，18（4）： 497-501.

（责任编辑：何学华）endprint