分子下推自动机理论及应用研究
|
摘要
DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来实现计算过程。自从Adleman博士1994年成功地给出用DNA计算方法求解有向图的Hamilton有向路问题以来,在短短的10多年内,DNA计算引起了学术界的广泛关注,取得了丰硕的成果。
DNA计算具有并行度高,能耗低的特点。利用DNA计算的方法构造的分子自动机是一种纳米尺度的计算机构,与传统的DNA计算的不同之处在于,它能够实现自动机的功能,在纳米尺度进行高度并行的逻辑、推理等运算。因此分子自动机提供了一种研究DNA计算和纳米计算的新思路,对其进行编码理论和运行机理上的研究将有助于开拓DNA计算新的应用领域。本文的主要工作包括:
首先分析了Yakoov等人构造的分子有限自动机,总结出该种分子有限自动机的硬件(限制性内切酶)、软件(状态转换分子)、有限自动机的状态以及字符之间的相互制约的关系。根据这一结果编制出了相应的计算机软件,该软件可以在构造该类型的分子有限自动机时,辅助进行字符编码和状态转换分子编码。在该软件的辅助下构造出状态和字符更多的分子有限自动机,其计算能力较yaakov等人设计的分子有限自动机要强。
接着提出了一种新的分子下推存储器的模型。首先利用一类特殊的限制性内切酶实现了延长DNA分子链的功能。该类限制性内切酶的特点是具有2个回文结构的识别位点,并且切割位点在2个识别位点之间。接着利用该特性构建了简单的分子存储器,研究了其存储和读取机理,并通过改进编码使这种存储器具有一定的编程能力,从而实现了按一定规律存储字符信息的下推存储器。通过分析表明,这种分子存储器的可编程能力和存储效率除了与所使用的限制性内切酶的特性有关外,还受分子存储器编码的影响,并得出了分子存储器存储效率最高或者编程能力最强的编码方式。研究表明该种下推存储器模型也可以视为一种特殊的有限自动机模型(非全状态转换),通过引入合适的调节分子,可以将其扩展为全状态转换的可编程有限自动机。这种有限自动机模型优点在于:初始DNA分子的合成较为简单;通过分子链的延长而非缩短来实现状态转换,这种状态转换机理可使计算步骤更多;最重要的是它能同时进行状态转换与数据存储,从而可以保存状态转换的历史信息。
进而提出了一种分子下推自动机的模型。计算理论表明,具有一个下推存储器的有限自动机的计算能力较单纯的有限自动机强。通过将前述分子下推存储器引入到的分子有限自动机的运算中,获得了计算能力更强的分子下推自动机。
最后讨论了分子自动机可能的应用。分子有限自动机的计算能力暂时还不能与电子计算相比,但是分子自动机是纳米计算机的一种,有其自身的优点,有望运用于一些特殊的场合。文中介绍了一些简单的理论计算的例子,同时对其可能的应用领域进行了说明。由于有限自动机可以用于信息加密和解密,因此分子有限自动机也可以实现类似的功能;而利用分子有限自动机进行疾病诊断则是一个较有前景的应用方向。可编程分子存储器可以用于存储信息,同时也可以用于构造一些分子池,文中以构造图顶点着色问题的分子池为例介绍了具体的构造方法。通过改进分子下推存储器可以构造出分子振荡器,进一步的可以作为微量检测的一种手段。
DNA computing aims at using nucleic acids for computing. Since Adleman’s successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing in 1994. In the past ten years, both the theory and the experiment method of DNA computing were improved greatly.
DNA solutions can act as billions of parallel nanoprocessors with few consume. The biomoluclar automata base on DNA computing is a kind of nano-computer. It’s difference to the original DNA computing that This DNA computing model can realized the base function of automaton.An automata made of biomolecules can combine the strongpoint of the DNA computing and electrical computing. It can also improve the practicability of DNA computer and extend the application of DNA computing.
In this paper, the restriction enzymes were analyzed for detail it infection to construct a finite automata made of biomolecules. Base on this result, a finite automaton with more state and symbol had been constructed.
Here a new finite automata made of biomolecules was described, which can be used as a programmable pushdown store. A new kind of restriction enzyme was used in this model. Which have two recognition sites and cut side between two recognitions? The basic mechanism of a simple pushdown store and an improved pushdownstore was studied. The programmable ability and the efficiency of this kind of pushdown store are influenced by the coding of the Symbol biomolucule and the restriction enzyme. Base on this result, a special enzyme and a suitable coding must be choosen to maximize the programmable ability and the efficiency of the biomolucula pushdown store. This pushdown store is also a programmable automaton. A tag molecule should be used to extend the pushdown store to a completely programmable automaton. This programmable automaton gains the advantage over the basic one. Such as simplify the coding, increase the step of computing and keep the transition information.
Bimolecular pushdown automatons can construct with a finite automaton and a pushdown store. Obviously, the pushdown automaton is more powerful than the finite automaton.
The application of bimolecular automaton is discussed in this paper too. The power of bimolecular automaton is less than electronic computer now. But the bimolecular automaton can used in some special area for it’s a nano-meter computer. Such as diagnosis and treat the disease, detect atom material and use in encrypt the information etc. It’s also can used too store some information, construct some bimolecular pool etc.
DNA计算具有并行度高,能耗低的特点。利用DNA计算的方法构造的分子自动机是一种纳米尺度的计算机构,与传统的DNA计算的不同之处在于,它能够实现自动机的功能,在纳米尺度进行高度并行的逻辑、推理等运算。因此分子自动机提供了一种研究DNA计算和纳米计算的新思路,对其进行编码理论和运行机理上的研究将有助于开拓DNA计算新的应用领域。本文的主要工作包括:
首先分析了Yakoov等人构造的分子有限自动机,总结出该种分子有限自动机的硬件(限制性内切酶)、软件(状态转换分子)、有限自动机的状态以及字符之间的相互制约的关系。根据这一结果编制出了相应的计算机软件,该软件可以在构造该类型的分子有限自动机时,辅助进行字符编码和状态转换分子编码。在该软件的辅助下构造出状态和字符更多的分子有限自动机,其计算能力较yaakov等人设计的分子有限自动机要强。
接着提出了一种新的分子下推存储器的模型。首先利用一类特殊的限制性内切酶实现了延长DNA分子链的功能。该类限制性内切酶的特点是具有2个回文结构的识别位点,并且切割位点在2个识别位点之间。接着利用该特性构建了简单的分子存储器,研究了其存储和读取机理,并通过改进编码使这种存储器具有一定的编程能力,从而实现了按一定规律存储字符信息的下推存储器。通过分析表明,这种分子存储器的可编程能力和存储效率除了与所使用的限制性内切酶的特性有关外,还受分子存储器编码的影响,并得出了分子存储器存储效率最高或者编程能力最强的编码方式。研究表明该种下推存储器模型也可以视为一种特殊的有限自动机模型(非全状态转换),通过引入合适的调节分子,可以将其扩展为全状态转换的可编程有限自动机。这种有限自动机模型优点在于:初始DNA分子的合成较为简单;通过分子链的延长而非缩短来实现状态转换,这种状态转换机理可使计算步骤更多;最重要的是它能同时进行状态转换与数据存储,从而可以保存状态转换的历史信息。
进而提出了一种分子下推自动机的模型。计算理论表明,具有一个下推存储器的有限自动机的计算能力较单纯的有限自动机强。通过将前述分子下推存储器引入到的分子有限自动机的运算中,获得了计算能力更强的分子下推自动机。
最后讨论了分子自动机可能的应用。分子有限自动机的计算能力暂时还不能与电子计算相比,但是分子自动机是纳米计算机的一种,有其自身的优点,有望运用于一些特殊的场合。文中介绍了一些简单的理论计算的例子,同时对其可能的应用领域进行了说明。由于有限自动机可以用于信息加密和解密,因此分子有限自动机也可以实现类似的功能;而利用分子有限自动机进行疾病诊断则是一个较有前景的应用方向。可编程分子存储器可以用于存储信息,同时也可以用于构造一些分子池,文中以构造图顶点着色问题的分子池为例介绍了具体的构造方法。通过改进分子下推存储器可以构造出分子振荡器,进一步的可以作为微量检测的一种手段。
DNA computing aims at using nucleic acids for computing. Since Adleman’s successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing in 1994. In the past ten years, both the theory and the experiment method of DNA computing were improved greatly.
DNA solutions can act as billions of parallel nanoprocessors with few consume. The biomoluclar automata base on DNA computing is a kind of nano-computer. It’s difference to the original DNA computing that This DNA computing model can realized the base function of automaton.An automata made of biomolecules can combine the strongpoint of the DNA computing and electrical computing. It can also improve the practicability of DNA computer and extend the application of DNA computing.
In this paper, the restriction enzymes were analyzed for detail it infection to construct a finite automata made of biomolecules. Base on this result, a finite automaton with more state and symbol had been constructed.
Here a new finite automata made of biomolecules was described, which can be used as a programmable pushdown store. A new kind of restriction enzyme was used in this model. Which have two recognition sites and cut side between two recognitions? The basic mechanism of a simple pushdown store and an improved pushdownstore was studied. The programmable ability and the efficiency of this kind of pushdown store are influenced by the coding of the Symbol biomolucule and the restriction enzyme. Base on this result, a special enzyme and a suitable coding must be choosen to maximize the programmable ability and the efficiency of the biomolucula pushdown store. This pushdown store is also a programmable automaton. A tag molecule should be used to extend the pushdown store to a completely programmable automaton. This programmable automaton gains the advantage over the basic one. Such as simplify the coding, increase the step of computing and keep the transition information.
Bimolecular pushdown automatons can construct with a finite automaton and a pushdown store. Obviously, the pushdown automaton is more powerful than the finite automaton.
The application of bimolecular automaton is discussed in this paper too. The power of bimolecular automaton is less than electronic computer now. But the bimolecular automaton can used in some special area for it’s a nano-meter computer. Such as diagnosis and treat the disease, detect atom material and use in encrypt the information etc. It’s also can used too store some information, construct some bimolecular pool etc.
引文
[1]. Leonard M Adleman. Molecular Computation of Solutions to Combinatorial Problems, Science. November 1994,266(11):1021-1023
[2]. Roweis S,Winfree E,Burgoyne R,Chelyapov,Goodman M,Rothemund P,Adleman L A . Sticker based model for DNA computation,2nd DIMACS Workshop on DNA Based Computers,Princeton, 1996,DIMACS Series,Vol.44,AMS Press,1999, 1-29
[3].许进,董亚非,魏小鹏.粘贴DNA计算机模型(I):理论.科学通报,2004,49(3): 205~212
[4].许进等.粘贴DNA计算机模型(II):应用.科学通报,2004,49(4): 299~30
[5]. Kari L. DNA computing: arrival of Biological mathematics. Math. Intelligencer,1997,19(2): 9-22
[6]. Praun G,Rozenberg G,Salomaa A. DNA computing-New Computing Paradigms. Springer,Berlin,1998
[7]. Sakamoto K,Gouzu H,Komiya K,et al. Molecular computation by DNA hairpin formation. Science,2000,288:1223~1226;
[8]. Head T,Rozenberg G,Bladergroen R B,Breek C K D,Lommerse P H M,Spaink H P. Computing with DNA by operating on plasmids. BioSystems,2000,57:87-93
[9].高琳、马润年.基于质粒求解最大匹配问题的DNA算法.生物化学与生物物理学进展,2002,29(5): 820-823
[10].马润年、张强、高琳.图的最大权图的DNA计算.电子学报,2004, 32(1): 1-16
[11]. G. P?un, Computing with membranes, Journal of Computer and System Sciences, 61(1)(2000), 108-143. (first circulated at TUCS Research Report No 208, November 1998).
[12]. Bennett C. H.: On Constructing a Molecular Computer. IBM Journal of Research and Development,17 (1973) 525~532
[13]. Benenson Y,Paz-Elizur T,Adar R,et al. Programmable and autonomous computing machine made of bimoleculars, Nature, 2001, 414(6862): 430-434
[14]. Benenson Y , Rivka Adar , Paz2Elizur Tamar , et al . DNA molecule provides acomputing machine with both data and fuel [J ] . PNAS , 2003 ,100 (5) :2191—2196.
[15]. Shi, XL, Li, X., Zhang, Z., et al.: Improve capability of DNA automaton: DNA automaton with three internal states and tape head move in two directions. LECT NOTES COMPUT SC 3645 (2005) 71-79
[16]. Shi Xiaolong, Pan linqiang, Xu Jin General DNA Automaton Model with R/W Tape LECT NOTES COMPUT SC 4115 (2006) 258-266
[17]. Zheng Zhang, Jin Xu, Jie Liu, Linqiang Pan Programmable Pushdown Store Base on DNA Computing: LECT NOTES COMPUT SC 4115 (2006) 286-293
[18]. Benenson Y , Binyamin Gil,et al. An autonomous molecular computer for logical control of gene expression Nature, 2003, 429: 423-429
[19]. Richard J Lipton. DNA Solution of Hard Computational Problems. Science,April 1995,268(28):542-545
[20]. Qi Ouyang,Peter D.Kaplan,Shumao Liu,Albert Libchaber. DNA Solution of the Maximal Clique Problem. Science,October 1997,278(17): 446-449
[21]. Yin Zhixiang,Zhang fengyue,Xu Jin. A Chinese Postman problem based on DNA Computing. Journal of Chemical Information and Computer Sciences,2002(2):42(2): 222-224
[22]. Yachun Liu,Jin Xu,Linqiang Pan,and Shiying Wang,DNA Solution of a Graph Coloring Problem,Journal of Chemical Information and Computer Science,2002,42(3): 524-528
[23]. Liu Wenbin,Xu Jin. A DNA Algorithm for the Graph Coloring Problem. Journal of Chemical Information and Computers,2002,42: 1176-1178
[24]. Pan Linqiang, Liu Guangwu, Xu Jin, Liu Yachun. Solid phase based DNA solution of the coloring problem. Progress in Natural Science, 2004, 14(5): 104-107
[25].王淑栋,刘文斌,许进.图顶点着色问题的DNA粘贴算法.系统工程与电子技术, 2005, 27(3): 568-572
[26].许进,强小利,方刚,周康.一种图顶点着色DNA计算机模型.科学通报, 2006, 51(4): 480-487
[27]. Xu Jin, QIANG Xiaoli, Fang Gang, Zhou kang. A DNA computer model for solving vertex coloring problem.科学通报(英文版), 2006, 51(20): 2541-2549
[28]. Yin Zhixiang,Zhang Fengyue,Xu Jin. The General Form of 0-1 ProgrammingProblem Based on DNA Computing. Biosystems,200370(1) : 73-79
[29].殷志祥,石晓龙,徐涛,许进. 0-1整数规划问题的半自动化DNA计算模型.生物信息学, 2006, 4(3): 113-116
[30]. Fengyue Zhang, Zhixiang Yin, Bo Liu, Jin Xu. DNA computation model to solve 0–1 programming problem. BioSystems, 2004, 74: 9-14
[31]. Yin Zhixiang, Cui Jianzhong, Shi Xiaolong, Shi Xiaohong, Pan Linqiang, Xu Jin. The Semi- roboticized DNA Computing Model of The 0-1 Integer Programming Problem. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006, 1: 3805-3809
[32].董亚非,张家秀,殷志祥,许进.最小顶点覆盖问题的改进粘贴模型.电子与信息学报, 2005, 27(4): 556-560
[33].王淑栋,刘文斌,许进.图的最小顶点覆盖问题的质粒DNA计算模型.华中科技大学学报(自然科学版), 2004, 32(11): 59-61
[34].高琳,许进.最小顶点覆盖问题的DNA分子算法.系统工程与电子技术, 2004, 26(4): 544-548
[35]. Yin Zhixiang, Cui Jianzhong, Shi Xiaohong, Pan Linqiang. The semi-automated DNA computing model for solving the satisfiability problem. International Journal of Computer Science and Network Security, 2006, 6(1): 163-167
[36]. LIU wenbin, ZHUO xiangou,GAO Lin. Solving the 3-SAT Based on DNA Evolutionary Algorithm. Chinese Journal of Electronics , 2006, 15(3): 437-440
[37]. YIN Zhixiang, Pan Linqiang, SHI Xiaohong. DNA algorithm of minimal spanning tree. Proceedings of SPIE , 2006, 6358: 1-5
[38]. Frutos A G et al. Demonstration of a word design strategy for DNA omputing on surfaces. Nucl. Acid. Res. 1997,25:4748-4757
[39]. Smith L M. A surface-based approach to DNA computation. J. Comput. Biol.,1998,5:255-267
[40]. Liu Qinghua,Liman Wang,Anthony G Frutos,Anne E. Condon,Robert M Corn,Lloyd M Smith. DNA computing on surfaces. Nature,2000,403(13): 175-178
[41]. Karl-Heinz Zimmermann. Efficient DNA sticker algorithms for NP-complete graph problems. Computer Physics Communications, 2002, 144: 297-309
[42]. Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002,11(2):280-284
[43]. Ravinderjit S. Braich, Nickolas Chelyapov, Cliff Johnson, Paul W. K. Rothemund, Leonard Adleman. Solution of a 20-variable 3-SAT problem on a DNA computer.
[44].王淑栋.四类DNA计算模型中一些理论与应用的研究.华中科技大学博士学位论文, 2003, 12
[45].潘林强,董亚非,许进等.求解接点网络问题的DNA算法.华中科技大学学报, 2003, 31(3): 69~71
[46]. Mancini M, Hadchouel M, Davis HL et al . DNA2mediated immunization in a transgenic mouse model of the hepatitis B surface antigen chronic carrier state. Proc Nat1 Acad Sci USA ,1996 ,93(22) :12496
[47]. Davis HL , Michel ML , Whalen RG. DNA2based immunization induces continuous secretion of hepatitis B surface antigen and high levels of circulating antibody. Hum Mol Genet , 1993 ,2(11) :1847
[48]. Chow YH, Huang WL , Chi WK et al . Improvement of hepatitis B virus DNA vaccines by plasmids coexpressing hepatitis B surface antigen and interleukin22. J Vi2 rol , 1997 ,71(1) :169
[49]. Oka Y, Akbar SM, Horiike N et al . Mechanismand therapeutic potential of DNA2based immunization against the envelope proteins of hepatitis B virus in normal and transgenic mice. Immunology ,2001 ,103(1) :90
[50]. Thermet A , Rollier C, Zoulim et al . Progress in DNA vaccine for prophylaxis and therapy of hepatitis B. Vaccine , 2003 ,21(728) :659
[51]. Jack S Cohen. Oligodeoxynucleocides, Antisense linhilistors of Gene Expression, Topics in Molecular and Structural Biology Volume 12,Macmilan Press, Scientific and Medical 1989
[52]. Sarin P S, Agrawal S Cieira et all. Ptnm al amol Sca Usa,1988,85,7448
[53]. Matsukura M zon G, Shinozuka K et al.Gene 1988,72:343
[54]. T.Head, Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors, Bulletin of Mathematical Biology, 49 (1987), 737--759.
[55]. Lipton, R. J. DNA solution of hard computational problem. Science 268, 542-545 (1995).
[56]. Landweber, L. F., Lipton, R. J. & Rabin, M. O. in DNA Based Computers III: DIMACS Workshop, June 23-27, 1997, University of Pennsylvania (eds Rubin, H. &Wood, D. H.) 161-172 (American Mathematical Society, Providence, Rhode Island, 1997).
[57]. Faulhammer, D., Cukras, A. R., Lipton, R. J. & Landweber, L. F. Molecular computation: RNA solutions to chess problems. Proc. Natl Acad. Sci. USA 97, 1385-1389 (2000).
[58]. Ruben, A. J. & Landweber, L. F. The past, present and future of molecular computing. Nature Rev. Mol.Cell Biol. 1, 69-72 (2000).
[59]. Yurke B., Andrew J. Turbereld, Allen P. Mills Jr, Friedrich C. Simmel & Jennifer L. Neumann:
[60]. A DNA-fuelled molecular machine made of DNA. Nature, 10 (2000) 605~608
[61]. Paul Wilhelm, Karl Rothemund: A DNA and restriction enzyme implementation of Turing machine. http://www.ugcs.caltech.edu.~pwkr /oett.html
[62]. Smith W., Scheweitzer A.: DNA computer in Vitro and Vivo. DIMACS workshop on DNA based computing. Princeton, 1995
[63]. Beaver D.: Computing with DNA. Journal of computation biology, 3 (1996) 254~ 257
[64]. Erik Winfree: On the computational power of DNA annealing and ligation, Technical Report, California Institute of Technology, USA, 1995
[65]. Erik Winfree, et al.: Design and self-assembly of two-dimensional DNA crystals, Nature, 394 (1998) 539-544
[66]. Khodor, J. & Gifford, D. K. Design and implementation of computational systems based on programmed mutagenesis. Biosystems 52, 93–97 (1999).
[67]. Mao, C., LaBean, T. H., Reif, J. H. & Seeman, N. C. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407, 493–496 (2000).
[68]. Lin Gao, Wenbin Liu, Weifeng Li, David K. Y. Chiu. Self-Assembly Based Models and Algorithms for DNA Computation. Int. J. of Unconventional Computing, 2006, 2: 267-280
[69]. Sakamoto, K. et al. State transitions by molecules. Biosystems 52, 81–91 (1999).
[70]. Rabin, M. O. Probabilistic automata. Inform. Contr. 6, 230–245 (1963).
[71]. Bar-Ziv, R., Tlusty, T. & Libchaber, A. Protein-DNA computation by stochastic assembly cascade. Proc. Natl Acad. Sci. USA 99, 11589–11592 (2002).
[72]. Sidransky, D. Emerging molecular markers of cancer. Nature Rev. Cancer 2, 210–219 (2002).
[73]. Pedersen, N. et al. Transcriptional gene expression profiling of small cell lung cancer cells. Cancer Res.63, 1943–1953 (2003).
[74]. Dhanasekaran, S. M. et al. Delineation of prognostic biomarkers in prostate cancer. Nature 412,822–826 (2001).
[75]. Takahashi, T. et al. The p53 gene is very frequently mutated in small-cell lung cancer with a distinct nucleotide substitution patter. Oncogene 6, 1775–1778 (1991).
[76]. Thorns, C., Gaiser, T., Lange, K., Metz, H. & Feller, A. C. cDNA arrays: Gene expression profiles of Hodgkin’s disease and anaplastic large cell lymphoma cell lines. Pathol. Int. 52, 578–585 (2002).
[77]. Ledley, R. S. & Lusted, L. B. Reasoning foundation of medical diagnosis. Science 130, 9–21 (1959).
[78]. Cui Jianzhong, Yin Zhixiang, Wang Wei, Shi Xiaohong, Pan Linqiang. Towards Reliable Simulation of Bounded Fan-in Boolean Circuits Using Molecular Beacon. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006, 1: 3910-3914
[79]. Holzer, S., Fremgen, A. M., Hundahl, S. A. & Dudeck, J. Analysis of medical-decision making and the use of standards of care in oncology. J. Am. Med. Inf. Assoc. (Suppl. S) 364–368 (2000).
[80]. Capoulade, C. et al. Apoptosis of tumoral and nontumoral lymphoid cells is induced by both mdm2 and p53 antisense oligodeoxynucleotides. Blood 97, 1043–1049 (2001).
[81]. Holmlund, J. T. Applying antisense technology. Ann. NY Acad. Sci. 1002, 244–251 (2003).
[82]. Klasa, R. J., Gillum, A. M., Klem, R. E. & Frankel, S. R. Oblimersen Bcl-2 antisense: Facilitating apoptosis in anticancer treatment. Antisense Nucleic Acid Drug Dev. 12, 193–213 (2002).
[83]. Yurke, B., Turberfield, A. J., Mills, A. P., Simmel, F. C. & Neumann, J. L. A DNA-fuelled molecular machine made of DNA. Nature 406, 605–608 (2000).
[84]. Stojanovic, M. N. & Stefanovic, D. A deoxyribozyme-based molecular automaton. Nature Biotechnol. 21, 1069–1074 (2003).
[85]. Balzani, V., Credi, A. & Venturi, M. Molecular logic circuits. Chemphyschem 4, 49–59 (2003).
[86]. Wenbin Liu, Xiaohong Shi, Shemin Zhang, Xiangrong Liu, Jin Xu. A new DNA computing model for the NAND gate based on induced hairpin formation. BioSystems, 2004, 77: 87-92
[2]. Roweis S,Winfree E,Burgoyne R,Chelyapov,Goodman M,Rothemund P,Adleman L A . Sticker based model for DNA computation,2nd DIMACS Workshop on DNA Based Computers,Princeton, 1996,DIMACS Series,Vol.44,AMS Press,1999, 1-29
[3].许进,董亚非,魏小鹏.粘贴DNA计算机模型(I):理论.科学通报,2004,49(3): 205~212
[4].许进等.粘贴DNA计算机模型(II):应用.科学通报,2004,49(4): 299~30
[5]. Kari L. DNA computing: arrival of Biological mathematics. Math. Intelligencer,1997,19(2): 9-22
[6]. Praun G,Rozenberg G,Salomaa A. DNA computing-New Computing Paradigms. Springer,Berlin,1998
[7]. Sakamoto K,Gouzu H,Komiya K,et al. Molecular computation by DNA hairpin formation. Science,2000,288:1223~1226;
[8]. Head T,Rozenberg G,Bladergroen R B,Breek C K D,Lommerse P H M,Spaink H P. Computing with DNA by operating on plasmids. BioSystems,2000,57:87-93
[9].高琳、马润年.基于质粒求解最大匹配问题的DNA算法.生物化学与生物物理学进展,2002,29(5): 820-823
[10].马润年、张强、高琳.图的最大权图的DNA计算.电子学报,2004, 32(1): 1-16
[11]. G. P?un, Computing with membranes, Journal of Computer and System Sciences, 61(1)(2000), 108-143. (first circulated at TUCS Research Report No 208, November 1998).
[12]. Bennett C. H.: On Constructing a Molecular Computer. IBM Journal of Research and Development,17 (1973) 525~532
[13]. Benenson Y,Paz-Elizur T,Adar R,et al. Programmable and autonomous computing machine made of bimoleculars, Nature, 2001, 414(6862): 430-434
[14]. Benenson Y , Rivka Adar , Paz2Elizur Tamar , et al . DNA molecule provides acomputing machine with both data and fuel [J ] . PNAS , 2003 ,100 (5) :2191—2196.
[15]. Shi, XL, Li, X., Zhang, Z., et al.: Improve capability of DNA automaton: DNA automaton with three internal states and tape head move in two directions. LECT NOTES COMPUT SC 3645 (2005) 71-79
[16]. Shi Xiaolong, Pan linqiang, Xu Jin General DNA Automaton Model with R/W Tape LECT NOTES COMPUT SC 4115 (2006) 258-266
[17]. Zheng Zhang, Jin Xu, Jie Liu, Linqiang Pan Programmable Pushdown Store Base on DNA Computing: LECT NOTES COMPUT SC 4115 (2006) 286-293
[18]. Benenson Y , Binyamin Gil,et al. An autonomous molecular computer for logical control of gene expression Nature, 2003, 429: 423-429
[19]. Richard J Lipton. DNA Solution of Hard Computational Problems. Science,April 1995,268(28):542-545
[20]. Qi Ouyang,Peter D.Kaplan,Shumao Liu,Albert Libchaber. DNA Solution of the Maximal Clique Problem. Science,October 1997,278(17): 446-449
[21]. Yin Zhixiang,Zhang fengyue,Xu Jin. A Chinese Postman problem based on DNA Computing. Journal of Chemical Information and Computer Sciences,2002(2):42(2): 222-224
[22]. Yachun Liu,Jin Xu,Linqiang Pan,and Shiying Wang,DNA Solution of a Graph Coloring Problem,Journal of Chemical Information and Computer Science,2002,42(3): 524-528
[23]. Liu Wenbin,Xu Jin. A DNA Algorithm for the Graph Coloring Problem. Journal of Chemical Information and Computers,2002,42: 1176-1178
[24]. Pan Linqiang, Liu Guangwu, Xu Jin, Liu Yachun. Solid phase based DNA solution of the coloring problem. Progress in Natural Science, 2004, 14(5): 104-107
[25].王淑栋,刘文斌,许进.图顶点着色问题的DNA粘贴算法.系统工程与电子技术, 2005, 27(3): 568-572
[26].许进,强小利,方刚,周康.一种图顶点着色DNA计算机模型.科学通报, 2006, 51(4): 480-487
[27]. Xu Jin, QIANG Xiaoli, Fang Gang, Zhou kang. A DNA computer model for solving vertex coloring problem.科学通报(英文版), 2006, 51(20): 2541-2549
[28]. Yin Zhixiang,Zhang Fengyue,Xu Jin. The General Form of 0-1 ProgrammingProblem Based on DNA Computing. Biosystems,200370(1) : 73-79
[29].殷志祥,石晓龙,徐涛,许进. 0-1整数规划问题的半自动化DNA计算模型.生物信息学, 2006, 4(3): 113-116
[30]. Fengyue Zhang, Zhixiang Yin, Bo Liu, Jin Xu. DNA computation model to solve 0–1 programming problem. BioSystems, 2004, 74: 9-14
[31]. Yin Zhixiang, Cui Jianzhong, Shi Xiaolong, Shi Xiaohong, Pan Linqiang, Xu Jin. The Semi- roboticized DNA Computing Model of The 0-1 Integer Programming Problem. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006, 1: 3805-3809
[32].董亚非,张家秀,殷志祥,许进.最小顶点覆盖问题的改进粘贴模型.电子与信息学报, 2005, 27(4): 556-560
[33].王淑栋,刘文斌,许进.图的最小顶点覆盖问题的质粒DNA计算模型.华中科技大学学报(自然科学版), 2004, 32(11): 59-61
[34].高琳,许进.最小顶点覆盖问题的DNA分子算法.系统工程与电子技术, 2004, 26(4): 544-548
[35]. Yin Zhixiang, Cui Jianzhong, Shi Xiaohong, Pan Linqiang. The semi-automated DNA computing model for solving the satisfiability problem. International Journal of Computer Science and Network Security, 2006, 6(1): 163-167
[36]. LIU wenbin, ZHUO xiangou,GAO Lin. Solving the 3-SAT Based on DNA Evolutionary Algorithm. Chinese Journal of Electronics , 2006, 15(3): 437-440
[37]. YIN Zhixiang, Pan Linqiang, SHI Xiaohong. DNA algorithm of minimal spanning tree. Proceedings of SPIE , 2006, 6358: 1-5
[38]. Frutos A G et al. Demonstration of a word design strategy for DNA omputing on surfaces. Nucl. Acid. Res. 1997,25:4748-4757
[39]. Smith L M. A surface-based approach to DNA computation. J. Comput. Biol.,1998,5:255-267
[40]. Liu Qinghua,Liman Wang,Anthony G Frutos,Anne E. Condon,Robert M Corn,Lloyd M Smith. DNA computing on surfaces. Nature,2000,403(13): 175-178
[41]. Karl-Heinz Zimmermann. Efficient DNA sticker algorithms for NP-complete graph problems. Computer Physics Communications, 2002, 144: 297-309
[42]. Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002,11(2):280-284
[43]. Ravinderjit S. Braich, Nickolas Chelyapov, Cliff Johnson, Paul W. K. Rothemund, Leonard Adleman. Solution of a 20-variable 3-SAT problem on a DNA computer.
[44].王淑栋.四类DNA计算模型中一些理论与应用的研究.华中科技大学博士学位论文, 2003, 12
[45].潘林强,董亚非,许进等.求解接点网络问题的DNA算法.华中科技大学学报, 2003, 31(3): 69~71
[46]. Mancini M, Hadchouel M, Davis HL et al . DNA2mediated immunization in a transgenic mouse model of the hepatitis B surface antigen chronic carrier state. Proc Nat1 Acad Sci USA ,1996 ,93(22) :12496
[47]. Davis HL , Michel ML , Whalen RG. DNA2based immunization induces continuous secretion of hepatitis B surface antigen and high levels of circulating antibody. Hum Mol Genet , 1993 ,2(11) :1847
[48]. Chow YH, Huang WL , Chi WK et al . Improvement of hepatitis B virus DNA vaccines by plasmids coexpressing hepatitis B surface antigen and interleukin22. J Vi2 rol , 1997 ,71(1) :169
[49]. Oka Y, Akbar SM, Horiike N et al . Mechanismand therapeutic potential of DNA2based immunization against the envelope proteins of hepatitis B virus in normal and transgenic mice. Immunology ,2001 ,103(1) :90
[50]. Thermet A , Rollier C, Zoulim et al . Progress in DNA vaccine for prophylaxis and therapy of hepatitis B. Vaccine , 2003 ,21(728) :659
[51]. Jack S Cohen. Oligodeoxynucleocides, Antisense linhilistors of Gene Expression, Topics in Molecular and Structural Biology Volume 12,Macmilan Press, Scientific and Medical 1989
[52]. Sarin P S, Agrawal S Cieira et all. Ptnm al amol Sca Usa,1988,85,7448
[53]. Matsukura M zon G, Shinozuka K et al.Gene 1988,72:343
[54]. T.Head, Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors, Bulletin of Mathematical Biology, 49 (1987), 737--759.
[55]. Lipton, R. J. DNA solution of hard computational problem. Science 268, 542-545 (1995).
[56]. Landweber, L. F., Lipton, R. J. & Rabin, M. O. in DNA Based Computers III: DIMACS Workshop, June 23-27, 1997, University of Pennsylvania (eds Rubin, H. &Wood, D. H.) 161-172 (American Mathematical Society, Providence, Rhode Island, 1997).
[57]. Faulhammer, D., Cukras, A. R., Lipton, R. J. & Landweber, L. F. Molecular computation: RNA solutions to chess problems. Proc. Natl Acad. Sci. USA 97, 1385-1389 (2000).
[58]. Ruben, A. J. & Landweber, L. F. The past, present and future of molecular computing. Nature Rev. Mol.Cell Biol. 1, 69-72 (2000).
[59]. Yurke B., Andrew J. Turbereld, Allen P. Mills Jr, Friedrich C. Simmel & Jennifer L. Neumann:
[60]. A DNA-fuelled molecular machine made of DNA. Nature, 10 (2000) 605~608
[61]. Paul Wilhelm, Karl Rothemund: A DNA and restriction enzyme implementation of Turing machine. http://www.ugcs.caltech.edu.~pwkr /oett.html
[62]. Smith W., Scheweitzer A.: DNA computer in Vitro and Vivo. DIMACS workshop on DNA based computing. Princeton, 1995
[63]. Beaver D.: Computing with DNA. Journal of computation biology, 3 (1996) 254~ 257
[64]. Erik Winfree: On the computational power of DNA annealing and ligation, Technical Report, California Institute of Technology, USA, 1995
[65]. Erik Winfree, et al.: Design and self-assembly of two-dimensional DNA crystals, Nature, 394 (1998) 539-544
[66]. Khodor, J. & Gifford, D. K. Design and implementation of computational systems based on programmed mutagenesis. Biosystems 52, 93–97 (1999).
[67]. Mao, C., LaBean, T. H., Reif, J. H. & Seeman, N. C. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407, 493–496 (2000).
[68]. Lin Gao, Wenbin Liu, Weifeng Li, David K. Y. Chiu. Self-Assembly Based Models and Algorithms for DNA Computation. Int. J. of Unconventional Computing, 2006, 2: 267-280
[69]. Sakamoto, K. et al. State transitions by molecules. Biosystems 52, 81–91 (1999).
[70]. Rabin, M. O. Probabilistic automata. Inform. Contr. 6, 230–245 (1963).
[71]. Bar-Ziv, R., Tlusty, T. & Libchaber, A. Protein-DNA computation by stochastic assembly cascade. Proc. Natl Acad. Sci. USA 99, 11589–11592 (2002).
[72]. Sidransky, D. Emerging molecular markers of cancer. Nature Rev. Cancer 2, 210–219 (2002).
[73]. Pedersen, N. et al. Transcriptional gene expression profiling of small cell lung cancer cells. Cancer Res.63, 1943–1953 (2003).
[74]. Dhanasekaran, S. M. et al. Delineation of prognostic biomarkers in prostate cancer. Nature 412,822–826 (2001).
[75]. Takahashi, T. et al. The p53 gene is very frequently mutated in small-cell lung cancer with a distinct nucleotide substitution patter. Oncogene 6, 1775–1778 (1991).
[76]. Thorns, C., Gaiser, T., Lange, K., Metz, H. & Feller, A. C. cDNA arrays: Gene expression profiles of Hodgkin’s disease and anaplastic large cell lymphoma cell lines. Pathol. Int. 52, 578–585 (2002).
[77]. Ledley, R. S. & Lusted, L. B. Reasoning foundation of medical diagnosis. Science 130, 9–21 (1959).
[78]. Cui Jianzhong, Yin Zhixiang, Wang Wei, Shi Xiaohong, Pan Linqiang. Towards Reliable Simulation of Bounded Fan-in Boolean Circuits Using Molecular Beacon. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006, 1: 3910-3914
[79]. Holzer, S., Fremgen, A. M., Hundahl, S. A. & Dudeck, J. Analysis of medical-decision making and the use of standards of care in oncology. J. Am. Med. Inf. Assoc. (Suppl. S) 364–368 (2000).
[80]. Capoulade, C. et al. Apoptosis of tumoral and nontumoral lymphoid cells is induced by both mdm2 and p53 antisense oligodeoxynucleotides. Blood 97, 1043–1049 (2001).
[81]. Holmlund, J. T. Applying antisense technology. Ann. NY Acad. Sci. 1002, 244–251 (2003).
[82]. Klasa, R. J., Gillum, A. M., Klem, R. E. & Frankel, S. R. Oblimersen Bcl-2 antisense: Facilitating apoptosis in anticancer treatment. Antisense Nucleic Acid Drug Dev. 12, 193–213 (2002).
[83]. Yurke, B., Turberfield, A. J., Mills, A. P., Simmel, F. C. & Neumann, J. L. A DNA-fuelled molecular machine made of DNA. Nature 406, 605–608 (2000).
[84]. Stojanovic, M. N. & Stefanovic, D. A deoxyribozyme-based molecular automaton. Nature Biotechnol. 21, 1069–1074 (2003).
[85]. Balzani, V., Credi, A. & Venturi, M. Molecular logic circuits. Chemphyschem 4, 49–59 (2003).
[86]. Wenbin Liu, Xiaohong Shi, Shemin Zhang, Xiangrong Liu, Jin Xu. A new DNA computing model for the NAND gate based on induced hairpin formation. BioSystems, 2004, 77: 87-92