期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

粘贴模型在两类特殊问题中的改进算法研究

Improved Algorithm of Sticker Model in Two Special Problem
下载PDF
导出
摘要 为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。 为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。
作者 任晓玲 白雪 刘希玉
机构地区 山东师范大学管理科学与工程学院
出处 《计算机科学》 CSCD 北大核心 2012年第S3期252-255,共4页 Computer Science
基金 国家自然科学基金(61170038) 山东省自然科学基金(ZR2011FM001) 教育部人文社会科学研究项目(12YJA630152) 山东省社会科学基金项目(11CGLJ22) 山东省高等学校科技计划项目(J12LN22 J12LN65)资助
关键词 DNA计算 粘贴模型 最小支配集 最小顶点覆盖 DNA computing Sticker model Minimum dominating set Minimum vertex cover
分类号 TP3 [自动化与计算机技术—计算机科学与技术]
  • 相关文献

参考文献11

  • 1范月科,强小利,许进.图的最大团与最大独立集粘贴DNA计算模型[J].计算机学报,2010,33(2):305-310. 被引量：10
  • 2董亚非,张家秀,殷志祥,许进.最小顶点覆盖问题的改进粘贴模型[J].电子与信息学报,2005,27(4):556-560. 被引量：9
  • 3王淑栋,刘文斌,许进.图顶点着色问题的DNA粘贴算法[J].系统工程与电子技术,2005,27(3):568-572. 被引量：13
  • 4薛圣伟..DNA计算中若干理论的研究[D].山东科技大学,2008:
  • 5Darehmiraki M,Nehi H M.Molecular solution to the 0-1 knapsack problem based on DNA computing. Journal of Applied Mathematics . 2007 被引量：1
  • 6SANCHES C A A,SOMA N Y.A polynomial-time DNA computing so-lution for the bin-packing problem. Applied Mathematics andComputation . 2009 被引量：1
  • 7Gao Lin,Xu Jin.DNA Solution of Vertex Cover Problem Based on Sticker Model. The Chinese Journal . 2002 被引量：1
  • 8Sam Roweis,Erik Winfree,Richard Burgoyne.A Sticker Based Model for DNA Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science . 1999 被引量：1
  • 9Razzazi, M,M Roayaei.Using sticker model of DNA computing to solve domatic partition,kernel and induced path problems. Information and Computation . 2011 被引量：1
  • 10Minyi Guo,Michael(Shan-Hui)Ho,Weng-Long Chang.Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing. Parallel Computing . 2004 被引量：1

二级参考文献57

  • 1Feyman R P. There's plenty of room at the bottom. California Institute of Technology Journal of Engineering and Science, 1960, 4(2): 23-36. 被引量：1
  • 2Bennett C H. On constructing a molecular computer. IBM Journal of Research and Development, 1973, 17:525-532. 被引量：1
  • 3Adleman L. Molecular computation of solutions to combinational problems. Science, 1994, 266(5178):1021-1024. 被引量：1
  • 4Lipton R J. DNA solution of hard computation problems. Science, 1995, 268(4): 542-545. 被引量：1
  • 5Roweis S, Winfree E, Burgoyne R et al. A sticker-based model for DNA computation. Journal of Computational Biology, 1998, 5(4):615-629. 被引量：1
  • 6Adleman L M. On applying molecular computation to the data encryption standard. Journal of Computational Biology, 1999, 6(1):53-63. 被引量：1
  • 7Roweis S, Winfree E, Burgoyne R et al. A sticker based architecture for DNA computation//Proceedings of the 2nd Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Princeton, 1996:1-27. 被引量：1
  • 8Ouyang Q et aI. DNA solution of the maximal clique problem. Science, 1997, 278:446-449. 被引量：1
  • 9Sakamoto et al. Molecular computation by hairpin formation. Science, 2000, 288:1223-1226. 被引量：1
  • 10Liu Q et al. DNA computing on surfaces. Nature, 2000, 403:175-179. 被引量：1

共引文献28

计算机科学
2012年 第S3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部