摘要
1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图的最小顶点覆盖问题 .构造了含有 6个顶点 10条边的图的顶点集子集对应的数据池之后 ,进行了一系列的合成、杂交、清洗、变性等生物操作 ,得到所有覆盖对应的 DNA序列 ,然后通过编址过程得到所要求的最小覆盖 .
In this paper, a model of DNA computing on surface of minimal vertex covering problems of graph is designed a feasible method and operating procedure of biochemical experiment of an example is given. Firstly, we construct a data pool corresponding to the subsets of vertex set of a graph with 6 vertices and 10 edges. Secondly, we proceed a series of biochemical experiments. synthesis, hybridization, cleaning and denaturalization etc. In this way, the DNA sequences corresponding to all the coverings is obtained. Then, we get all the minimal coverings according to the encoding address procedure.
出处
《小型微型计算机系统》
CSCD
北大核心
2004年第2期242-244,共3页
Journal of Chinese Computer Systems
基金
国家自然科学基金 (60 1740 47
60 2 740 2 6)资助课题
关键词
DNA计算
覆盖
顶点的度
DNA computing
covering
degree of a vertex
