图的最小顶点覆盖问题的DNA表面计算模型

doi:10.3778/j.issn.1002-8331.2009.06.021

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (6): 69-72.DOI: 10.3778/j.issn.1002-8331.2009.06.021

图的最小顶点覆盖问题的DNA表面计算模型

羊四清^1,2,李小龙²,袁辉勇¹

1.湖南人文科技学院，湖南娄底 417000
2.湖南大学计算机与通信学院，长沙 410082

收稿日期:2008-01-14 修回日期:2008-04-10 出版日期:2009-02-21 发布日期:2009-02-21
通讯作者: 羊四清

Surface-based DNA algorithm for minimal vertex covering problem

YANG Si-qing^1,2,LI Xiao-long²,YUAN Hui-yong¹

1.Hunan Institute of Humanities，Science and Technology，Loudi，Hunan 417000，China
2.College of Computer and Communication，Hunan University，Changsha 410082，China

Received:2008-01-14 Revised:2008-04-10 Online:2009-02-21 Published:2009-02-21
Contact: YANG Si-qing

摘要/Abstract

摘要： 基于生化反应原理的DNA计算具有强大的并行运算能力，DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略，给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上，然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术，通过观察荧光来排除非解，具有编码、解读简单和错误率低的特点。

关键词: DNA计算, 表面方式, 解空间, 顶点覆盖

Abstract: Biochemical reaction theory based DNA computation is of the massive inherent parallelism，so compared to silicon computer，DNA computer has most superiority out and away on NP problems.This paper proposes a new DNA algorithm of minimal vertex covering problem based surface by using the method of fluorescence labeling.The DNA molecules of the solution space are fixed on the solid carrier，and then get the all solutions of minimal vertex covering problem by the biochemical actions.The new algorithm utilizes the fluorescence-quenching technique，and can get all of the feasible solutions through investigating fluorescence.Analyses show that，the new algorithm has some good characteristics such as simple coding and encoding，low error rate.

Key words: DNA computing, surface-based fashion, solution space, vertex covering

羊四清^1,2,李小龙²,袁辉勇¹. 图的最小顶点覆盖问题的DNA表面计算模型[J]. 计算机工程与应用, 2009, 45(6): 69-72.

YANG Si-qing^1,2,LI Xiao-long²,YUAN Hui-yong¹. Surface-based DNA algorithm for minimal vertex covering problem[J]. Computer Engineering and Applications, 2009, 45(6): 69-72.

[1]	谭莉1，应石2. 多目标优化机制下DNA编码序列模型[J]. 计算机工程与应用, 2016, 52(15): 34-37.
[2]	陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.
[3]	孙守霞1，刘伟2，郭迎3，孟大志4. DNA计算机算术运算的自装配模型（III）—减法[J]. 计算机工程与应用, 2012, 48(32): 39-42.
[4]	臧文科1，夏瑞芳2，刘希玉1. MSC问题的一类表面DNA解法[J]. 计算机工程与应用, 2012, 48(22): 14-17.
[5]	叶春晓，罗娟. 基于网格的混合微粒群算法解决任务调度问题[J]. 计算机工程与应用, 2012, 48(12): 34-37.
[6]	张勋才，郗方. 微流控DNA计算的研究进展及展望[J]. 计算机工程与应用, 2011, 47(32): 37-41.
[7]	朱越. 基于DNA的连续优化算法[J]. 计算机工程与应用, 2011, 47(22): 48-52.
[8]	金婷婷，王波，宁爱兵. 最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用, 2011, 47(1): 32-34.
[9]	栗青生¹，杨玉星¹，马季兰². 基于粘贴模型的两类全排问题的DNA算法[J]. 计算机工程与应用, 2010, 46(4): 46-48.
[10]	刘伟¹，郭迎²，孟大志³. DNA计算机算术运算的自装配模型（I）—加法[J]. 计算机工程与应用, 2010, 46(20): 157-160.
[11]	刘伟¹，郭迎²，孟大志3. DNA计算机算术运算的自装配模型（II）—乘法[J]. 计算机工程与应用, 2010, 46(20): 161-163.
[12]	殷脂^1，2，叶春明¹，温蜜². 最小自由能约束的DNA编码设计研究[J]. 计算机工程与应用, 2010, 46(12): 25-27.
[13]	崔光照¹,秦利敏¹,王延峰¹,张勋才². 基于DNA技术的加密方案[J]. 计算机工程与应用, 2009, 45(8): 104-106.
[14]	李珍,王淑栋. DNA编码限制条件与编码策略[J]. 计算机工程与应用, 2009, 45(5): 43-45.
[15]	李金松,张强,周士华. 双链DNA解链温度的最小二乘支持向量机预测方法[J]. 计算机工程与应用, 2009, 45(5): 55-58.

图的最小顶点覆盖问题的DNA表面计算模型

Surface-based DNA algorithm for minimal vertex covering problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics