DNA芯片组技术及其在解决NP问题中的应用  

DNA-chip-group Technology and Its Application in Solving NP Problems

作　　者：孟大志[1] 仲国强[1] 王丽娜[2] 

机构地区：[1]北京工业大学,应用数理学院,北京100124 [2]青岛理工大学,琴岛学院,青岛266106

出　　处：《北京工业大学学报》2009年第5期685-689,共5页Journal of Beijing University of Technology

摘　　要：为了用DNA并行算法解决实际应用中的一个NP问题——图的四着色问题,基于先进的DNA计算理论、DNA芯片技术、数据库技术,提出了DNA芯片组技术的概念;通过解决一个极大平面图(包括外边界的中国地图)的四着色问题,阐述了DNA芯片组技术的具体操作步骤;对生化实验进行计算机模拟并对数据库进行分析与处理,得到了所有的可行着色方案,从而验证了DNA芯片组技术在解决NP问题中的巨大应用能力.In order to solve a practical NP problem of map four-coloring by using DNA parallel algorithm,a concept of DNA-chip-group technology is proposed,which is based on advanced DNA computing theorem, DNA-chip technology and database technology.The operation steps of the DNA-chip-technology are introduced through solving a four-coloring problem of a maximal planer graph—map of China,which includes the outside part of the boundary as well as the inside ones.The computer simulation of the biochemical experiment,the analysis and processing on the database is carried out,and all of the correct coloring schemes are obtained.The powerful capability of application of the DNA-chip-group technology in solving NP problem is proved.

关 键 词：DNA计算 DNA芯片 极大平面图 NP问题 四着色问题 

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