图顶点着色DNA计算模型及实验研究
|
摘要
DNA计算是以DNA分子作为“数据”,以生化反应作为“信息处理工具”的一种新颖计算模式。由于其高度并行性、海量存储能力、低能耗等优点,DNA计算成为众多学者关注的焦点。近年来,许多研究成果已经提高了它的性能并增加了它的可行性。但是,DNA计算尚未成熟。关于DNA计算理论和技术上的进一步研究都具有重要的科学意义。
图顶点着色问题存在于丰富的科学和工程应用中,如工序问题、排课表问题、物资储存问题等等,但它却是众所周知的NP-完全问题。本文针对这一具体问题,结合分子生物学的研究方法和实验技术,旨在建立自动化程度较高的,可用于求解较大规模问题的DNA计算模型,研究探讨了四种解决图顶点着色的DNA计算模型的可行性及优缺点,对每个DNA计算模型给出了具体的编码条件及相应的编码,及实现DNA计算模型的生化操作的实验步骤,并对一些模型给出了详细的实验验证。主要工作如下:
文章首先基于杂交反应提出一种枚举型的DNA计算模型。在该模型中,提出了具体编码方案,并利用DNA自动合成仪合成初始解空间,然后利用杂交反应和聚合酶链式反应来求解问题。文章以具有5个顶点图为例对该模型进行了生化实验验证。实验结果表明,该模型能有效求解图顶点着色问题。
为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文章提出一种改进的枚举型DNA计算模型。在该模型中,利用双编码法对图顶点着色这一问题进行编码,利用酶切反应和聚合酶链式反应对问题进行求解。实例分析表明,该模型具有编码量少、求解过程简单的优点,尤其是因为该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作。
解空间指数爆炸问题是阻碍DNA计算发展的最大瓶颈。针对这一问题,文章提出一种非枚举型DNA计算模型。在模型中,首先对编码方案和初始解空间构建进行了优化,构建了非枚举型的初始解空间,删除了大量非解,提高计算效率;然后利用聚合酶链式反应实现非解删除的操作,并使用DNA测序技术读取最终解;文章以一个含有12个顶点的图为例对该模型进行了实验验证。实验结果表明,该模型有效可靠,可以较好的克服DNA计算中的解空间指数爆炸问题。
为建立可用于求解大规模图顶点着色问题的DNA计算模型,文章在非枚举型DNA计算模型的基础上,引入并行处理的思想,建立了一种并行型DNA计算模型。在模型中,给出了一种子图划分的方法和原则,通过对给定图进行分解和合并处理,使得该DNA计算模型能够求解更大规模的图顶点着色问题。文章以一个含有61个顶点的图为例,对该模型进行了实验验证。实验结果表明,该模型不但延续了非枚举型DNA计算的优势,而且具有解决大规模的图顶点着色问题的能力。同传统的DNA计算模型相比,该模型可以大大提高计算效率,降低成本,能有效处理更大规模的图顶点着色问题,具有较强的应用价值。
为了满足不同DNA计算模型的编码需求,文章也考虑了不同编码条件及参数,设计了大量DNA编码。实验结果表明,这些编码能满足DNA计算中的数量和质量要求。由此所构成的编码数据库,能方便DNA计算技术的设计与利用,为后续超大规模DNA计算模型奠定了基础,具有较高的理论意义和应用价值。
DNA computing is a novel computation paradigm with DNA molecules as“data”, and biochemistry trials as“information processing instruments”. Because of its massive parallelism, high-density storage and energy efficiency, DNA computing attracts the concern of many scientists with different backgrounds. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. However, many issues still exist in DNA computing. It is important and interesting for further study on DNA computing.
The graph vertex coloring problem is the main topic of graph theory and applied in many fields, which is known as NP-complete problem. In this dissertation, with the biological research method and experimental technique, four effective, reliable DNA computing models to solve this problem are proposed. The advantage and disadvantage of these DNA computing models are discussed. The main research works are as follows:
An enumerating DNA computing model based on hybridization reactions is proposed. The graph vertex coloring is encoded by DNA molecules and solve by hybridization reactions and polymerase chain reaction. To testify this DNA computing model, a graph with five vertices is designed and the relevant biochemistry trials are completed. The results show that this model can solve vertex coloring problem efficiently.
To reduce the number of encoding, an improved enumerating DNA computing model is presented, which is based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method, and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction.
The solution space exponential explosion problem is the biggest obstacle in DNA computing. To overcome this problem, a non-enumerating DNA computing model is designed and testified based on the optimization of encoding method and construction of initial solution space. Polymerase chain reaction and Sequencing technology are used for delete false solutions and true solution detection in these models. This DNA computing model is used for solving vertex 3-coloring problem of a graph with 12 vertices. The results of the biochemistry trials show that many false solutions can be deleted when constructing the initial solution space, which overcome the solution space exponential explosion problem and improve the computational efficiency.
To solve large-scale graph vertex problem, a parallel type of DNA computing model is proposed based on the development of the non-enumerating DNA computing model. The method and principles of subgraph division are studied to implement the parallel procedure. To testify its computing capacity, a graph with 61 vertices is testified. The results indicate that this model extends the advantage of the first non-enumerative DNA computing model, improves the computational efficiency, and reduces costs significantly, which can be used for NP problems in a larger scale.
To get enough encodings for different DNA models, many constraints and parameters are considered and given. The rich encodings can form a database for design and application of DNA computing technology. The experiment results prove that these encodings are qualified and can avoid the error in experiments. The database can benefit further researches in the field of DNA computing.
图顶点着色问题存在于丰富的科学和工程应用中,如工序问题、排课表问题、物资储存问题等等,但它却是众所周知的NP-完全问题。本文针对这一具体问题,结合分子生物学的研究方法和实验技术,旨在建立自动化程度较高的,可用于求解较大规模问题的DNA计算模型,研究探讨了四种解决图顶点着色的DNA计算模型的可行性及优缺点,对每个DNA计算模型给出了具体的编码条件及相应的编码,及实现DNA计算模型的生化操作的实验步骤,并对一些模型给出了详细的实验验证。主要工作如下:
文章首先基于杂交反应提出一种枚举型的DNA计算模型。在该模型中,提出了具体编码方案,并利用DNA自动合成仪合成初始解空间,然后利用杂交反应和聚合酶链式反应来求解问题。文章以具有5个顶点图为例对该模型进行了生化实验验证。实验结果表明,该模型能有效求解图顶点着色问题。
为了减少DNA计算中编码的数量,不降低生化实验操作的可靠性,文章提出一种改进的枚举型DNA计算模型。在该模型中,利用双编码法对图顶点着色这一问题进行编码,利用酶切反应和聚合酶链式反应对问题进行求解。实例分析表明,该模型具有编码量少、求解过程简单的优点,尤其是因为该模型的解的检测方法类似于DNA测序技术,使得该模型更容易实现自动化操作。
解空间指数爆炸问题是阻碍DNA计算发展的最大瓶颈。针对这一问题,文章提出一种非枚举型DNA计算模型。在模型中,首先对编码方案和初始解空间构建进行了优化,构建了非枚举型的初始解空间,删除了大量非解,提高计算效率;然后利用聚合酶链式反应实现非解删除的操作,并使用DNA测序技术读取最终解;文章以一个含有12个顶点的图为例对该模型进行了实验验证。实验结果表明,该模型有效可靠,可以较好的克服DNA计算中的解空间指数爆炸问题。
为建立可用于求解大规模图顶点着色问题的DNA计算模型,文章在非枚举型DNA计算模型的基础上,引入并行处理的思想,建立了一种并行型DNA计算模型。在模型中,给出了一种子图划分的方法和原则,通过对给定图进行分解和合并处理,使得该DNA计算模型能够求解更大规模的图顶点着色问题。文章以一个含有61个顶点的图为例,对该模型进行了实验验证。实验结果表明,该模型不但延续了非枚举型DNA计算的优势,而且具有解决大规模的图顶点着色问题的能力。同传统的DNA计算模型相比,该模型可以大大提高计算效率,降低成本,能有效处理更大规模的图顶点着色问题,具有较强的应用价值。
为了满足不同DNA计算模型的编码需求,文章也考虑了不同编码条件及参数,设计了大量DNA编码。实验结果表明,这些编码能满足DNA计算中的数量和质量要求。由此所构成的编码数据库,能方便DNA计算技术的设计与利用,为后续超大规模DNA计算模型奠定了基础,具有较高的理论意义和应用价值。
DNA computing is a novel computation paradigm with DNA molecules as“data”, and biochemistry trials as“information processing instruments”. Because of its massive parallelism, high-density storage and energy efficiency, DNA computing attracts the concern of many scientists with different backgrounds. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. However, many issues still exist in DNA computing. It is important and interesting for further study on DNA computing.
The graph vertex coloring problem is the main topic of graph theory and applied in many fields, which is known as NP-complete problem. In this dissertation, with the biological research method and experimental technique, four effective, reliable DNA computing models to solve this problem are proposed. The advantage and disadvantage of these DNA computing models are discussed. The main research works are as follows:
An enumerating DNA computing model based on hybridization reactions is proposed. The graph vertex coloring is encoded by DNA molecules and solve by hybridization reactions and polymerase chain reaction. To testify this DNA computing model, a graph with five vertices is designed and the relevant biochemistry trials are completed. The results show that this model can solve vertex coloring problem efficiently.
To reduce the number of encoding, an improved enumerating DNA computing model is presented, which is based on enzyme digestion reactions. The graph vertex coloring problem is encoded by double encoding method, and the false solutions deletion and the true solutions detection are updated and automized partly after enzyme digestion reactions and polymerase chain reaction.
The solution space exponential explosion problem is the biggest obstacle in DNA computing. To overcome this problem, a non-enumerating DNA computing model is designed and testified based on the optimization of encoding method and construction of initial solution space. Polymerase chain reaction and Sequencing technology are used for delete false solutions and true solution detection in these models. This DNA computing model is used for solving vertex 3-coloring problem of a graph with 12 vertices. The results of the biochemistry trials show that many false solutions can be deleted when constructing the initial solution space, which overcome the solution space exponential explosion problem and improve the computational efficiency.
To solve large-scale graph vertex problem, a parallel type of DNA computing model is proposed based on the development of the non-enumerating DNA computing model. The method and principles of subgraph division are studied to implement the parallel procedure. To testify its computing capacity, a graph with 61 vertices is testified. The results indicate that this model extends the advantage of the first non-enumerative DNA computing model, improves the computational efficiency, and reduces costs significantly, which can be used for NP problems in a larger scale.
To get enough encodings for different DNA models, many constraints and parameters are considered and given. The rich encodings can form a database for design and application of DNA computing technology. The experiment results prove that these encodings are qualified and can avoid the error in experiments. The database can benefit further researches in the field of DNA computing.
引文
[1]李承祖,量子通信和量子计算.中国,长沙:国防科技大学出版社,2000
[2] Vlatko V, Martin B. Basic of quantum computation. Progress in Quantum Electronics, 1998, 22: 1~39
[3]许进,保铮.神经网络与图论.中国科学(E辑), 2001, 31(6): 533~555
[4]陈虎,戴葵,胡守仁.环形阵列神经网络计算机系统.计算机研究与发展, 1999, 36(2): 144~149
[5] Bocko M, Herr A, Feldman M. Prospects of quantum coherent computation using superconducting electronics. IEEE Transaction on Applied Superconductivity, 1997, 7(2): 3638~3641
[6] Gao F, Zhao H, Niu H. A study of numerical simulation of image reconstruction in optical computer tomography. Bioimaging, 1997, 5(2): 51~57
[7] Adleman L M. Molecular computation of solution to combinational problem. Science, 1994, 266(5187): 1021~1024
[8]许进. DNA计算与运筹学发展的新机遇.《中国运筹学会第六届学术交流会论文集》(上卷) (主编:章祥荪,王建方,刘宝碇,刘德刚), Global~Link Publishing Company香港, 2000: 43~54
[9] Chen J, Wood D H. Computation with biomolecules. Proc. Natl. Acad. Sci. USA, 2000, 97(4): 1328~1330
[10] Ruben A J, Landweber L F. The past, present and future of molecular computing. Perspectives, 2000, 1: 69~72
[11] Jonoska N. Trends in computing with DNA. J. Comput. Sci. & Technol., 2004, 19(1): 98~113
[12] Feynman R P. There’s plenty of room at the bottom. in: Gilbert D.H. (Ed.) Miniaturization, Reinhold, New York, 1961, 282~296
[13] Bennett C H. On constructing a molecular computer. IBM Journal of research and Development, 1973, 17: 525~532
[14] Head T. Formal language theory and DNA an analysis of the generative capacityof specific recombinant behaviors. Bull. Math. Bio., 1987, 149: 737~759
[15]许进,谭刚军,范月科,等. DNA计算机原理、进展及难点(Ⅳ):论DNA计算机模型.计算机学报, 2007, 30(6): 881~893
[16]王淑栋.四类DNA计算模型中一些理论与应用的研究. [博士学位论文].华中科技大学, 2004
[17] Zingel T. Formal models of DNA computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 2000, 49(2): 90~99
[18] Lipton R J. DNA solution of hard computational problems. Science, 1955, 268(5210): 542~545
[19] Ouyang Q, Kaplan P D, Liu S, et al. DNA solution of the maximal clique problem. Science, 1997, 278(5337): 446~449
[20] Sakamoto K, Gouzu H, Komiya K, et al. Molecular computation by DNA hairpin formation. Science, 2000, 288(5469):1223~1226
[21] Benenson Y, Paz-lizur T, Adar R, et al. Programmable and autonomous computing machine made of biomolecules. Nature, 2001, 414(6862): 430~434
[22] Landweber L F, Lipton R J. DNA 2 DNA Computations: A Potential `Killer App? in Proc. 3rd Annual DIMACS Meeting on DNA Based Computers, University of Pens. 1997
[23] Cukras A R, Faulhammer D, Lipton R J, et al. Chess games: a model for RNA based computation. Biosystems, 1999, 52(1-3): 35~45
[24] Liu W B, Zhang F Y, Xu J. A DNA algorithm for the graph coloring problem. Journal of Chemical Information and Computers, 2002, 42: 1176~1178
[25] Adleman L, Cheng Q, Goel A, et al. Combinatorial optimization problems in self-assembly. in: Proc. of the 4th annual ACM Symposium on Theory of Computing (STOC), New York: ACM Press, 2002, 23~32
[26] Chang W, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model. Biosystems, 2003, 72(3): 263~275
[27] Ibrahim Z, Tsuboi Y, Ono O. Hybridizatin-Ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for direct-proportional length-based DNA computing. IEEE Transaction onNanobioscience, 2006, 5(2): 103~109
[28] Watanabe S, Tsuboi Y, Ibrahim Z, et al. Adaptive DNA computing algorithm by using PCR and restriction enzyme. in: Proc. 2004 IEEE Conference on Cybemetics and Intelligent Systes, 2004, 262~267
[29] Yin Z X, Zhang F Y, Xu J. The general form of 0-1 programming problem based on DNA computing. Biosystems, 2003, 70(1): 73~79
[30] Yin Z X,Zhang F Y,Xu J. A Chinese postman problem based on DNA computing. Journal of Chemical Information and Computer Sciences,2002, 42(2): 222~224
[31] Xu J, Qiang X L, Fang G, et al. A DNA computer model for solving vertex coloring problem. Chinese Science Bulletin, 2006, 51: 2541~2549
[32]张凤月,殷志祥,许进. DNA芯片在0-1规划问题中的应用.生物化学与生物物理进展, 2003, 30(3): 412~415
[33] Smith L M, Corn R M, Condon A, et al. A surface-based approach to DNA computation. Journal of Computational Biology, 1998, 5(2): 255~267
[34] Frutos A G., Liu Q, Thiel A J, et al. Demonstration of a word design strategy for DNA computing on surfaces. Nucl. Acid. Res. 1997, 25(23): 4748~4757
[35] Liu Q, Wang L, Frutos A G, et al. DNA computing on surfaces. Nature, 2000, 403(6766): 175~179
[36] Wu H Y. An improved surface-based method for DNA computation. Biosystems, 2001, 59(1): 1~5
[37]刘文斌,高琳,王淑栋,等.最大匹配问题的DNA表面计算模型.电子学报, 2003, 31(10): 1496~1499
[38] Pan L Q, Liu G W, Xu J, et al. Solid phase based DNA solution of the coloring problem. Progress in Natural Science, 2004, 14(5): 104~107
[39] Liu Q, Thiel A J, Frutos A. G., et al. Surface-based DNA computation: hybridize and destruction. in: Proc. of 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., 1997
[40] Wang L, Liu Q, Frutos A, et al. Surface-based DNA computing operation: destroy and readout. Biosystems, 1999, 52(1-3): 189~191
[41] Su X, Smith L M. Demonstration of a universal surface DNA computer. Nucleic Acids Research, 2004, 32(10): 3115~3123
[42] Liu Q, Frutos A G, Wang L M, et al. Progress toward demonstration of a surface based DNA computation: a one word approach to solve a model satisfiability problem. Biosystems, 1999, 52(1-3): 25~33
[43] Braich R S, Johnson C, Rothemund P W K, et al. Solution of a satisfiability problem on gel-based DNA computer. in: Proc. 6th International Workshop on DNA-Based Computer: DNA Computing. Heidelberg: Springer, 2000, 27~42
[44] David H W, Catherine L, Taylor C, et al. Universal biochip readout of directed Hamiltonian path problems. in: Hagiya M., Ohuchi A., (Eds.). DNA computing: 8th International Workshop on DNA-Based Computers. Berlin Heidelberg: Springer-Verlag, 2003, 168~181
[45] Kou S, Lee H N, Noort D V, et al. Fluorescent molecular logic gates using microfluidic devices. Angew. Chem. Int. Ed., 2008, 47(5): 872~876
[46] Li W G, Ding Y S. A microfluidic systems-based DNA algorithm for solving special 0-1 integer programming problem. Applied Mathematics and Computation, 2007, 185(2): 1160~1170
[47] Livstone M S, Weiss R, Landweber L F. Automated design and programming of a microfluidic DNA computer. Natural Computing, 2006, 5: 1~13
[48] Livstone M S, Landweber L F. Mathematical considerations in the design of microreactor-based DNA computers. in: Chen J. Reif J. (Eds), DNA 9, LNCS, 2943, Heidelber: Springer-Verlag, 2004, 180~189
[49] Noort D V, Tang Z L, Landweber L F. Fully controllable microfluidics for molecular computers. JALA 9, 2004
[50] Roweis S, Winfree E, Burgoyne R, et al. A sticker based architecture for DNA computation. in: Proc. 2nd Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society, 1996
[51]许进,董亚非,魏小鹏.粘贴DNA计算机模型(Ⅰ):理论.科学通报, 2004, 49(3): 205~212
[52]许进,李三平,董亚非,等.粘贴DNA计算机模型(Ⅱ):应用.科学通报, 2004, 49(4): 299~307
[53] Paun G, Rozenberg G, Salomaa A. DNA computing: new computing paradigms. Spirnger-Verlag, Berlin Heidelberg, 1998
[54] Paun G. DNA computing based on splicing: universality result. Theoretical Computer Science, 2000, 231(2): 275~296
[55]孟大志,曹海萍. DNA计算与生物数学.生物物理学报, 2002, 18(2): 163~174
[56] Kari L. Computing with DNA. In: Misener S., Krawetz S. (Eds.) Computer Methods in Molecular Biology in Methods in Molecular Biology series. Humana Press.1998
[57] Kari L, Paun G, Rozenberg G, et al. DNA computing, sticker systems, and universality, Acta Informatica, 1998, 35(5): 401~420
[58] Paun G, Rozenberg G. Sticker systems. Theoretical computer science, 1998, 204: 183~203
[59] Lai T, Zimmermann K H. A software platform for the sticker model. Technology Report 2001. 2, Dept. Computer Engineering, TU Hamburg-harburg, 1996
[60] Sakakibara Y, Kobayashi S. Sticker systems with complex structures. Soft Computing, 2001, 5: 114~120
[61] Karl H, Zimmermann E. Efficient DNA sticker algorithm for NP-complete graph problems. Computer Physics Communications, 2003, 144(3): 297~309
[62] Gao L, Xu J. DNA solution of vertex cover problem based on sticker model. Chinese Journal of Electronics, 2002, 11(2): 280~284
[63] Braich R S, Chelyapov N, Johnson C, et al. Solution of a 20-Variable 3-SAT problem on a DNA computer. Science, 2002, 296(5567): 499~502
[64] Yang C N, Yang C B. A DNA solution of SAT problem by a modified sticker model. Biosystems, 2005, 81(1): 1~9
[65] Head T. Splicing system and molecular processes. in: ICEC’97 Special Session on DNA Based Computation, IEEE, 1997, 203~205
[66] Paun G. Splicing systems with target are computationally universal. InformationProcessing Letters, 1996, 59(3): 129~133
[67] Freund R, Kari L, Paun G. DNA computing based on splicing: The existence of universal computer. Theoretical Computer Science, 1999, 32(1): 69~112
[68] Paun G, Mauri G, Kobayashi S, et al. On the universality of post and splicing systems. Theoretical Computer Science, 2000, 231(2): 157~170
[69] Paun G, Salomaa A. DNA computing based on the splicing operation. Math. Japonica, 1996, 43(3): 607~632
[70] Benenson Y, Gil B, Ben-Dor U., et al. An autonomous molecular computer for logical control of gene expression. Nature, 2004,429: 423~429
[71] Liu W B, Shi X L, Zhang S M, et al. A new DNA computing model for the NAND gate based on induced hairpin formation. Biosystems, 2004, 87~92
[72] Head T, Kaolan P D, Bladergroen R R, et al. Computing with DNA by operating on plasmids. Biosystem, 2000, 57(2): 87~93
[73]马润年、张强、高琳、许进.图的最大权图的DNA计算.电子学报,2004, 32(1): 1~16
[74]高琳,马润年,许进.基于质粒求解最大匹配问题的DNA算法.生物化学与生物物理学进展, 2002, 29(5): 820~823
[75] Jonoska N, Karl S A, Saito M. Three dimensional DNA structures in computing. Biosystems, 1999, 52 (1-3): 143~153
[76] Seeman N C, Zhang Y, Du S M, et al. Construction of DNA polyhedra and knots through symmetry minimization, Supermolecular Stereochemistry, J.S. Siegel, 1995, 27~32
[77] Fang G, Zhang S M, Dong Y F, et al. A novel DNA computing model based on RecA-mediated triple-stranded DNA structure. Progress in Natural Science, 2007, 17(6): 708~711
[78] Kari L, Paun G, Thierrin G, et al. At the crossroads of DNA computing and formal languages: characterizing recursively enumerable languages by insertion-deletion systems. In: Rubin H., Wood D., (Eds), DNA Based Computers III, DIMACS Series, AMS, 1999, 48: 329~347
[79] Takahara A. On the computational power of insertion-deletion systems. in: Proc.of 8th International Meeting on DNA Based Computers, Sapporo, 2002, 139~150
[80] Winfree E. Design and self -assembly of two-dimensional DNA crystals. Nature, 1998, 394(6693): 539~544
[81] Winfree E. Algorithmic self-assembly of DNA. Ph. D. Thesis, California Institute of Technology Pasadena, 1998
[82] Adleman L. Towards a mathematical theory of self-assembly. Technical Report 00-722, University of Southern California, 2000
[83] Adleman L, Cheng Q, Goel A, et al. Running time and program size for self-assembled squares. ACM Symposium on Theory of Computing (STOC) 2001, 740~748
[84] Adleman L, Cheng Q, Goel A, et al. Linear self-assemblies: equilibria, entropy, and convergence rate. in: Proceedings of 6th International Conference on Difference Equations, Augsburg, Germany, 2001: New Progress in Difference Equations, CRC Press, 2004
[85] Rothemund P W K, Papadakis N, Winfree E. Algorithmic self-assembly of DNA sierpinski triangles. Plos Biology, 2004, 2(22): 2041~2053
[86] Winfree E, Eng T, Rozenberg G. String tile models for DNA computing by self-assembly. in: Condon A, Rozenberg G. (Eds.) DNA computers, Springer, LNCS, 2001, 2054: 63~88
[87] Brun Y. Arithmetic computation in the tile assembly model: addition and multiplication. Theoretical Computer Science, 2007, 378: 17~31
[88] Carbone A, Seeman N. Circuit and programmable self-assembling DNA structures. Proc. Natl. Acad. Sci. USA, 2002, 99(20): 12577~12582
[89] Wasiewicz P, Borsuk P, Mulawka J J, et al. Implementation of data flow logical operations via self-assembly of DNA. Lecture Notes in Computer Science, 1999, 1586: 174~182
[90] Ogihara M, Ray A. Simulating boolean circuits on a DNA computer. Computer Science Department, University of Rochester, Singapore, Technical Report TR 631, 1996
[91] Amos M, Paun G, Rozenberg G, et al. Topics in the theory of DNA computing. Theoretical Computer Science. 2002, 287: 3~38
[92] Amos M, Dunne P E, Gibbons A. DNA simulation of boolean Circuits. in: Proceedings of the 3rd Annual Conference, 1998, University of Wisconsin, Madison, Wisconsin, 679~683, San Francisco, CA
[93] Dunne P E, Amos M, Gibbons A. Boolean transitive closure in DNA. in: Computing with Bio-Molecules: Theory and Experiments, George Paun (Ed.), Springer-Verlag, Singapore, 1998, 127~137
[94] Mulawka J J, Wasiewicz P, Plucienniczak A. Another logical molecular NAND gate system. in: 7th International Conference on Microelectronics for Neural, Fuzzy and Bio-Inspired Systems, Granada, Spain, 1999, 340~346
[95] Wasiewice P. DNA computing: implementation of data flow logical operations. Future Generation Computer Systems, 2001, 17(4): 361~378
[96] Chen X, Wang Y, Liu Q, et al. Construction of molecular logic gates with a DNA-Cleaving deoxyribozyme. Angew. Chem. Int. Ed., 2006, 45: 1759~1762
[97] Seeling G, Soloveichik D, Zhang D Y, et al. Enzyme-free nucleic acid logic circuits. Science, 2006, 314(5805): 1585~1588
[98] Rinaudo K, Bleris L, Maddamsetti R, et al. A universal RNAi-based logic evaluator that operates in mammalian cells. Nature Biotechnology, 2007, 25: 795~801
[99] Rothemund P. A DNA and restriction enzyme implementation of Turing Machine, in: Lipton R. J., Baum E. B. (Eds.), DNA based Computers:Proc. of the DIMACS Workshop, Rhode Island, 1996
[100] Freund R, Paun G, Rozenberg G, et al. Watson-Crick finite automata. in: Proc.3rd DIMACS Workshop on DNA Based computers, Philadelphia, 1997, 305~317
[101] Adar R, Beneson Y, Linshiz G, et al. Stochastic computing with biomolecular automata. Proc. Natl. Acad. Sci., 2004, 101(27): 9960~9965
[102]刘西奎. DNA计算和遗传算法的编码与几个优化模型的研究. [博士学位论文],华中科技大学图书馆, 2004
[103] Kari L, Paun G, Rozengberg G, et al. DNA computing, matching systems and universlity. Technical Report 49, Turku University, 1996
[104] Garzon M, Jonoska N, Karl S. The bounder complexity of DNA computing. in: Proc. 4th workshop, Prince
[105] Shortreed M R, Chang S B, Hong D G, et al. A thermodynamic approach to design structure-free combinational DNA word sets. Nucleic Acids Research, 2005, 33(15): 4965~4977
[106] Tulpan D, Andronescu M, Chang S B, et al. Thermodynamically based DNA strand design. Nucleic Acids Research, 2005, 33(15): 4951~4964
[107]刘文彬,王淑栋,许进. DNA计算中的编码方法研究.计算机工程与宜用, 2003, 27: 118~121
[108] Feldkamp U, Rauhe H, Banzhaf W. Software tools for DNA sequence design. Genetic Programming and Evolvable Machines, 2003, 4: 153~171
[109] Shin S Y, Lee I H, Kim D, et al. Multiobjective evolutionary optimization of DNA sequences for reliable DNA computing. IEEE Transactions on Evolutionary Computation 2005, 9(2): 143~158
[110] Xiao J H, Xu J, Geng X T, et al. Multi-objective carrier chaotic evolutionary algorithm for DNA sequences design. Progress in Natural Science, 2007, 17(12): 1515~1520
[111] Deaton R. Good encodings for DNA-based solutions to combinatorial problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1999, 44: 247~258
[112] Arita M. The power of sequence design in DNA computing. 4th International Conference on Computational Intelligence and Multimedia Applications. 2001, 163~166
[113] Faulhammer D, Cukras A R, Lipton R J, et al. Molecular computation: RNA solutions to chess problems. Proc. Natl. Acad. Sci. USA, 1999, 97(4): 1385~1389
[114] Miyoshi D, Inoue M, Sugimoto N. DNA logic gates based on structural polymorphism of telomere DNA molecules responding to chemical input signals.Angew. Chem. Int. Ed., 2006, 45: 7716~7719
[115] Kossoy E, Lavid N, Soreni-Harari M, et al. A programmable biomolecular computing machine with bacterial phenotype output. ChemBioChem, 2007, 8: 1255~1260
[116] Karp R, Kenyon C, Waarts O. Error-resilient DNA computation. in: Proc. 7th Annual Symposium on Discrete Algorithms, SODA, Society for Industrial and Applied Mathematics Philadelphia, PA: USA, 1996, 458~467
[117] Wifree E. On the computational power of DNA annealing and ligation [M]. Technical Report USA, California: California Institute of Technology, 1995
[118] Nakatsugawa M, Yamamoto M, Shiba T, et al. Design of a PCR protocol for improving reliability of PCR in DNA computing. in: Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, IEEE, 2002, 91~96
[119] Rose J A, Deaton R, Franceschetti D R, et al. A statistical mechanical treatment of error in annealing biostep of DNA computation. in: Orlando F. L. (Ed)Special program in DNA and Molecular Computing at the Genetic and Evolutionary Computation Conference (GECCO-99), Morgan-Kaufmann, 1999, 1829~1834
[120]刘文彬,王淑栋,许进.可满足性(SAT)问题的几种DNA计算模型.小型微型计算机系统, 2004, 25(7): 1321~1325
[121] Guuarnieri F., Fliss M., Bancroft C. Making DNA add. Science, 1996, 273(5272): 220~223
[122]游林,温巧燕,杨义先. DNA计算与数据加密标准.北京邮电大学学报. 2004, 27(2): 77~83
[123]许进,张雷. DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用,计算机学报, 2003, 26(1): 1~11
[124] Mills A P. Gene expression profiling diagnosis through DNA molecular computation. Trends in Biotechnology, 2004, 20(4): 137~140
[125] Noort D V. Automation of microfluidics for molecular computers. in: Proc. of 2004 IEEE Conference on Cybernetics and Intelligent Systems, Singapore: IEEE, 2004, 1~3
[126] Chang W L, Guo M, Ho M S H. Fast parallel molecular algorithms forDNA-based computation: factoring integers. IEEE Transactions on nanobioscience, 2005, 4,(2): 149~163
[127]高琳,许进,张军英. DNA计算的研究进展与展望.电子学报, 2001, 7: 973~975
[128] Kari L. DNA computing: arrival of biological mathematics. The Mathematical Intelligence, 1997, 19(2): 9~22
[129] Chen K, Ramachandran V A. Space-Efficient randomized DNA algorithm for k-SAT. in: Proc. 6th International Workshop on DNA-Based Computers. Lecture Notes in Computer Science. 2000, 2054: 199~208
[130] Rose J A, Hagiya M, Deaton R J, et al. A DNA-based in vitro genetic program. Journal of Biological Physics, 2002, 28: 493~498
[131]任立红,丁永生,邵世煌. DNA计算研究的现状与展望.信息与控制, 1999, 28(4): 241~248
[132]王镜岩,朱圣庚,徐长法.生物化学(上),第三版,北京:高等教育出版社, 2002
[133]王镜岩,朱圣庚,徐长法.生物化学(下),第三版,北京:高等教育出版社, 2002
[134]刘承建,蔡武城译.分子生物学导论.上海:复旦大学出版社. 1989
[135]朱玉贤,李毅编著.现代分子生物学.高等教育出版社. 1997
[136]范维珂.分子生物学:基因工程的原理与技术.重庆大学出版社. 1999
[137]吴乃虎.基因工程原理.科学出版社. 2002
[138]奥斯伯,布伦特,金斯敦等.精编分子生物学实验指南,颜子颖,王海林译,北京:科学出版社, 1998
[139]萨姆布鲁克,拉塞尔.分子克隆实验指南,黄培堂等译,北京:科学出版社, 2002
[140] Jensen T R, Toft B. Graph coloring problem. New York: Wiley-Interscience, 1995, 1~23
[141] Werra D de. Theory and methodology: the combinatorics of timetabling. European Journal of Operational Research, 1997, 96: 504~513
[142] Gómez D, Montero J, Yá?ez J. A coloring fuzzy graph approach for imageclassification. Information Sciences, 2006, 176: 3645~3657
[143] Garey M R, Johnson D S. Computers and Intractability: A guide to the theory of NP-Completeness. W. H. Freeman, New York, 1979
[144] Eppstein D. Small maximal independent sets and faster exact graph coloring. Journal of Graph Algorithms and Applications, 2003, 7: 131~140
[145] Lucet C, Mendes F, and Moukrim A. An exact method for graph coloring. Computers and Operations Research, 2006, 33: 2189~2207
[146] Fleurent C, Ferland J A. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 1996, 63: 437~461
[147] Tzeng W G, King G H. Three-quarter approximation for the number of unused colors in graph coloring. Information Sciences, 1999, 114: 105~126
[148]许进,张军英,保铮.基于Hopfield网络的图的着色算法.电子学报, 1996, 24(10): 7~13
[149] Caramia M, Dell’Olmo P, Italiano G. F. Improved local search for graph coloring. Journal of Discrete Algorithms, 2006, 4: 277~298
[150] Johnson D S, Aragon C R, Mcgeoch L A, et al. Optimization by simulated annealing: an experimental evaluation; partⅡ, graph coloring and number partitioning. Journal of operations research, 1991, 39: 378~406.
[151] Bui T N, Nguyen T V H, Patel C M, et al. An ant-based algorithm for coloring graphs. Discrete Applied mathematics, 2008, 156: 190~200
[152]孙惠泉.图论及其应用.北京:科学出版社, 2004.
[153]高琳,许进.图的顶点着色问题的DNA算法.电子学报, 2003, 31(4): 494~496
[154] Yin Z X, Pan L Q, Shi X L. DNA algorithm of minimal spanning tree. in Proc. Of SPIE, 2006, 6358: 1~5
[155] Garzon M, Deaton R, Nino L F, et al. Genome encoding for DNA computing. in: The 3rd DIMACS Workshop on DNA-based Computing. U of Pennsylvania, 1997, 230~237
[156]张凤月.简单0-1规划问题和排课表问题的DNA计算. [博士学位论文],华中科技大学图书馆, 2005
[157] Harary F, Hedetniemi S T, Robinson R W. Uniquely colorable graphs. J. Combin. Theory, 1996, 6: 264~270
[158]林万明著. PCR技术操作与应用指南.北京:人民军医出版社, 1993
[159]郑仲承.寡核苷酸的优化设计.生命的化学, 2001, 21(3): 254~256
[160]殷志祥,刘文彬,董亚非,等. DNA计算在组合优化中的应用及其复杂性.系统工程与电子技术, 2003, 25(4): 427~431
[161] Zhang K, Pan L Q, Xu J. A global heuristically search algorithm for DNA encoding. Progress in Natural Science, 2007, 17: 745~749
[162]王延峰. DNA计算中的编码理论与方法研究. [博士学位论文],华中科技大学图书馆, 2007
[163] Rose J A, Deaton R J, Franceschetti D R, et al. Statistical-mechanical treatment of error in the annealing biostep of DNA computation. Proc. GECCO-99 conference, Morgan-Kaufmann, 1829~1834
[2] Vlatko V, Martin B. Basic of quantum computation. Progress in Quantum Electronics, 1998, 22: 1~39
[3]许进,保铮.神经网络与图论.中国科学(E辑), 2001, 31(6): 533~555
[4]陈虎,戴葵,胡守仁.环形阵列神经网络计算机系统.计算机研究与发展, 1999, 36(2): 144~149
[5] Bocko M, Herr A, Feldman M. Prospects of quantum coherent computation using superconducting electronics. IEEE Transaction on Applied Superconductivity, 1997, 7(2): 3638~3641
[6] Gao F, Zhao H, Niu H. A study of numerical simulation of image reconstruction in optical computer tomography. Bioimaging, 1997, 5(2): 51~57
[7] Adleman L M. Molecular computation of solution to combinational problem. Science, 1994, 266(5187): 1021~1024
[8]许进. DNA计算与运筹学发展的新机遇.《中国运筹学会第六届学术交流会论文集》(上卷) (主编:章祥荪,王建方,刘宝碇,刘德刚), Global~Link Publishing Company香港, 2000: 43~54
[9] Chen J, Wood D H. Computation with biomolecules. Proc. Natl. Acad. Sci. USA, 2000, 97(4): 1328~1330
[10] Ruben A J, Landweber L F. The past, present and future of molecular computing. Perspectives, 2000, 1: 69~72
[11] Jonoska N. Trends in computing with DNA. J. Comput. Sci. & Technol., 2004, 19(1): 98~113
[12] Feynman R P. There’s plenty of room at the bottom. in: Gilbert D.H. (Ed.) Miniaturization, Reinhold, New York, 1961, 282~296
[13] Bennett C H. On constructing a molecular computer. IBM Journal of research and Development, 1973, 17: 525~532
[14] Head T. Formal language theory and DNA an analysis of the generative capacityof specific recombinant behaviors. Bull. Math. Bio., 1987, 149: 737~759
[15]许进,谭刚军,范月科,等. DNA计算机原理、进展及难点(Ⅳ):论DNA计算机模型.计算机学报, 2007, 30(6): 881~893
[16]王淑栋.四类DNA计算模型中一些理论与应用的研究. [博士学位论文].华中科技大学, 2004
[17] Zingel T. Formal models of DNA computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 2000, 49(2): 90~99
[18] Lipton R J. DNA solution of hard computational problems. Science, 1955, 268(5210): 542~545
[19] Ouyang Q, Kaplan P D, Liu S, et al. DNA solution of the maximal clique problem. Science, 1997, 278(5337): 446~449
[20] Sakamoto K, Gouzu H, Komiya K, et al. Molecular computation by DNA hairpin formation. Science, 2000, 288(5469):1223~1226
[21] Benenson Y, Paz-lizur T, Adar R, et al. Programmable and autonomous computing machine made of biomolecules. Nature, 2001, 414(6862): 430~434
[22] Landweber L F, Lipton R J. DNA 2 DNA Computations: A Potential `Killer App? in Proc. 3rd Annual DIMACS Meeting on DNA Based Computers, University of Pens. 1997
[23] Cukras A R, Faulhammer D, Lipton R J, et al. Chess games: a model for RNA based computation. Biosystems, 1999, 52(1-3): 35~45
[24] Liu W B, Zhang F Y, Xu J. A DNA algorithm for the graph coloring problem. Journal of Chemical Information and Computers, 2002, 42: 1176~1178
[25] Adleman L, Cheng Q, Goel A, et al. Combinatorial optimization problems in self-assembly. in: Proc. of the 4th annual ACM Symposium on Theory of Computing (STOC), New York: ACM Press, 2002, 23~32
[26] Chang W, Guo M. Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model. Biosystems, 2003, 72(3): 263~275
[27] Ibrahim Z, Tsuboi Y, Ono O. Hybridizatin-Ligation versus parallel overlap assembly: an experimental comparison of initial pool generation for direct-proportional length-based DNA computing. IEEE Transaction onNanobioscience, 2006, 5(2): 103~109
[28] Watanabe S, Tsuboi Y, Ibrahim Z, et al. Adaptive DNA computing algorithm by using PCR and restriction enzyme. in: Proc. 2004 IEEE Conference on Cybemetics and Intelligent Systes, 2004, 262~267
[29] Yin Z X, Zhang F Y, Xu J. The general form of 0-1 programming problem based on DNA computing. Biosystems, 2003, 70(1): 73~79
[30] Yin Z X,Zhang F Y,Xu J. A Chinese postman problem based on DNA computing. Journal of Chemical Information and Computer Sciences,2002, 42(2): 222~224
[31] Xu J, Qiang X L, Fang G, et al. A DNA computer model for solving vertex coloring problem. Chinese Science Bulletin, 2006, 51: 2541~2549
[32]张凤月,殷志祥,许进. DNA芯片在0-1规划问题中的应用.生物化学与生物物理进展, 2003, 30(3): 412~415
[33] Smith L M, Corn R M, Condon A, et al. A surface-based approach to DNA computation. Journal of Computational Biology, 1998, 5(2): 255~267
[34] Frutos A G., Liu Q, Thiel A J, et al. Demonstration of a word design strategy for DNA computing on surfaces. Nucl. Acid. Res. 1997, 25(23): 4748~4757
[35] Liu Q, Wang L, Frutos A G, et al. DNA computing on surfaces. Nature, 2000, 403(6766): 175~179
[36] Wu H Y. An improved surface-based method for DNA computation. Biosystems, 2001, 59(1): 1~5
[37]刘文斌,高琳,王淑栋,等.最大匹配问题的DNA表面计算模型.电子学报, 2003, 31(10): 1496~1499
[38] Pan L Q, Liu G W, Xu J, et al. Solid phase based DNA solution of the coloring problem. Progress in Natural Science, 2004, 14(5): 104~107
[39] Liu Q, Thiel A J, Frutos A. G., et al. Surface-based DNA computation: hybridize and destruction. in: Proc. of 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., 1997
[40] Wang L, Liu Q, Frutos A, et al. Surface-based DNA computing operation: destroy and readout. Biosystems, 1999, 52(1-3): 189~191
[41] Su X, Smith L M. Demonstration of a universal surface DNA computer. Nucleic Acids Research, 2004, 32(10): 3115~3123
[42] Liu Q, Frutos A G, Wang L M, et al. Progress toward demonstration of a surface based DNA computation: a one word approach to solve a model satisfiability problem. Biosystems, 1999, 52(1-3): 25~33
[43] Braich R S, Johnson C, Rothemund P W K, et al. Solution of a satisfiability problem on gel-based DNA computer. in: Proc. 6th International Workshop on DNA-Based Computer: DNA Computing. Heidelberg: Springer, 2000, 27~42
[44] David H W, Catherine L, Taylor C, et al. Universal biochip readout of directed Hamiltonian path problems. in: Hagiya M., Ohuchi A., (Eds.). DNA computing: 8th International Workshop on DNA-Based Computers. Berlin Heidelberg: Springer-Verlag, 2003, 168~181
[45] Kou S, Lee H N, Noort D V, et al. Fluorescent molecular logic gates using microfluidic devices. Angew. Chem. Int. Ed., 2008, 47(5): 872~876
[46] Li W G, Ding Y S. A microfluidic systems-based DNA algorithm for solving special 0-1 integer programming problem. Applied Mathematics and Computation, 2007, 185(2): 1160~1170
[47] Livstone M S, Weiss R, Landweber L F. Automated design and programming of a microfluidic DNA computer. Natural Computing, 2006, 5: 1~13
[48] Livstone M S, Landweber L F. Mathematical considerations in the design of microreactor-based DNA computers. in: Chen J. Reif J. (Eds), DNA 9, LNCS, 2943, Heidelber: Springer-Verlag, 2004, 180~189
[49] Noort D V, Tang Z L, Landweber L F. Fully controllable microfluidics for molecular computers. JALA 9, 2004
[50] Roweis S, Winfree E, Burgoyne R, et al. A sticker based architecture for DNA computation. in: Proc. 2nd Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society, 1996
[51]许进,董亚非,魏小鹏.粘贴DNA计算机模型(Ⅰ):理论.科学通报, 2004, 49(3): 205~212
[52]许进,李三平,董亚非,等.粘贴DNA计算机模型(Ⅱ):应用.科学通报, 2004, 49(4): 299~307
[53] Paun G, Rozenberg G, Salomaa A. DNA computing: new computing paradigms. Spirnger-Verlag, Berlin Heidelberg, 1998
[54] Paun G. DNA computing based on splicing: universality result. Theoretical Computer Science, 2000, 231(2): 275~296
[55]孟大志,曹海萍. DNA计算与生物数学.生物物理学报, 2002, 18(2): 163~174
[56] Kari L. Computing with DNA. In: Misener S., Krawetz S. (Eds.) Computer Methods in Molecular Biology in Methods in Molecular Biology series. Humana Press.1998
[57] Kari L, Paun G, Rozenberg G, et al. DNA computing, sticker systems, and universality, Acta Informatica, 1998, 35(5): 401~420
[58] Paun G, Rozenberg G. Sticker systems. Theoretical computer science, 1998, 204: 183~203
[59] Lai T, Zimmermann K H. A software platform for the sticker model. Technology Report 2001. 2, Dept. Computer Engineering, TU Hamburg-harburg, 1996
[60] Sakakibara Y, Kobayashi S. Sticker systems with complex structures. Soft Computing, 2001, 5: 114~120
[61] Karl H, Zimmermann E. Efficient DNA sticker algorithm for NP-complete graph problems. Computer Physics Communications, 2003, 144(3): 297~309
[62] Gao L, Xu J. DNA solution of vertex cover problem based on sticker model. Chinese Journal of Electronics, 2002, 11(2): 280~284
[63] Braich R S, Chelyapov N, Johnson C, et al. Solution of a 20-Variable 3-SAT problem on a DNA computer. Science, 2002, 296(5567): 499~502
[64] Yang C N, Yang C B. A DNA solution of SAT problem by a modified sticker model. Biosystems, 2005, 81(1): 1~9
[65] Head T. Splicing system and molecular processes. in: ICEC’97 Special Session on DNA Based Computation, IEEE, 1997, 203~205
[66] Paun G. Splicing systems with target are computationally universal. InformationProcessing Letters, 1996, 59(3): 129~133
[67] Freund R, Kari L, Paun G. DNA computing based on splicing: The existence of universal computer. Theoretical Computer Science, 1999, 32(1): 69~112
[68] Paun G, Mauri G, Kobayashi S, et al. On the universality of post and splicing systems. Theoretical Computer Science, 2000, 231(2): 157~170
[69] Paun G, Salomaa A. DNA computing based on the splicing operation. Math. Japonica, 1996, 43(3): 607~632
[70] Benenson Y, Gil B, Ben-Dor U., et al. An autonomous molecular computer for logical control of gene expression. Nature, 2004,429: 423~429
[71] Liu W B, Shi X L, Zhang S M, et al. A new DNA computing model for the NAND gate based on induced hairpin formation. Biosystems, 2004, 87~92
[72] Head T, Kaolan P D, Bladergroen R R, et al. Computing with DNA by operating on plasmids. Biosystem, 2000, 57(2): 87~93
[73]马润年、张强、高琳、许进.图的最大权图的DNA计算.电子学报,2004, 32(1): 1~16
[74]高琳,马润年,许进.基于质粒求解最大匹配问题的DNA算法.生物化学与生物物理学进展, 2002, 29(5): 820~823
[75] Jonoska N, Karl S A, Saito M. Three dimensional DNA structures in computing. Biosystems, 1999, 52 (1-3): 143~153
[76] Seeman N C, Zhang Y, Du S M, et al. Construction of DNA polyhedra and knots through symmetry minimization, Supermolecular Stereochemistry, J.S. Siegel, 1995, 27~32
[77] Fang G, Zhang S M, Dong Y F, et al. A novel DNA computing model based on RecA-mediated triple-stranded DNA structure. Progress in Natural Science, 2007, 17(6): 708~711
[78] Kari L, Paun G, Thierrin G, et al. At the crossroads of DNA computing and formal languages: characterizing recursively enumerable languages by insertion-deletion systems. In: Rubin H., Wood D., (Eds), DNA Based Computers III, DIMACS Series, AMS, 1999, 48: 329~347
[79] Takahara A. On the computational power of insertion-deletion systems. in: Proc.of 8th International Meeting on DNA Based Computers, Sapporo, 2002, 139~150
[80] Winfree E. Design and self -assembly of two-dimensional DNA crystals. Nature, 1998, 394(6693): 539~544
[81] Winfree E. Algorithmic self-assembly of DNA. Ph. D. Thesis, California Institute of Technology Pasadena, 1998
[82] Adleman L. Towards a mathematical theory of self-assembly. Technical Report 00-722, University of Southern California, 2000
[83] Adleman L, Cheng Q, Goel A, et al. Running time and program size for self-assembled squares. ACM Symposium on Theory of Computing (STOC) 2001, 740~748
[84] Adleman L, Cheng Q, Goel A, et al. Linear self-assemblies: equilibria, entropy, and convergence rate. in: Proceedings of 6th International Conference on Difference Equations, Augsburg, Germany, 2001: New Progress in Difference Equations, CRC Press, 2004
[85] Rothemund P W K, Papadakis N, Winfree E. Algorithmic self-assembly of DNA sierpinski triangles. Plos Biology, 2004, 2(22): 2041~2053
[86] Winfree E, Eng T, Rozenberg G. String tile models for DNA computing by self-assembly. in: Condon A, Rozenberg G. (Eds.) DNA computers, Springer, LNCS, 2001, 2054: 63~88
[87] Brun Y. Arithmetic computation in the tile assembly model: addition and multiplication. Theoretical Computer Science, 2007, 378: 17~31
[88] Carbone A, Seeman N. Circuit and programmable self-assembling DNA structures. Proc. Natl. Acad. Sci. USA, 2002, 99(20): 12577~12582
[89] Wasiewicz P, Borsuk P, Mulawka J J, et al. Implementation of data flow logical operations via self-assembly of DNA. Lecture Notes in Computer Science, 1999, 1586: 174~182
[90] Ogihara M, Ray A. Simulating boolean circuits on a DNA computer. Computer Science Department, University of Rochester, Singapore, Technical Report TR 631, 1996
[91] Amos M, Paun G, Rozenberg G, et al. Topics in the theory of DNA computing. Theoretical Computer Science. 2002, 287: 3~38
[92] Amos M, Dunne P E, Gibbons A. DNA simulation of boolean Circuits. in: Proceedings of the 3rd Annual Conference, 1998, University of Wisconsin, Madison, Wisconsin, 679~683, San Francisco, CA
[93] Dunne P E, Amos M, Gibbons A. Boolean transitive closure in DNA. in: Computing with Bio-Molecules: Theory and Experiments, George Paun (Ed.), Springer-Verlag, Singapore, 1998, 127~137
[94] Mulawka J J, Wasiewicz P, Plucienniczak A. Another logical molecular NAND gate system. in: 7th International Conference on Microelectronics for Neural, Fuzzy and Bio-Inspired Systems, Granada, Spain, 1999, 340~346
[95] Wasiewice P. DNA computing: implementation of data flow logical operations. Future Generation Computer Systems, 2001, 17(4): 361~378
[96] Chen X, Wang Y, Liu Q, et al. Construction of molecular logic gates with a DNA-Cleaving deoxyribozyme. Angew. Chem. Int. Ed., 2006, 45: 1759~1762
[97] Seeling G, Soloveichik D, Zhang D Y, et al. Enzyme-free nucleic acid logic circuits. Science, 2006, 314(5805): 1585~1588
[98] Rinaudo K, Bleris L, Maddamsetti R, et al. A universal RNAi-based logic evaluator that operates in mammalian cells. Nature Biotechnology, 2007, 25: 795~801
[99] Rothemund P. A DNA and restriction enzyme implementation of Turing Machine, in: Lipton R. J., Baum E. B. (Eds.), DNA based Computers:Proc. of the DIMACS Workshop, Rhode Island, 1996
[100] Freund R, Paun G, Rozenberg G, et al. Watson-Crick finite automata. in: Proc.3rd DIMACS Workshop on DNA Based computers, Philadelphia, 1997, 305~317
[101] Adar R, Beneson Y, Linshiz G, et al. Stochastic computing with biomolecular automata. Proc. Natl. Acad. Sci., 2004, 101(27): 9960~9965
[102]刘西奎. DNA计算和遗传算法的编码与几个优化模型的研究. [博士学位论文],华中科技大学图书馆, 2004
[103] Kari L, Paun G, Rozengberg G, et al. DNA computing, matching systems and universlity. Technical Report 49, Turku University, 1996
[104] Garzon M, Jonoska N, Karl S. The bounder complexity of DNA computing. in: Proc. 4th workshop, Prince
[105] Shortreed M R, Chang S B, Hong D G, et al. A thermodynamic approach to design structure-free combinational DNA word sets. Nucleic Acids Research, 2005, 33(15): 4965~4977
[106] Tulpan D, Andronescu M, Chang S B, et al. Thermodynamically based DNA strand design. Nucleic Acids Research, 2005, 33(15): 4951~4964
[107]刘文彬,王淑栋,许进. DNA计算中的编码方法研究.计算机工程与宜用, 2003, 27: 118~121
[108] Feldkamp U, Rauhe H, Banzhaf W. Software tools for DNA sequence design. Genetic Programming and Evolvable Machines, 2003, 4: 153~171
[109] Shin S Y, Lee I H, Kim D, et al. Multiobjective evolutionary optimization of DNA sequences for reliable DNA computing. IEEE Transactions on Evolutionary Computation 2005, 9(2): 143~158
[110] Xiao J H, Xu J, Geng X T, et al. Multi-objective carrier chaotic evolutionary algorithm for DNA sequences design. Progress in Natural Science, 2007, 17(12): 1515~1520
[111] Deaton R. Good encodings for DNA-based solutions to combinatorial problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1999, 44: 247~258
[112] Arita M. The power of sequence design in DNA computing. 4th International Conference on Computational Intelligence and Multimedia Applications. 2001, 163~166
[113] Faulhammer D, Cukras A R, Lipton R J, et al. Molecular computation: RNA solutions to chess problems. Proc. Natl. Acad. Sci. USA, 1999, 97(4): 1385~1389
[114] Miyoshi D, Inoue M, Sugimoto N. DNA logic gates based on structural polymorphism of telomere DNA molecules responding to chemical input signals.Angew. Chem. Int. Ed., 2006, 45: 7716~7719
[115] Kossoy E, Lavid N, Soreni-Harari M, et al. A programmable biomolecular computing machine with bacterial phenotype output. ChemBioChem, 2007, 8: 1255~1260
[116] Karp R, Kenyon C, Waarts O. Error-resilient DNA computation. in: Proc. 7th Annual Symposium on Discrete Algorithms, SODA, Society for Industrial and Applied Mathematics Philadelphia, PA: USA, 1996, 458~467
[117] Wifree E. On the computational power of DNA annealing and ligation [M]. Technical Report USA, California: California Institute of Technology, 1995
[118] Nakatsugawa M, Yamamoto M, Shiba T, et al. Design of a PCR protocol for improving reliability of PCR in DNA computing. in: Evolutionary Computation, 2002. CEC'02. Proceedings of the 2002 Congress on, IEEE, 2002, 91~96
[119] Rose J A, Deaton R, Franceschetti D R, et al. A statistical mechanical treatment of error in annealing biostep of DNA computation. in: Orlando F. L. (Ed)Special program in DNA and Molecular Computing at the Genetic and Evolutionary Computation Conference (GECCO-99), Morgan-Kaufmann, 1999, 1829~1834
[120]刘文彬,王淑栋,许进.可满足性(SAT)问题的几种DNA计算模型.小型微型计算机系统, 2004, 25(7): 1321~1325
[121] Guuarnieri F., Fliss M., Bancroft C. Making DNA add. Science, 1996, 273(5272): 220~223
[122]游林,温巧燕,杨义先. DNA计算与数据加密标准.北京邮电大学学报. 2004, 27(2): 77~83
[123]许进,张雷. DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用,计算机学报, 2003, 26(1): 1~11
[124] Mills A P. Gene expression profiling diagnosis through DNA molecular computation. Trends in Biotechnology, 2004, 20(4): 137~140
[125] Noort D V. Automation of microfluidics for molecular computers. in: Proc. of 2004 IEEE Conference on Cybernetics and Intelligent Systems, Singapore: IEEE, 2004, 1~3
[126] Chang W L, Guo M, Ho M S H. Fast parallel molecular algorithms forDNA-based computation: factoring integers. IEEE Transactions on nanobioscience, 2005, 4,(2): 149~163
[127]高琳,许进,张军英. DNA计算的研究进展与展望.电子学报, 2001, 7: 973~975
[128] Kari L. DNA computing: arrival of biological mathematics. The Mathematical Intelligence, 1997, 19(2): 9~22
[129] Chen K, Ramachandran V A. Space-Efficient randomized DNA algorithm for k-SAT. in: Proc. 6th International Workshop on DNA-Based Computers. Lecture Notes in Computer Science. 2000, 2054: 199~208
[130] Rose J A, Hagiya M, Deaton R J, et al. A DNA-based in vitro genetic program. Journal of Biological Physics, 2002, 28: 493~498
[131]任立红,丁永生,邵世煌. DNA计算研究的现状与展望.信息与控制, 1999, 28(4): 241~248
[132]王镜岩,朱圣庚,徐长法.生物化学(上),第三版,北京:高等教育出版社, 2002
[133]王镜岩,朱圣庚,徐长法.生物化学(下),第三版,北京:高等教育出版社, 2002
[134]刘承建,蔡武城译.分子生物学导论.上海:复旦大学出版社. 1989
[135]朱玉贤,李毅编著.现代分子生物学.高等教育出版社. 1997
[136]范维珂.分子生物学:基因工程的原理与技术.重庆大学出版社. 1999
[137]吴乃虎.基因工程原理.科学出版社. 2002
[138]奥斯伯,布伦特,金斯敦等.精编分子生物学实验指南,颜子颖,王海林译,北京:科学出版社, 1998
[139]萨姆布鲁克,拉塞尔.分子克隆实验指南,黄培堂等译,北京:科学出版社, 2002
[140] Jensen T R, Toft B. Graph coloring problem. New York: Wiley-Interscience, 1995, 1~23
[141] Werra D de. Theory and methodology: the combinatorics of timetabling. European Journal of Operational Research, 1997, 96: 504~513
[142] Gómez D, Montero J, Yá?ez J. A coloring fuzzy graph approach for imageclassification. Information Sciences, 2006, 176: 3645~3657
[143] Garey M R, Johnson D S. Computers and Intractability: A guide to the theory of NP-Completeness. W. H. Freeman, New York, 1979
[144] Eppstein D. Small maximal independent sets and faster exact graph coloring. Journal of Graph Algorithms and Applications, 2003, 7: 131~140
[145] Lucet C, Mendes F, and Moukrim A. An exact method for graph coloring. Computers and Operations Research, 2006, 33: 2189~2207
[146] Fleurent C, Ferland J A. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 1996, 63: 437~461
[147] Tzeng W G, King G H. Three-quarter approximation for the number of unused colors in graph coloring. Information Sciences, 1999, 114: 105~126
[148]许进,张军英,保铮.基于Hopfield网络的图的着色算法.电子学报, 1996, 24(10): 7~13
[149] Caramia M, Dell’Olmo P, Italiano G. F. Improved local search for graph coloring. Journal of Discrete Algorithms, 2006, 4: 277~298
[150] Johnson D S, Aragon C R, Mcgeoch L A, et al. Optimization by simulated annealing: an experimental evaluation; partⅡ, graph coloring and number partitioning. Journal of operations research, 1991, 39: 378~406.
[151] Bui T N, Nguyen T V H, Patel C M, et al. An ant-based algorithm for coloring graphs. Discrete Applied mathematics, 2008, 156: 190~200
[152]孙惠泉.图论及其应用.北京:科学出版社, 2004.
[153]高琳,许进.图的顶点着色问题的DNA算法.电子学报, 2003, 31(4): 494~496
[154] Yin Z X, Pan L Q, Shi X L. DNA algorithm of minimal spanning tree. in Proc. Of SPIE, 2006, 6358: 1~5
[155] Garzon M, Deaton R, Nino L F, et al. Genome encoding for DNA computing. in: The 3rd DIMACS Workshop on DNA-based Computing. U of Pennsylvania, 1997, 230~237
[156]张凤月.简单0-1规划问题和排课表问题的DNA计算. [博士学位论文],华中科技大学图书馆, 2005
[157] Harary F, Hedetniemi S T, Robinson R W. Uniquely colorable graphs. J. Combin. Theory, 1996, 6: 264~270
[158]林万明著. PCR技术操作与应用指南.北京:人民军医出版社, 1993
[159]郑仲承.寡核苷酸的优化设计.生命的化学, 2001, 21(3): 254~256
[160]殷志祥,刘文彬,董亚非,等. DNA计算在组合优化中的应用及其复杂性.系统工程与电子技术, 2003, 25(4): 427~431
[161] Zhang K, Pan L Q, Xu J. A global heuristically search algorithm for DNA encoding. Progress in Natural Science, 2007, 17: 745~749
[162]王延峰. DNA计算中的编码理论与方法研究. [博士学位论文],华中科技大学图书馆, 2007
[163] Rose J A, Deaton R J, Franceschetti D R, et al. Statistical-mechanical treatment of error in the annealing biostep of DNA computation. Proc. GECCO-99 conference, Morgan-Kaufmann, 1829~1834