DNA solution on surface for minimal set covering problem

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (22): 14-17.

Previous Articles Next Articles

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

MSC问题的一类表面DNA解法

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

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

Abstract

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

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

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

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

[1]	TAN Li1, YING Shi2. Multi objective optimization mechanism for DNA coding sequence model [J]. Computer Engineering and Applications, 2016, 52(15): 34-37.
[2]	ZHANG Xuncai，XI Fang. Research advances and prospect of microfluidic DNA computing [J]. Computer Engineering and Applications, 2011, 47(32): 37-41.
[3]	ZHU Yue. Continuous optimization algorithm based on DNA [J]. Computer Engineering and Applications, 2011, 47(22): 48-52.
[4]	LI Qing-sheng¹，YANG Yu-xing¹，MA Ji-lan². DNA algorithm of two kinds of full permutation problem based on sticker model [J]. Computer Engineering and Applications, 2010, 46(4): 46-48.
[5]	YIN Zhi^1，2，YE Chun-ming¹，WEN Mi². Research on DNA encoding design constraint by minimal free energy [J]. Computer Engineering and Applications, 2010, 46(12): 25-27.
[6]	CUI Guang-zhao¹,QIN Li-min¹,WANG Yan-feng¹,ZHANG Xun-cai². Encryption scheme research based on DNA technology [J]. Computer Engineering and Applications, 2009, 45(8): 104-106.
[7]	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.
[8]	LI Jin-song,ZHANG Qiang,ZHOU Shi-hua. Prediction of melting temperature of DNA duplex by least squares support vector machine [J]. Computer Engineering and Applications, 2009, 45(5): 55-58.
[9]	ZHOU Kang^1,2,WEI Chuan-jia¹,CHENG Zhen²,HUANG Yu-fang²,XU Jin². Study of DNA computing model [J]. Computer Engineering and Applications, 2009, 45(18): 1-5.
[10]	ZHENG Xue-dong¹,XU Jin¹,XU Fei². Parallel DNA arithmetic computation based on special moduli set [J]. Computer Engineering and Applications, 2008, 44(6): 51-54.
[11]	WANG Yan-feng¹,NIU Ying¹,CUI Guang-zhao¹,ZHANG Xun-cai². Efficient genetic algorithm based on cultural algorithm applied to DNA sequences design [J]. Computer Engineering and Applications, 2008, 44(36): 61-65.
[12]	WANG Zi-cheng,ZHOU Kang,LUO Liang,QIANG Xiao-li. Research of filtering function on coding sequence in DNA computing [J]. Computer Engineering and Applications, 2008, 44(32): 10-11.
[13]	YANG Yu-xing¹,LI Qing-sheng¹,MA Ji-lan². DNA algorithm of a kind of forbidden ranking problem based on sticker model [J]. Computer Engineering and Applications, 2008, 44(30): 40-42.
[14]	LI Qing-sheng,YANG Yu-xing. Sticker DNA algorithm of Oracle-Bone Inscriptions retrieving [J]. Computer Engineering and Applications, 2008, 44(28): 140-142.
[15]	MA Fang-fang¹,WANG Shu-dong¹,LI Han²,XUE Sheng-wei¹. DNA computing model for shortest directed path problem based on sticker and delete system [J]. Computer Engineering and Applications, 2008, 44(25): 40-42.

DNA solution on surface for minimal set covering problem

MSC问题的一类表面DNA解法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics