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

基于环形DNA分子的一种求解最大集团的计算模型 被引量：4

原文传递
导出
摘要 文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.
作者 杨静 张成 许进 刘向荣 强小利
机构地区 北京大学信息科学技术学院
出处 《中国科学：信息科学》 CSCD 2010年第8期1078-1085,共8页 Scientia Sinica(Informationis)
基金 国家自然科学基金重点项目(批准号:60533010) 面上项目(批准号:30670540 60874036 60503002) 国家高技术研究发展计划(批准号:2006AA01Z104) 国家教育部博士点基金(批准号:20070001020) 中国博士后科学基金(批准号:20060400344)资助
关键词 DNA计算 环形DNA分子 NP完全问题 环化酶 磁珠
分类号 O242.1 [理学—计算数学]
  • 相关文献

参考文献11

  • 1LIYuan FANGChen OUYANGQi.Genetic algorithm in DNA computing: A solution to the maximal clique problem[J].Chinese Science Bulletin,2004,49(9):967-971. 被引量：8
  • 2Brun Y.Arithmetic computation in the tile assembly model:addition and multiplication. Theoretical Computer Science . 2007
  • 3C. Mao,T. H. LaBean,J. H. Relf,N. C. Seeman.Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature . 2000
  • 4Carbone,A.,Seeman,N.C.Circuits and programmable self-assembling DNA structures. Proceedings of the National Academy of Sciences of the United States of America . 2002
  • 5Adleman LM.Molecular computation of solutions to combinatorial problems. Science . 1994
  • 6Faulhammer D,Cukras AR,Lipton RJ,et al.Molecular computation: RNA solutions to chess problems. Proc.Of the National Academy of Science of USA . 2000
  • 7Head T,Rozenberg G,Bladergroen R B,et al.Computing with DNA by operating on plasmids. Biosystems Engineering . 2000
  • 8Karp RM,Miller RE,Thatcher JW.Reducibility among combinatorial problems. Complexity of Computer Computations . 1972
  • 9Bondy JA,Murty USR.Graph Theory with Applications. . 1976
  • 10Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the maximal clique problem. Science . 1997

二级参考文献10

  • 1Liu QH,Wang L,Frutos AG,et al.DNA computing on surfaces[].Nature.2000
  • 2D Faulhammer,AR Cukras,RJ Lipton,LF Landweber.Molecular computation: RNA solutions to chess problems[].Proceedings of the National Academy of Sciences of the United States of America.2000
  • 3OgiharaM,Ray A.DNAcomputingonachip[].Nature.2000
  • 4Foster. J. A.Evolutionary computation[].Nature Reviews Genetics.2001
  • 5Sakamoto K,Gouzu H,Komiya K,et al.Molecular computation by DNA hairpin formation[].Science.2000
  • 6Benenson Y,Paz-Elizur T,Adar R,et al.Programmable and autonomous computing machine made of biomolecules[].Nature.2001
  • 7Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the m axim al clique problem[].Science.1997
  • 8Ruben,A.J,Landweber,L.F.Thepast,presentandfutureofmo-lecularcomputing[].Nature Reviews MolecularCell Biology.2000
  • 9Wang,L,Hall,J.G,Lu,M.etal.ADNAcomputingreadoutop-erationbasedonstructure-specificcleavage[].Nature Biotechnology.2001
  • 10Zimmermann,K -H.Onapplyingmolecularcomputationtobi-narylinearcodes[].IEEE Transactions on Information Theory.2002

共引文献7

同被引文献38

引证文献4

二级引证文献8

中国科学：信息科学
2010年 第8期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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