A DNA computer model for solving vertex coloring prob-lem  

作　　者：XU Jin QIANG Xiaoli FANG Gang ZHOU Kang 

机构地区：[1]Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China [2]Department of Biotechnology, Dalian University, Dalian 116622, China

出　　处：《Chinese Science Bulletin》2006年第20期2541-2549,共9页

基　　金：the National Natural Science Foundation of China （Grant Nos. 60533010, 60574041, 60373089, 60274026）.

摘　　要：A special DNA computer was designed to solve the vertex coloring problem. The main body of this kind of DNA computer was polyacrylamide gel electrophoresis which could be classified into three parts: melting region, unsatisfied solution region and solution region. This polyacrylamide gel was con- nected with a controllable temperature device, and the relevant temperature was Tm1, Tm2 and Tm3, res- pectively. Furthermore, with emphasis on the encod- ing way, we succeeded in performing the experiment of a graph with 5 vertices. In this paper we introduce the basic structure, the principle and the method of forming the library DNA sequences.A special DNA computer was designed to solve the vertex coloring problem. The main body of this kind of DNA computer was polyacrylamide gel electrophoresis which could be classified into three parts： melting region, unsatisfied solution region and solution region. This polyacrylamide gel was con- nected with a controllable temperature device, and the relevant temperature was Tin1, T~ and T~, res- pectively. Furthermore, with emphasis on the encoding way, we succeeded in performing the experiment of a graph with 5 vertices. In this paper we introduce the basic structure, the principle and the method of forming the library DNA sequences.

关 键 词：DNA计算机 编码 生物计算机 顶点着色 

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