《计算机应用研究》|Application Research of Computers

一种广义分子计算模型及其在NP问题中的应用

Generalized molecular computational model for NP problems

免费全文下载 (已被下载 次)  
获取PDF全文
作者 李艳梅,余文,宁建国
机构 1.北京理工大学 机电学院 爆炸科学与技术国家重点实验室,北京 100081;2.北京邮电大学 计算机学院 智能通信软件多媒体北京市重点实验室,北京 100876
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2014)11-3353-04
DOI 10.3969/j.issn.1001-3695.2014.11.035
摘要 目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题(SAT),比现有分子计算模型在计算准确性和通用性上存在明显优势。
关键词 广义分子计算模型;图灵机;SAT问题
基金项目 国家自然科学基金资助项目(11272066)
本文URL http://www.arocmag.com/article/01-2014-11-035.html
英文标题 Generalized molecular computational model for NP problems
作者英文名 LI Yan-mei, YU Wen, NING Jian-guo
机构英文名 1. State Key Laboratory of Explosive Science & Technology, College of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China; 2. Beijing Key Laboratory of Intelligent Telecommunication Software & Multimedia, College of Computer, Beijing University of Posts & Telecommunications, Beijing 100876, China
英文摘要 DNA computing is a novel parallel computation paradigm. Existing models were mostly based on molecular biological technology and different from the traditional computers, they were less universal than traditional ones, so the algorithm or a DNA computer just for one kind of problem could not be transplanted to solve other problems without any modification. This paper put forward a new generalized molecular computational model(designated by GMCM) based on Turing machine, which did not rely on biotechnology and included an ordinary single tape Turing machine, a finite write-only tape, and a special working tape. Through the topological mapping between the write-only tape and the wokring tape, it could realize read or write in parallel. Validation test proves that GMCM can solve the satisfiability problem in a polynomial time and has obvious advantages compared with exsiting DNA computer on computation accuracy and universal property.
英文关键词 generalized molecular computational model; Turing machine; satisfiability problem
参考文献 查看稿件参考文献
  [1] FEYNMAN R P. There’s plenty of room at the bottom[J] . California Institute of Technology Journal of Engineering and Science, 1960, 4(2):23-36.
[2] BENNETT C H. Logical reversibility of computation[J] . IBM Journal of Research and Development, 1973, 17(6):525-532.
[3] ADLEMAN L. Molecular computation of solutions to combinational problems[J] . Science, 1994, 266(5178):1021-1024.
[4] HEAD T. Formal language theory and DNA:an analysis of the generative capacity of specific recombinant behaviors[J] . Bulletin of Mathe-matical Biology, 1987, 49(6):737-759.
[5] FREUND R, KARI L, PAUN G H. DNA computing based on splicing:the existence of universal computers[J] . Theory of Computing Systems, 1999, 32(1):69-112.
[6] BENENSON Y, PAZ-ELIZUR T, ADAR R, et al. Programmable and autonomous computing machine made of biomolecules[J] . Nature, 2001, 414(22):430-434.
[7] LILA K, STEFFEN K. Deciding whether a regualar language if gene-rated by splicing system[C] //Proc of the 18th International Confe-rence on DNA Computing and Molecular Programming. 2012:98-109.
[8] ROWEIS S, WINFREE E, BURQOVNE R, et al. A sticker-based model for DNA computation[J] . Journal of Computational Biology, 1998, 5(4):615-629 .
[9] SAKAMOTO K, GOUZU H, KOMIYA K, et al. Molecular computation by DNA hairpin formation[J] . Science, 2000, 288(5469):1223-1226.
[10] HEAD T, ROZENBERG G, BLADERGROEN R S, et al. Computing with DNA by operating on plasmids[J] . Biosystems, 2000, 57(2):87-93.
[11] SEELIG G, SOLOVEICHIK D, ZHANG D Y, et al. Enzyme-free nucleic acid logic circuits[J] . Science, 2006, 314(5805):1585-1588.
[12] SHARMA J, CHHABRA R, CHENG An-chi, et al. Control of self-assembly of DNA tubules through integration of gold nanoparticles[J] . Science, 2009, 323(5910):112-116.
[13] ALDAYE F A, SLEIMAN H F. Sequential self-assembly of a DNA hexagon as a template for the organization of gold nanoparticles[J] . Angewanalte Chemie International Edition, 2006, 45(14):2204-2209.
[14] ALDAYE F A, SLEIMAN H F. Dynamic DNA templates for discrete gold nanoparticle assemblies control of geometry, modularity, write erase and structural switching[J] . Journal of the American Chemical Society, 2007, 129(14):4130-4131.
[15] MASTROIANNI A J, CLARIDGE S A, ALIVISATOS A P. Pyramidal and chiral groupings of gold nanocrystals assembled using DNA scaffolds[J] . Journal of the American Chemical Society, 2009, 131(24):8455-8459.
[16] QIAN Lu-lu, WINFREE E. Scaling up digital circuit computation with DNA strand displacement cascades[J] . Science, 2011, 332(6034):1196-1201.
[17] QIAN Lu-lu, WINFREE E, BRUCK J. Neural network computation with DNA strand displacement cascades[J] . Nature, 2011, 475(7356):368-372.
[18] ZHANG Cheng, YANG Jing, XU Jin. Molecular logic computing model based on self-assembly of DNA nanoparticles[J] . Chinese Science Bulletin, 2011, 56(33):3566-3571.
[19] LIU Qing-hua, WANG Li-man, FRUTIONS A G, et al. DNA computing on surfaces[J] . Nature, 2000, 403(13):175-178.
[20] BRAICH R S, CHELYAPOV N, JOHNSON C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[J] . Science, 2002, 296(5567):499-502.
[21] YIN Zhi-xiang, CUI Jian-zhong, ZHI Ling-ying, et al. Molecular beacon based DNA computing model for general satisfiability problem[J] . Chinese Journal of Computers, 2008, 31(12):2200- 2206.
[22] ZHOU Kang, WEI Chuan-jia, LIU Shuo, et al. Closed circle DNA algorithm for SAT problem[J] . Journal of Huazhong University of Science and Technologh, 2009, 37(7):75-78.
[23] XIAO Jian-hua, XU Jin. The DNA computatioin model based on giant magnetoresistance for SAT problem[J] . Chinese Journal of Computers, 2013, 36(4):829-835. [24] YU Wen, GAO Li, ZHENG Wei-min, et al. A generalized Turing machine based on molecular computation[J] . Computer Science, 2006, 33(7):362-365.
收稿日期 2013/11/22
修回日期 2013/12/29
页码 3353-3356
中图分类号 TP301
文献标志码 A