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

• 博士论坛 • 上一篇    下一篇

MSC问题的一类表面DNA解法

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

  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. 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

摘要: 利用基于表面的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