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

张 喆，殷志祥

(安徽理工大学理学院，安徽 淮南 232000)

对于给定的无向图G=(V，E)。如果U⊆V，且对任意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 计算的算法求出其最大权团。

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

1 DNA 计算的原理

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

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

2 质粒及粘贴模模型

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

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

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

3 DNA 算法步骤

以图1 为例来说明算法的实现过程，设计的模型如图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)。

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

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

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.