基于面上DNA计算求解最小集合覆盖问题  

DNA computing approach on surface to solve minimal set covering problem

作　　者：臧文科[1] 刘希玉[1] 刘文菊[2] 

机构地区：[1]山东师范大学管理科学与工程学院 [2]东南大学计算机科学与工程学院

出　　处：《计算机应用研究》2012年第4期1220-1222,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(61170038;60873058);山东省自然科学基金资助项目(ZR2011FM001)

摘　　要：利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。Using the gotten DNA computing mechanism and realization through DNA molecular structure,this paper proposed a DNA solution on surface for minimal set covering problem,and presented specific applications and algorithm evaluation.It listed all possible results in the surface of the calculation template,which at the same time,verified whether the results met the conditions for the realization of the strong parallelism of DNA computing.Meanwhile,when complementary oligonucleotide gather nucleotide clips occured,it should be decided whether to hybridize through the catalyst,reducing human intervention and improving efficiency.Finally,computer simulations demonstrate the feasibility of the model.

关 键 词：DNA计算 表面方式 最小集合覆盖问题 

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