图的顶点着色问题的DNA算法  

A DNA Algorithm for Graph Vertex Coloring Problem

作　　者：高琳[1] 许进[2] 

机构地区：[1]西安电子科技大学雷达信号处理国家重点实验室,陕西西安710071 [2]华中科技大学系统科学研究所,湖北武汉430074

出　　处：《电子学报》2003年第4期494-497,共4页Acta Electronica Sinica

基　　金：国家自然科学基金 (No 69971 0 1 8;60 0 71 0 2 6);陕西省自然科学基金 (2 0 0 1X0 5)

摘　　要：图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色 ,这个问题是著名的NP 完全问题 ,没有非常有效的算法 .但在 1994年Adleman[1] 首次提出用DNA计算解决NP 完全问题 ,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算 ,使得NP 完全问题的求解可能得到解决 .本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法 ,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码 ,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离 ,依据分子生物学的实验方法 ,本文提出的算法是有效和可行的 ;其次指出了该算法的优点。Given an undirected graph,the vertex coloring problem is to assign a different color for vertex mutually adjacent.This problem is an NP-complete one and has no effective solving method.But Adleman introduced firstly the DNA computing in 1994,with which the NP-complete problems are likely to be solved.DNA-based algorithm simulates molecular biology structure of DNA by means of molecular biology technological computation.This paper first introduces the DNA algorithm for the vertex coloring problem based on bio-molecular technology.The key of the algorithm is coding for the vertex and the color of the vertex The problem is solved by tube operation that performs the basic core processing and extraction that makes the results visible.On the basis of the experimental bio-molecular method,the algorithm is an effective method.Finally,the advantage and disadvantage are discussed,and the future research directions are pointed out.

关 键 词：DNA计算 NP-完全问题 顶点着色问题 限制酶 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]