MSC问题的一类表面DNA解法  

DNA solution on surface for minimal set covering problem

作　　者：臧文科[1] 夏瑞芳 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院 [2]山东山大鸥玛软件有限公司

出　　处：《计算机工程与应用》2012年第22期14-17,21,共5页Computer Engineering and Applications

基　　金：山东省高等学校科技计划项目(No.J12LN65);国家自然科学基金(No.61170038);山东省自然科学基金(No.ZR2011FM001)

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

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

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]