马莹++殷志祥

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

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

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

文章编号：1672-1098（2015）01-0000-00

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

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