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

DNA缩短法计算模型求解最大独立集问题 被引量：7

原文传递
导出
摘要 提出了一种基于环形DNA缩短法的新型计算模型.该模型可以求解n个顶点m条边的图的最大独立集.算法的时间复杂度是O(n+m).随着问题规模的增大,计算所需的试管数量呈线性增长.在计算模型的生物操作中,有两个主要技术:DNA分子内环化和DNA长度逐步缩短.结合反向PCR(聚合酶链式反应),磁珠吸附和环化酶催化等多种方法,在求解步骤中,DNA分子的结构在线性双链DNA(dsDNA)、线性单链DNA(ssDNA)和环形单链DNA之间进行循环变化.利用环形DNA分子的结构特点,在计算过程中避免了DNA分子间重组.为了证实该DNA计算模型的可行性,利用其求解了一个最大独立集问题的实例.
作者 张成 杨静 许进 赵东明
机构地区 北京大学信息科学技术学院
出处 《科学通报》 EI CAS CSCD 北大核心 2009年第24期3913-3919,共7页 Chinese Science Bulletin
基金 国家自然科学基金重点项目(批准号:60533010) 国家自然科学基金面上项目(批准号:30670540 60874036 60503002) 国家高技术研究发展计划(批准号:2006AA01Z104) 教育部博士点基金(批准号:20070001020) 中国博士后科学基金(批准号:20060400344)资助项目
关键词 NP完全问题 反向PCR 线性单链DNA环化 DNA长度逐步减短法
分类号 TP301 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献21

  • 1Majid D. A new solution for maximal clique problem based sticker model. Biosystems, 2009, 95:145-149.
  • 2Lipton R J. DNA solution of hard computational problems, Science, 1995, 268:542-545.
  • 3Adleman L M. Molecular computation of solutions to combinatorial problems. Science, 1994, 266:1021-1024.
  • 4Ouyang Q, Kaplan P D, Liu S, et al. DNA solution of the maximal clique problem. Science, 1997, 278:446-449.
  • 5Liu Q H, Wang L M, Frutos A G, et al. DNA computing on surfaces. Nature, 2000, 403:175 178.
  • 6Rothemund P W K. Folding DNA to create nanoscale shapes and patterns. Nature, 2006, 440:297-302.
  • 7Mao C D, LaBean T H, ReifJ H, et al. Logical computation using algorithmic self-assembly of DNA triplecrossover molecules. Nature, 2000, 407:493-496.
  • 8Seelig G, Soloveichik D, Zhang Y D, et al. Enzyme-free nucleic acid logic circuits. Science, 2006, 314:1585-1588.
  • 9Kensaku S, Hidetaka G, Ken K, et al. Molecular computation by DNA hairpin formation. Science, 2000, 288:1223-1226.
  • 10Head T, Rozenberg G, Bladergroen R S, et al. Computing with DNA by operating on plasmids. Biosystems, 2000, 57:87-93.

二级参考文献30

  • 1董亚非,谭刚军,张社民.基于粘贴系统求解TSP问题[J].系统仿真学报,2005,17(6):1299-1302. 被引量：5
  • 2Feynmam R P. In minaturization; Gilbart, D H, Ed[M]. New York: Reinhold, 1961 282-296.
  • 3Adleman L M. Molecular computation of solutions to combinatorial problems[J].Science, 1994 , 266 (5187): 1021-1023.
  • 4Lipton R J . DNA solution of hard computation problem[J]. Science ,1995 , 268(5210):542-545.
  • 5Ouyang Q, Kaplan p D, Liu S M, et al. DNA solution of the maximal clique problem[J]. Science, 1997, 278(17):446-449.
  • 6Head T, Rozenberg G, Bladergroen R B, et al. Computing with DNA by operating on plasmids[J]. Biosysterns, 2000, 57(2):87-93.
  • 7Liu Q H , Wang L M , Fruto A C et al . DNA computing on surfaces[J].Nature,2000,403(13):175-179.
  • 8Wu H Y. An improved surface- based method for DNA computation[J]. Biosystems,2001,59 (1): 1-5.
  • 9Head T. Formal language theory and DNA: An analysis of the general capacity of specific recombinant behaviors[J]. Bull Math Biology,1987,49(6):737-759.
  • 10Roweis S, Winfree E, BurgoyneR, et al. A sticker-based model for DNA computation[J]. J Comput Biol,1998 5(4):615-629.

共引文献6

同被引文献55

引证文献7

二级引证文献13

科学通报
2009年 第24期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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