最小顶点覆盖问题的闭环DNA算法

计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (20): 7-.

最小顶点覆盖问题的闭环DNA算法

周康,许进

武汉工业学院数理科学系

收稿日期:2006-04-24 修回日期:1900-01-01 出版日期:2006-07-11 发布日期:2006-07-11
通讯作者: 周康 zhoukang65

Closed Circle DNA Algorithm of the Minimal Covering Problem

Kang Zhou,

武汉工业学院数理科学系

Received:2006-04-24 Revised:1900-01-01 Online:2006-07-11 Published:2006-07-11
Contact: Kang Zhou

摘要/Abstract

摘要： 提出了闭环DNA计算模型的基本概念及其基本生化实验，并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中，提出并实现了用删除实验直接构造顶点覆盖补集的构想；再通过电泳实验得到最小顶点覆盖的补集，由补集得到最小顶点覆盖。这使得算法的设计独特而新颖。由于算法仅用到基本的生化实验，这使得算法的实现简捷、可靠。

关键词: 闭环DNA计算模型, 最小顶点覆盖问题, 补集, 删除实验

Abstract: In this paper, basic concepts and basic bio-chemistry experiments of a model of closed circle DNA computing are brought forward. Closed circle DNA algorithm of the minimal covering problem is put forward. In the closed circle DNA algorithm, an idea that complementary sets of vertex covering are formed straightway by delete experiment is put forward and realized, which has design of the algorithm inimitable and novel. And then complementary sets of minimal covering are obtained by electrophoresis experiment. Minimal coverings can gained from the complementary sets. Only using basic bio-chemistry experiments in the algorithm, so realizing the algorithm is simple and credible.

Key words: a model of closed circle DNA computing, minimal covering problem, complementary set, delete experiment

周康,许进.

最小顶点覆盖问题的闭环DNA算法

[J]. 计算机工程与应用, 2006, 42(20): 7-.

Kang Zhou,. Closed Circle DNA Algorithm of the Minimal Covering Problem[J]. Computer Engineering and Applications, 2006, 42(20): 7-.

[1]	王树梅. 数字图像中小目标自适应检测算法[J]. 计算机工程与应用, 2016, 52(1): 210-213.
[2]	彭立，杨恒伏. 描述逻辑SHIN的ABox一致性判定算法[J]. 计算机工程与应用, 2013, 49(20): 55-62.
[3]	周康同小军许进. 基于闭环DNA模型的八皇后问题算法[J]. 计算机工程与应用, 2007, 43(6): 4-6.
[4]	吴健辉^1,2,张国云¹,杨坤涛². 基于置信度的多分类器互补集成手写数字识别[J]. 计算机工程与应用, 2007, 43(30): 228-230.