MSC问题的一类表面DNA解法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (22): 14-17.

MSC问题的一类表面DNA解法

臧文科1，夏瑞芳2，刘希玉1

1.山东师范大学管理科学与工程学院，济南 250014
2.山东山大鸥玛软件有限公司，济南 250101

出版日期:2012-08-01 发布日期:2012-08-06

DNA solution on surface for minimal set covering problem

ZANG Wenke1, XIA Ruifang2, LIU Xiyu1

1.Management Science and Engineering Institute, Shandong Normal University, Jinan 250014, China
2.Shandong?University?OuMa?Software?Co.Ltd, Jinan 250101, China

Online:2012-08-01 Published:2012-08-06

摘要/Abstract

摘要： 利用基于表面的DNA粘贴模型求解最小集合覆盖问题。改进体现在计算模版表面穷举了所有可能的结果，同一时间验证结果是否满足条件，真正实现了DNA的强大并行性。同时在互补的寡聚核苷酸片段发生退火反应时，利用特殊的化学反应，通过催化剂来决定是否杂交，减少了人工参与，提高了计算效率。通过计算机仿真模拟验证了模型的可行性。

关键词: DNA计算, MSC问题, 表面方式

Abstract: This paper uses surface-based DNA model to solve the problem of minimum cover set. The improvement is reflected in all the possible results that are listed exhaustively on the surface of calculation template, which are at the same time verified to satisfy the condition. Accordingly the powerful parallelism of DNA is realized. While oligonucleotide annealing reaction of complementary pieces occurs, use a special chemical reaction, and determine by catalyst whether to create hybrid. This can reduce human intervention and improve calculation efficiency. Finally, the feasibility of this model is verified by computer simulation.

Key words: DNA computing, minimal set covering problem, surface-based fashion

臧文科1，夏瑞芳2，刘希玉1. MSC问题的一类表面DNA解法[J]. 计算机工程与应用, 2012, 48(22): 14-17.

ZANG Wenke1, XIA Ruifang2, LIU Xiyu1. DNA solution on surface for minimal set covering problem[J]. Computer Engineering and Applications, 2012, 48(22): 14-17.

[1]	谭莉1，应石2. 多目标优化机制下DNA编码序列模型[J]. 计算机工程与应用, 2016, 52(15): 34-37.
[2]	孙守霞1，刘伟2，郭迎3，孟大志4. DNA计算机算术运算的自装配模型（III）—减法[J]. 计算机工程与应用, 2012, 48(32): 39-42.
[3]	张勋才，郗方. 微流控DNA计算的研究进展及展望[J]. 计算机工程与应用, 2011, 47(32): 37-41.
[4]	朱越. 基于DNA的连续优化算法[J]. 计算机工程与应用, 2011, 47(22): 48-52.
[5]	栗青生¹，杨玉星¹，马季兰². 基于粘贴模型的两类全排问题的DNA算法[J]. 计算机工程与应用, 2010, 46(4): 46-48.
[6]	刘伟¹，郭迎²，孟大志³. DNA计算机算术运算的自装配模型（I）—加法[J]. 计算机工程与应用, 2010, 46(20): 157-160.
[7]	刘伟¹，郭迎²，孟大志3. DNA计算机算术运算的自装配模型（II）—乘法[J]. 计算机工程与应用, 2010, 46(20): 161-163.
[8]	殷脂^1，2，叶春明¹，温蜜². 最小自由能约束的DNA编码设计研究[J]. 计算机工程与应用, 2010, 46(12): 25-27.
[9]	崔光照¹,秦利敏¹,王延峰¹,张勋才². 基于DNA技术的加密方案[J]. 计算机工程与应用, 2009, 45(8): 104-106.
[10]	羊四清^1,2,李小龙²,袁辉勇¹. 图的最小顶点覆盖问题的DNA表面计算模型[J]. 计算机工程与应用, 2009, 45(6): 69-72.
[11]	李金松,张强,周士华. 双链DNA解链温度的最小二乘支持向量机预测方法[J]. 计算机工程与应用, 2009, 45(5): 55-58.
[12]	李珍,王淑栋. DNA编码限制条件与编码策略[J]. 计算机工程与应用, 2009, 45(5): 43-45.
[13]	周康^1,2,魏传佳¹,程珍²,黄玉芳²,许进². DNA计算模型的研究[J]. 计算机工程与应用, 2009, 45(18): 1-5.
[14]	郑学东¹,许进¹,徐菲². 基于特定模数集的并行DNA算术运算[J]. 计算机工程与应用, 2008, 44(6): 51-54.
[15]	王延峰¹,牛莹¹,崔光照¹,张勋才². 基于文化遗传算法的DNA编码序列设计[J]. 计算机工程与应用, 2008, 44(36): 61-65.