马莹++殷志祥

摘 要：图的着色问题是著名的NP问题，有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多，有表面DNA计算，粘贴DNA计算。本文提出质粒DNA计算，首先把顶点着色问题转化为求最大独立集问题，然后给出了图顶点着色问题的质粒DNA分子生物实验，利用限制性内切酶的特性切割有边相连的顶点，得到最大独立集，在试验中特别引入了一个备用试管，最后给出一个具体的实例。实例给出具体的着色方案，证明了该质粒DNA算法有效并且是可行的。

关键词：DNA计算；顶点着色；最大独立集；质粒

中图分类号：TP301 文献标志码：A 文章编号：1672-1098（2015）02-0064-04

DNA Computing Model for the Graph Vertex Coloring Problem by Plasmids

MA Ying， YIN Zhi-xiang

（School of Science，Anhui University of Science and Technology，Huainan Anhui 232001， China）

Abstract：Graph coloring is a famous NP-problem， which has important practical significance， which applies in channel allocation of communication system， examination room arrangement and so on. There are a lot of DNA computing methods for graph coloring problem， such as surface DNA computing， pasting DNA computing. In the paper the plasmid DNA computing for the graph vertex coloring problem was presented. At first， the graph vertex coloring problem was transformed into a vertex of maximum independent set problem. Then the plasmid DNA molecular biological experiment of graph vertex coloring problem was conducted. The vertexes connected with edges were cut by using the feature of restriction enzymes， and the maximum independent set was obtained. In the experiment a spare tube was introduced. At last， the method was illustrated by an example. In the example the final coloring schemes were given. It was verified that the plasmid DNA algorithm is effective and feasible.

Key words：DNA computing； vertex coloring problem； maximum independent set； plasmid

1994年，文献[1]首次用DNA计算解决有向图的哈密顿问题；1995年文献[2]在Adleman思想的启发下，解决了可满足性问题；1997年，文献[3]利用DNA计算解决了另一个NP完全问题，图的最大团问题；2000年，文献[4]提出了用质粒DNA分子来解决可满足性问题；2004年，文献[5]提出了基于质粒DNA匹配问题的分子算法。

图顶点着色问题是著名的NP问题。2003年，文献[6]讨论了图的3-顶点着色的DNA算法；2005年，文献[7]提出了先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA 粘贴算法，并调用这两个算法解决了图顶点着色问题；2006年，文献[8]提出将图的顶点着色问题转化为SAT-问题来解，并且利用粘贴DNA计算来解决；2009年，文献[9]建立了一种基于酶切技术和PCR技术的图顶点着色DNA计算模型，给出了实现该模型的双编码的编码方案。……