图顶点着色问题的质粒DNA计算  

DNA Computing Model for the Graph Vertex Coloring Problem by Plasmids

作　　者：马莹[1] 殷志祥[1] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001

出　　处：《安徽理工大学学报（自然科学版）》2015年第2期64-67,86,共5页Journal of Anhui University of Science and Technology:Natural Science

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]