DNA计算中若干理论问题的研究
|
摘要
DNA 计算是一种以生物分子DNA 作为计算介质,以生物化学反应作为计算工具的一种新型计算方法.一般认为,经典数字计算机执行串行任务的能力是不容置疑的.而DNA 计算在求解自然界大量存在的需用穷举搜索方法求解的复杂问题上,具有经典数字计算机所无法比拟的天然优势.
本文主要从DNA 计算机研制中DNA 分子的合成问题,DNA 计算中的编码问题两个方面出发,以DNA 计算中较为成熟的粘贴模型和粘贴系统为基础,对DNA计算机中的若干问题进行了研究和讨论,具体内容如下:
编码问题是DNA 计算机研制中最为核心的问题.因为,首先它直接影响着DNA 序列的合成质量; 其次,编码的好坏直接影响着能否按照所设计的目标进行杂交; 第三,编码的好坏不仅直接影响解空间的大小,而且决定能否解决所谓的“解空间指数爆炸问题”,即与DNA计算机研究能否深入发展息息相关.所以,我们在详细讨论影响编码的主要因素的基础上,对DNA 计算机中的编码问题进行了较为深入的研究.
DNA 分子的合成问题不仅是DNA 计算中生物操作过程中首先要处理的问题,而且是DNA计算机研制中必须要解决的问题,因为最终实用化的DNA计算机应是一种全自动化的,如何给出一种将DNA 分子的合成过程与编码以及其它生化操作自动化地衔接起来是全自动化DNA 计算机当前研究的关键难题.为了解决这个问题,必须十分熟悉有关DNA 分子合成的基本原理以及合成技术,这也是本文需要研讨的首要问题.
在深入探讨DNA计算的原理、完备性和通用性以及粘贴模型和粘贴系统的基础上,借鉴经典数字计算机组成原理,提出了基于粘贴模型的协同DNA计算机基本组成原理模型,并对该系统内部各组成单元功能进行了论述.
提出了一种新的基于粘贴DNA 计算模型的分子逻辑门的实现方法.在此方法中,逻辑门、输入信号和输出信号是DNA分子.可以实现AND ,OR 和NAND 类型
DNA computing is a new calculation method that used biological molecule DNA as calculation medium and biochemical reaction as calculation tool. Generally considering, although the ability of the classical digital computer is unassailable when it executes serial task, DNA computing shows natural advantage compared with the classical digital computer in solving the problems that all possible solution should be verified which exist everywhere.
In the dissertation, several problems in DNA molecule synthesis and DNA computing coding of DNA computer manufacture are studied and discussed mainly from the point of sticker models and sticker systems. The detailed contents are as follows:
The coding problem is the core problem of DNA computer realization. Firstly because it has an impact on the quality of DNA sequence synthesis; Secondly because the quality of coding directly influences the process whether the hybridization can be proceeded according to the desired target; Thirdly because the quality of coding has effects not only on the space size of solution but also on whether the problem of “exponential explosion of space size of solution”which relates closely to the development of DNA computer can be solved. So we lucubrate the coding problem of DNA computer in-depth based on the discussion of major influencing factors of coding problem.
The problem of DNA molecule synthesis is not only the all-important problem which should be disposed firstly in the biological operation process, but also the problem which must be solved in DNA computer manufacture. The realization of DNA computer should be automatic completely. The problem of how to find the solution to link up the synthesizing and coding process of DNA molecule and other biochemical operation automatically is becoming the sixty-four-dollar question of completely automatic DNA
computer research. In order to solve this problem, we must focus our mind on the basic principle and techniques of DNA molecule synthesis firstly. The basic combination principle model of cooperation DNA computer and functions of each unit inside the system are proposed and discussed detailedly based on the theory, completeness, universality of DNA computing, sticker model and sticker system. The organizations of classical digital computer are referenced. A new method of molecule logic gate realization based on the sticker model of DNA computing is presented in this paper. Logic gate, input and output signals are all composed of DNA strands. AND operation of logic gate can be achieved by this method. In theory, the molecular logic gate based on DNA is considered as the fundamental of both DNA computer architecture and hardware technology. Logic gate, inputs and outputs are all DNA strands in this method. This technique employs standard operations of biomedical engineering, such as polymerase chain reaction (PCR), agarose gel electrophoresis, labeling and detecting of probe. These techniques may be applied on DNA chips to develop DNA computer.
本文主要从DNA 计算机研制中DNA 分子的合成问题,DNA 计算中的编码问题两个方面出发,以DNA 计算中较为成熟的粘贴模型和粘贴系统为基础,对DNA计算机中的若干问题进行了研究和讨论,具体内容如下:
编码问题是DNA 计算机研制中最为核心的问题.因为,首先它直接影响着DNA 序列的合成质量; 其次,编码的好坏直接影响着能否按照所设计的目标进行杂交; 第三,编码的好坏不仅直接影响解空间的大小,而且决定能否解决所谓的“解空间指数爆炸问题”,即与DNA计算机研究能否深入发展息息相关.所以,我们在详细讨论影响编码的主要因素的基础上,对DNA 计算机中的编码问题进行了较为深入的研究.
DNA 分子的合成问题不仅是DNA 计算中生物操作过程中首先要处理的问题,而且是DNA计算机研制中必须要解决的问题,因为最终实用化的DNA计算机应是一种全自动化的,如何给出一种将DNA 分子的合成过程与编码以及其它生化操作自动化地衔接起来是全自动化DNA 计算机当前研究的关键难题.为了解决这个问题,必须十分熟悉有关DNA 分子合成的基本原理以及合成技术,这也是本文需要研讨的首要问题.
在深入探讨DNA计算的原理、完备性和通用性以及粘贴模型和粘贴系统的基础上,借鉴经典数字计算机组成原理,提出了基于粘贴模型的协同DNA计算机基本组成原理模型,并对该系统内部各组成单元功能进行了论述.
提出了一种新的基于粘贴DNA 计算模型的分子逻辑门的实现方法.在此方法中,逻辑门、输入信号和输出信号是DNA分子.可以实现AND ,OR 和NAND 类型
DNA computing is a new calculation method that used biological molecule DNA as calculation medium and biochemical reaction as calculation tool. Generally considering, although the ability of the classical digital computer is unassailable when it executes serial task, DNA computing shows natural advantage compared with the classical digital computer in solving the problems that all possible solution should be verified which exist everywhere.
In the dissertation, several problems in DNA molecule synthesis and DNA computing coding of DNA computer manufacture are studied and discussed mainly from the point of sticker models and sticker systems. The detailed contents are as follows:
The coding problem is the core problem of DNA computer realization. Firstly because it has an impact on the quality of DNA sequence synthesis; Secondly because the quality of coding directly influences the process whether the hybridization can be proceeded according to the desired target; Thirdly because the quality of coding has effects not only on the space size of solution but also on whether the problem of “exponential explosion of space size of solution”which relates closely to the development of DNA computer can be solved. So we lucubrate the coding problem of DNA computer in-depth based on the discussion of major influencing factors of coding problem.
The problem of DNA molecule synthesis is not only the all-important problem which should be disposed firstly in the biological operation process, but also the problem which must be solved in DNA computer manufacture. The realization of DNA computer should be automatic completely. The problem of how to find the solution to link up the synthesizing and coding process of DNA molecule and other biochemical operation automatically is becoming the sixty-four-dollar question of completely automatic DNA
computer research. In order to solve this problem, we must focus our mind on the basic principle and techniques of DNA molecule synthesis firstly. The basic combination principle model of cooperation DNA computer and functions of each unit inside the system are proposed and discussed detailedly based on the theory, completeness, universality of DNA computing, sticker model and sticker system. The organizations of classical digital computer are referenced. A new method of molecule logic gate realization based on the sticker model of DNA computing is presented in this paper. Logic gate, input and output signals are all composed of DNA strands. AND operation of logic gate can be achieved by this method. In theory, the molecular logic gate based on DNA is considered as the fundamental of both DNA computer architecture and hardware technology. Logic gate, inputs and outputs are all DNA strands in this method. This technique employs standard operations of biomedical engineering, such as polymerase chain reaction (PCR), agarose gel electrophoresis, labeling and detecting of probe. These techniques may be applied on DNA chips to develop DNA computer.
引文
[1] Ouyang Q., Kaplan P.D., Liu S., et al.. DNA Solution of the Maximal Clique Problem. Science, 1997, 278 (17): 446 –449.
[2] 李承祖. 量子通信和量子计算机. 国防科技大学出版社, 2000.
[3] 陈虎, 戴葵, 胡守仁. 环行阵列神经网络计算机系统. 计算机研究与发展, 1999, 36(2):144-149.
[4] Vlatko V., Martin B.. Basic of Quantum Computation. Progress in Quantum Electronics, 1998, 22: 1-39.
[5] Hwang K.. Advanced Computer Architecture. NewYork, McGrawHill, 1991.
[6] Netterer F. The Mathematics of Computerized Tomography. NewYork, Wiley, 1986: 114-126.
[7] Gao F., Niu H., Zhao H.. A study on numerical simulation of imager construction in optical computer tomography. Bioimaging,1997,5(2) : 51～57.
[8] 许进, 保铮. 神经网络与图论. 中国科学(E 辑),2001,31(6): 533-555.
[9] 许进. DNA 计算与运筹学发展的新机遇. 《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company 香港,2000: 43-54(注:特邀大会主题报告).
[10] 许进, 张雷. DNA 计算机原理、进展及难点( Ⅰ):生物计算系统及其在图论中的应用. 计算机学报, 2003, 26(1):1-11.
[11] 许进, 董亚非,魏小鹏. 粘贴DNA 计算机模型(Ⅰ):理论. 科学通报, 2004,49(3):205-212.
[12] 许进, 李三平,董亚非,魏小鹏. 粘贴DNA 计算机模型(Ⅱ):应用. 科学通报, 2004,49(4):299-307.
[13] 丁永生,邵世煌,任立红. DNA 计算与软计算. 科学出版社,2002.10.
[14] Adleman L.. Molecular Computation of Solution to Combinatorial problems. Science. 1994,66 (11):1021-1024.
[15] Paun G., Rozenberg G., Salomaa A.. DNA Computing-New Computing Paradigms. Springer, 1998.
[ 16 ] Feyman R.P. There's plenty of room at the bottom, In Minaturization. D.H.Gilbert.ED. Reinhold, New York,1961, 282-296.
[17] Freund R., Paun G., Rozenberg G., et al.. Watson-Crick Finite Automata, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[18] Fu B., Beigel R.. Length bounded molecular computing. 4th Int. Meeting on DNA-Based Computing, Balti-more, Penns., (June, 1998).
[19] Fu B., Beigel R., Zhou F.. An O(2n) volume molecular algorithm for Hamiltonian Path. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[20] Roweis S., Winfree E., Burgoyne R., et al.. A sticker based architecture for DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996.
[21] Yoshikawa T.. Emergence of Effective Fuzzy Rules for Controling Mobile Robots Using DNA Coding Method. Proceeding of 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan ,1996, 5: 581-586.
[22] GuptaV., Parthasarathy S., Zaki M.J.. Arithmetic and Logic Operations with DNA. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[23] Hagiya M., Arita M., Kiga D., et al.. Towards Parallel Evaluation and Learning of Boolean -Formulas with Molecules. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June,1997).
[24] Gibbons A., Amos M., Hodgson D.. Models of DNA computation, Mathematical Foundations of Computer. Science. 1996, 1113: 18-36.
[25] Guarnieri Frank, Fliss M. and Bancroft C. Making DNA add. Science. 1996,273: 220-223.
[26] Rozen D. E., McGrew S., Ellington A. D.. Molecular computing: Does DNA computer. Current Biology, 1996, 6(3): 254-258.
[27] Adleman, L.M., Rothemun P.W.K., Roweis d. S., et al.. On Applying Molecular Computation To The Data Encryption Standard. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
[28] Lipton R. J.. DNA Solution of Hard Computation Problems. Science, 1995 , 268 (4) :542-545.
[29] 孟大志,曹海萍. DNA 计算与生物数学.生物物理学报, 2002, 18(2): 163-166.
[30] Roweis S., Winfree E., Burgoyne R., Chelyapov N., Goodman M., Rothemund P., Adleman L.. A sticker based arcchtecture for DNA computation.in: Baum E B et al(Eds),DNA Based Computers, Proc. 2nd Annual Meeting, Princeton, 1999: 1-27.
[31] Kari L., Paun G., Rozenberg G., et al.. DNA computing, sticker systems, and universality. Acta Informatica, 1998, 35: 401-420.
[32] Kazic T.. After the Turing machine: A meta model for molecular computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[33] Pixton D.. Linear and circular splicing systems, Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
[34] Mirkin C.A., Letsinger R.L., Mucic R.C., et al.. A DNA-based Method for Rationally Assembling Nanoparticles Into Macroscopic Materials. Nature, 1996, 382: 607-611.
[35] Gatterdam R. W.. DNA and twist free splicing systems, in words, languages andcombinatorics. Singapore, World Scienctific Publishers, 1994.
[36] Khodor J., and David K. G.. The Efficiency of Sequence-Specific Separation of DNA Mixtures for Biological Computing. 3rd DIMACS Meeting on DNA Based Computers,Univ. of Penns., (June,1997).
[37] Kari L.. DNA computers: tomorrow's reality. Tutorial in the Bulletin of EATCS, 1996, 59: 256-266.
[38] Kari L., Sakakibara. Y.. DNA Computers Journal of the Institute of Electronics, Information and Communication Engineers, 80: 935-939, (in Japanese,1997).
[39] Kari L., Gloor G., Yu S.. Using DNA to solve the Bounded Post Correspondence Problem. Theoretical Computer Science, 2000, 231(2): 193-203.
[40] Freund R., Kari L., Paun G.. DNA computing based on splicing: The existence of universal computers. Theory of Computing Systems, 1999,32(1): 69-112.
[41] Kari L.. DNA computing based on insertions and deletions. Proceedings of the conference Conceptual tools for understanding dynamics in biological systems, London, 1996. In COENOSES, C.E.T.A. Gorizia, Italy, N.Kenkel, ed., 1997, 12: 89-95.
[42] Deninnghoff K. L., Gatterdam R. W.. On the Undecidability of splicing systems. Int. J. Computer Math., 1989, 27: 133-145.
[43] Paun G.. On the power of splicing operation. Int. J. Computer Math.,1995, 59: 7-35. [ 44 ] Kobyshi S. S., Szkaibara Y. B.. Multiple splicing systems and universal computability. Theoretical Computer Science, 2001, 264(1): 3-23.
[45] Paun G.. DNA computing based on splicing: Universality results. Theoretical Computer Science, 2000, 231(2): 275-296.
[46] Sakakibara Y. B., Ferreti C.. Splicing on tree-like structures. Theoretical Computer Science, 1999, 210(2): 227-243.
[47] Paun G., Mauri G., Kobayashi S., Yokomori T.. On the universality of Post and splicing systems. Theoretical Computer Science, 2000, 231(2):157-170.
[48] Paun G.. Splicing systems with targets are computationally universal. Information Processing Letters, 1996, 59(3):129-133.
[49] Mateesu A., Paun G., Rozenberg G., Salomaa A., Simple splicing systems. Discrete Applied Mathematics, 1998, 84(1-3):145-163.
[50] Adleman L.. On Constructing a Molecular Computing. Technical Report TR 79-387, Computer science Department ,University of Southern California, USA, January 1995.
[51] RooβD. and Wagner K. W. On the power of DNA-computing. Information and Computation. 1996. 131(2):95-109. [ 52 ] Mark Daley, Lila Kari, Greg Gloor, Rani Siromoney. Circular Contextual Insertions-Deletions with Applications to Biomolecular Computation, Manuscript, 1998. [ 53 ] L.Kari, G..Thierrin. Contextual Insertions-Deletions and Computability. Inf. Comput., 1996, 131, 47–61.
[54] C. Martin-Vide, Gh.P?un, A. Salomaa. Characterizations of Recursively Enumerable Languages by means of Insertion Grammars. Theoretical Computer Science, 205,1-2 (1998), 195-205.
[55] L.Kari, G.P?un, G.Thierrin, S.Yu. At the Crossroads of DNA Computing and Formal Languages: Characterizing Recursively Enumerable Languages by Insertion-Deletion Systems. In DNA Based Computers III, H.Rubin, D.Wood, eds, DIMACS Series, vol.48, 1999, AMS Press, 329-347.
[56] A.Takahara. On the Computational Power of Insertion-Deletion Systems. Proc. of 8th International Meeting on DNA Based Computers, June, Sapporo, 139-150, 2002.
[57] Tiina Zingel. Formal Model of DNA Computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 49(2)(2000): 90–99.
[58] T. Head. Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors. Bull. Math. Bio., 1987, l49: 737-759.
[59] Kari L. DNA Computing: Arrival of Biological Mathematics. The Mathematical Intelligencer, 1997, 19(2): 9-22.
[60] P?un G., Rozenberg G., Salomaa A.. DNA Computing. Springer, 1998: 10-41.
[61] T. Head. Splicing Schemes and DNA, In: Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics and Developmental Biology, Ed. By G.Rozenberg and A.Salomaa, Springer-Verlag, 1992, 371-383.
[62] Gh.P?un, A.Salomaa. DNA Computing Based on the Splicing Operation. Math. Japonica 1996, 43(3): 607-632.
[63] Katrin Erk. Simulating Boolean Circuits by Finite Splicing. In Proceedings of the Congress on Evolutionary Computation (CEC'99), Washington D.C., USA, July 6-9, 1999.
[64] Yokomori, T., Kobayashi, S. DNA-EC: A Model of DNA-computing Based on Equality Checking. In 3rd DIMACS Workshop on DNA-Based Computers, 1997, 334–345.
[65] E.Csuhaj-Varju, R.Freund, F. Wachtler. Test Tube Distributed Systems based on Splicing. Computer and AI, 15, 2-3 (1996), 211-232.
[66] K.Culik II, T. Harju. Splicing Semigroups of Dominoes and DNA. Discrete Appl. Math., 31(1991), 261-277.
[67] J.Dassow, V.Mitrana. Splicing Grammar Systems. Computer and AI, 15, 2-3 (1996), 109-122.
[68] L.Kari, Gh.P?un, A. Salomaa. The Power of Restricted Splicing with Rules from a Regular Set. J. Universal Computer Sci., 2, 4(1996), 224-240.
[69] Pixton D. Linear and Circular Splicing Systems. Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
[70] Rudolf Freund. Splicing Systems on Graphs. Manuscript, 1995. [ 71 ] Y. Benenson, T. Paz-Elizur, R. Adar, E. Kelnan, Z. Livneh, E.Shapiro. Programmable and Autonomous Computing Machine Made of Biomolecules. Nature 414 (22), (2001) 430-434.
[72] Roweis, et al. A Sticker Based Model for DNA Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44, 1-27.
[73] P?un Gh, Rozenberg G. Sticker Systems. Theoretical Computer Science 204 (1998): 183-203.
[74] T.Lai, K.H. Zimmermann. A Software Platform for the Sticker Model. Techn. Report, No. 2001.2, Dept. Computer Engineering, TU Hamburg-Harburg, 2001.
[75] K.H. Zimmermann. DNA Sticker Algorithms for Binary Linear Codes. IEEE Trans. Infor. Theory, to appear. [ 76 ] Y.Sakakibara, S.Kobayashi. Sticker Systems with Complex Structures. Soft Computing 5 (2001): 114-120.
[77] Karl-Heinz Zimmerman. Efficient DNA Sticker Algorithms for NP-Complete Graph Problems. Computer Physics Communications, 2002,144: 297-309.
[78] Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002, 11(2): 280-284.
[79] 许进, 董亚非. 粘贴DNA 计算模型理论及应用. 科学通报, 2003, 48: (12).
[80] Wenbin Liu, Shudong Wang, Jin Xu. Solving the 3-SAT Problem Based on DNA Computing. J. Chem. Inf. Comput. Sci. 2003.11.
[81] Nishikawa A., Hagiya M., Yamamura M.. Virtul DNA Simulator and protocol design by GA. Proc. The Genetic and Evolutionary Computation Conference. Orlando. FL. USA. July 13-17,1999:1810-1816.
[82] Mulawka J. J., Wasiewicz P., Pietak K.. Virus-enhanced genetic algorithms inspired by DNA Computing. 11th International Symposium and Methodologies for Intelligent Systems. Warsaw. Poland. 8-11 June 1999: 529-537.
[83] Boneh D., and Lipton R. J.. A Divide and conquer approach to DNA sequencing. Princeton University, 1996.
[84] Lipton R.. A memory based attack on cryptosystems with application to DNA computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[85] Head T., Kaolan P. D., Bladergroen R. R., et al. Computing with DNA by operating on plasmids. Biosystem, 2000, 57: 87-93.
[86] 高琳, 马润年, 许进. 基于质粒DNA 匹配问题的分子算法. 生物化学与生物物理进展, 2002(5): 820-822.
[87] 张连珍, 许进. 基于质粒的DNA 计算模型研究. 计算机工程与应用, 2004, 40(1).
[88] Cukras A., Faulhammer D., Lipton R., et al.. Chess games: A model for RNA-based computation. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[89] Liu Q. H., Guo Z., Condon A. E., et al.. A surface-based approach to DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996.
[90] Liu Q. H., Guo Z., Condon A. E., et al.. DNA Computing on Surfaces, Nature, 2000, 403: 175-179.
[91] Liu Q., Frutos A., Wang L., et al.. Progress towards demonstration of a surface based DNA computation: A one word approach to solve a model satiability problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[ 92 ] Wu H. Y.. An improved surface-based method for DNA computation. Biosystems,2001, 59(1): 1-5.
[93] Sakamoto k.. Molecular Computation by DNA Hairpin Formation. Science, 2000,283: 1223-1227.
[94] Braich, R. S., Chelyapov, N., Johnson, C., Rothemund, P.W.K., Adleman, L.. Solution of a 20-Variable 3-SAT Problem on a DNA Computer. Science , 2002, 296: 499-502.
[95] Mccammon, J., and S. Harvey, Dynamics of Proteins and Nucleic Acids, Cambridge University Press, (1987).
[96] Plum, G.E., and D. S. Pilch, Nucleic Acid Hybridize: Triplex Stability and Energetics., Annu. Rev. Biophys. Biomol. Struct. , 24:, 319{350, (February 1997).
[97] Hartemink, A.J., D.K. Giord Thermodynamic Simulation of Deoxyoligonucleotide Hybridize for DNA Computation, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[98] Watson, J., M. Gilman, J. Witkowski, M. Zoller, Recombinant DNA (2nd ed.), Scientic American Books, W.H. Freeman and Co., (1992).
[99] Watson, J., N. Hoplins, J. Roberts, et. al., Molecular Biology of the Gene, Benjamin/Cummings, Menlo Park, CA, (1987).
[100] Alberts, B., Bray, D., Lewis, J., Raff, M., Roberts, K., Watson, J. 1994. Molecular Biology of the Cell. 3rd ed. New York: Garland Publishing.
[101] Sambrook, J., E. Fritsch, and T. Maniatis, Molecular Cloning: A Laboratory Manual, Cold Spring Harbor Laboratory Press, NY, Vol. 1,2,3 (1989).
[102] Boneh, D., and R. Lipton, Making DNA Computers Error Resistant, Princeton CS Tech-Report CS-TR-491-95 Also in 2nd Annual DIMACS Meeting on DNA Based Computers,, Princeton University, June 1996.
[103] Amos, M., A. Gibbons, D. Hodgson, Error-resistant Implementation of DNA Computations, 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
[104] Deputat, M., G. Hajduczok, E. Schmitt, On Error-Correcting Structures Derived from DNA, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[105] Freud. R, Freud. F. Proceeding of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97). Indian apolis, IN USA, 1997. 237-242.
[106] Cai, W., A. Condon, R.M. Corn, Z. Fei, T. Frutos, E. Glaser, Z. Guo, M.G. Lagally, Q. Liu, L.M. Smith, and A. Thiel, The Power of Surface-Based Computation, Proc. First International Conference on Computational Molecular Biology (RECOMB97), January, 1997.
[107] Smith L.M, Corn R.M., Condon A.E., et al. Journal of Computational Biology, 1998, 5(2):255—267.
[108] Liu, Q., A.J. Thiel, A.G. Frutos, R.M. Corn, L.M. Smith, Surface-Based DNA Computation: Hybridize and Destruction, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[109] Manca, V., C. Martin-Vide, G. Paun, New computing paradigms suggested by DNA computing by carving, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[110] Wang, L., Q. Liu, A. Frutos, S. Gillmor, A. Thiel, T. Strother, A. Condon, R. Corn, M. Lagally, L. Smith, Surface-based DNA computing operations: DESTROY and READOUT", 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[111] Eng, T., and B.M. Serridge, A Surface-Based DNA Algorithm for Minimal Set Cover, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[112] Liu, Q., A. Frutos, L. Wang, A. Thiel, S. Gillmor, T. Strother, A. Condon, R. Corn, M. Lagally, L. Smith, Progress towards demonstration of a surface based DNA computation: A one word approach to solve a model satiability problem, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[113] Smith L.M, Corn R.M., Condon A.E., et al. Journal of Computational Biology, 1998, 5(2):255—267.
[114] Frutos, A.G., A.J. Thiel, A.E. Condon, L.M. Smith, R.M. Corn, DNA Computing at Surfaces: 4 Base Mismatch Word Design, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[115] Leonard M Adleman. Molecular Computation of Solutions to Combinatorial Problems, Science. November 1994, 266(11): 1021-1023.
[116] Lipton R. J.. DNA Solution of Hard Computation Problems. Science, 1995, 268 (4) : 542-545.
[117] Baum E B. DNA sequences useful for computation. In DNA based Computers:Proceedings of the DIMACS Workshop, June 10, 1996, Princeton University (eds Laura F. Landweber, Eric B. Baum)(DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44 :235-241).
[118] Deaton R. et al. Good Encodings for DNA-Based Solutions to Combinatorial Problems. In DNA based Computers:Proceedings of the DIMACS Workshop, June 10, 1996, Princeton University (eds Laura F. Landweber, Eric B. Baum)(DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44 :247-258).
[119] Baum E B. Building an associative memory vastly larger than the brain. Science, 268: 583-585, 1995.
[120] Garzon, M., Neathery, P., Deaton, R.J., Murphy, R..C., Franceschetti, D.R., Stevens, S.E.Jr.. A new metric for DNA Computing. Proceedings of the 2nd Annual Genetic Programming Conference, 1997,472-487.
[121] Garzon M., Deaton R., Nino L.F., Stevens S.E. , Wittner M.. Genome Encoding for DNA Computing. The Third DIMACS Workshop on DNA-based Computing, U of Pennsylvania, 1997, 230-237.
[122] Deaton R. and Garzon M.. Thermodynamic Constraints on DNA-based Computing, in Computing with Bio-Molecues: Theory and Expirements. ed. G. Paun, Springer-Verlag: Singapore, 1998, 138-152.
[123] Deaton R., Franceschetti D. R., Garzon M., Rose J. A., Murphy R. C., and Stevens S. E.. Information transfer through hybridyzation reaction in DNA based computing. Proceedings of the Second Annual Conference, 1997, July 13-16, Stanford University, (Morgan Kaufmann, San Francisco, 463-471.
[124] Deaton R. et al. A DNA Based Implementation of an Evolutionary Computation. Proceedings IEEE Conference on Evolutionary Computation. Indiana, 1997, 267-271.
[125] Rose J.A., The Fidelity of DNA computation, Ph. D thesis, The University of Memphis, 1999. 11.
[126] Rose J.A., Deaton R.J., Franceschetti D.R., Garzon M.H.. Statistical-mechanical Treatment of Error in the Annealing Biostep of DNA Computation, Proc. GECCO-99 conference, Morgan-Kaufmann, 1829-1834.
[127] Marathe, A.; Condon, A. E.; Corn, R. M. On Combinatorial DNA Code Design. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999; Vol. 44, pp75-87.
[128] Edge R. Wang, 夏令伟. 核酸探针的合成、标记及应用. 北京:科学出版社,1998.
[129] Qi Ouyang,Peter D.Kaplan,Shumao Liu,Albert Libchaber. DNA Solution of the Maximal Clique Problem. Science,October 1997,278(17): 446-449.
[130] Stemmer W. DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution. Proc. Natl. Acad. Sci. 1994, 91:10747-10751.
[131] Stemmer W. Rapid evolution of a protein in vitro by DNA shuffling. Nature, 1994, 370, 389-391.
[132] Stemmer,W.P., Crameri,A., Ha,K.D., Brennan,T.M. and Heyneker,H.L. (1995) Single-step assembly of a gene and entire plasmid from large numbers of oligonucleotides. Gene, 164, 49–53.
[133] Khorana H G. Total synthesis of a gene. Science, 1979, 203: 614~625.
[134] 吴乃虎. 基因工程原理(上册). 北京:科学出版社,2001,82~89.
[135] 沈同,王镜岩. 生物化学(第二版下册),302~315.
[136] Beaucage, S L and Caruthers M H. 1981, Tetrahedron Letters, 22: 1859.
[137] Smith,J., Cook,E., Fotheringham,I., Pheby,S., Derbyshire,R.,Eaton,M.A., Doel,M., Lilley,D.M., Pardon,J.F., Patel,T., Lewis,H. and Bell,L.D. (1982) Chemical synthesis and cloning of a gene for human beta-urogastrone. Nucleic Acids Res., 10, 4467–4482.
[138] Edge,M.D., Greene,A.R., Heathcliffe,G.R., Moore,V.E., Faulkner,N.J., Camble,R., Petter,N.N., Trueman,P., Schuch,W. and Hennam,J. (1983) Chemical synthesis of a human interferon-alpha 2 gene and its expression in Escherichia coli. Nucleic Acids Res., 11, 6419–6435. [ 139 ] Jay,E., MacKnight,D., Lutze-Wallace,C., Harrison,D., Wishart,P., Liu,W.Y., Asundi,V., Pomeroy-Cloney,L., Rommens,J. and Eglington,L. (1984) Chemical synthesis of a biologically active gene for human immune interferon-gamma. Prospect for site-specific mutagenesis and structure-function studies. J. Biol. Chem., 259, 6311–6317.
[140] Sproat,B.S. and Gait,M.J. (1985) Chemical synthesis of a gene for somatomedin C. Nucleic Acids Res., 13, 2959–2977.
[141] Ecker,D.J., Khan,M.I., Marsh,J., Butt,T.R. and Crooke,S.T. (1987) Chemical synthesis and expression of a cassette adapted ubiquitin gene. J. Biol. Chem., 262, 3524–3527.
[142] Ashman,K., Matthews,N. and Frank,R.W. (1989) Chemical synthesis, expression and product assessment of a gene coding for biologically active human tumour necrosis factor alpha. Protein Eng., 2, 387–391.
[143] Mandecki,W. and Bolling,T.J. (1988) FokI method of gene synthesis. Gene, 68, 101–107.
[144] Dillon,P.J. and Rosen,C.A. (1990)Arapid method for the construction of synthetic genes using the polymerase chain reaction. Biotechniques, 9, 298–300.
[145] Prodromou,C. and Pearl,L.H. (1992) Recursive PCR: a novel technique for total gene synthesis. Protein Eng., 5, 827–829. [ 146 ] Ciccarelli,R.B., Gunyuzlu,P., Huang,J., Scott,C. and Oakes,F.T. (1991) Construction of synthetic genes using PCR after automated DNA synthesis of their entire top and bottom strands. Nucleic Acids Res., 19, 6007–6013.
[147] Hayashi,N., Welschof,M., Zewe,M., Braunagel,M., Dubel,S., Breitling,F. and Little,M. (1994) Simultaneous mutagenesis of antibody CDRregions by overlap extension and PCR. Biotechniques, 17, 310–315.
[148] Strizhov,N., Keller,M., Mathur,J., Koncz-Kalman,Z., Bosch,D., Prudovsky,E., Schell,J., Sneh,B., Koncz,C. and Zilberstein,A. (1996) A synthetic cryIC gene, encoding a Bacillus thuringiensis delta-endotoxin, confers Spodoptera resistance in alfalfa and tobacco. Proc. Natl Acad. Sci. USA, 93, 15012–15017.
[149] Gao,X., Yo,P., Keith,A., Ragan,T.J. and Harris,T.K. (2003) Thermodynamically balanced inside-out (TBIO) PCR-based gene synthesis: a novel method of primer design for highfidelity assembly of longer gene sequences. Nucleic Acids Res., 31:143.
[150] David,M.H. and Jacek,L. (2002) DNAWorks: an automated method for designing oligonucleotides for PCR-based gene synthesis. Nucleic Acids Res., 30,:43.
[151] Peter D.Kaplan,Qi Ouyang et al. Parallel Overlap Assembly for the Construction of Computational DNA Libraries. J. theor. Biol., 1997, 188: 333~341.
[ 152 ] 刘文斌, 高琳等. 最大匹配问题的DNA 表面计算模型. 电子学报,2003,10:1496-1499.
[153] 王书栋,许进等.图的最小顶点覆盖问题的面上DNA 解法.小型微型计算机系统,2004,2:242-244.
[154] 高琳,马瑞年等.有向最短哈密尔顿路问题的DNA 算法.系统工程与电子技术2002,8:102-105.
[155] 殷志祥,张风月等.0-1 规划问题的DNA 计算.电子与信息学报,2003,1:62-66
[156] 刘文斌,王书栋等.可满足性(SAT)问题的几种DNA 计算模型.小型微型计算机系统, 2004, 7: 1321-1325
[157] G.Rozenberg, A.Salomaa. Watson-Crick complementarity, universal computations and genetic engineering. Techn. Report 96-28, Dept. of Computer Science, Leiden Univ., Oct. 1996.
[ 158 ] J.Engelfriet, G.Rozenberg, Fixed point languages, equality languages, and representations of recursively enumerable languages. Journal of the ACM, 27(1980), 499-518.
[159] A.Salomaa. Jewels of Formal Language Theory. Computer Science Press, Rockville, Md.,1981.
[160] Foder S P, Read J L, Pirrung M C, et al. Light-directed, spatially addressable parallel chemical synthesis. Science, 1991, 251(4995):767-773.
[161] Rehman F N, Audeh M, Abrams E S, et al. Immobilization of acrylamide-modified oligonucleotides by co-polymerization. Nucleic Acids Res, 1999, 27: 649-655.
[162] Marshall A and Hodgson J. DNA chips: an array of possibilities. Nat Biotechnol, 1998, 16: 27-31.
[163] Bobrow M N and Litt G J. Method for the detection or quantification of an analyte using an analyte dependent enzyme activation system. United State Patent, [5, 731,158].1993.
[164] Lizardi P M, Huang X, Zhu Z, et al. Mutation detection and single-molecule counting using isothermal rolling-circle amplification. Nat Genet, 1998, 19: 225-232.
[165] Schweitzer B, Wiltshire S, Lambert J et al. Inaugural article: immunoassays with rolling circle DNA amplification: a versatile platform for ultrasensitive antigen detection. P Natl Acad Sci USA 2000, 97: 10113-10119.
[166] Adrian J. Harwood. Basic DNA and RNA Protocols. 盛小禹等译.北京:科学出版社,2002:203-215.
[167] 邢婉丽,程京.生物芯片技术.北京:清华大学出版社, 2004.
[168] 刘文斌,王书栋等.DNA 计算中的编码方法研究.计算机工程与应用, 2003, 27: 118-121.
[169] 楼士林,杨盛昌等. 基因工程. 北京: 科学出版社, 2002.
[2] 李承祖. 量子通信和量子计算机. 国防科技大学出版社, 2000.
[3] 陈虎, 戴葵, 胡守仁. 环行阵列神经网络计算机系统. 计算机研究与发展, 1999, 36(2):144-149.
[4] Vlatko V., Martin B.. Basic of Quantum Computation. Progress in Quantum Electronics, 1998, 22: 1-39.
[5] Hwang K.. Advanced Computer Architecture. NewYork, McGrawHill, 1991.
[6] Netterer F. The Mathematics of Computerized Tomography. NewYork, Wiley, 1986: 114-126.
[7] Gao F., Niu H., Zhao H.. A study on numerical simulation of imager construction in optical computer tomography. Bioimaging,1997,5(2) : 51～57.
[8] 许进, 保铮. 神经网络与图论. 中国科学(E 辑),2001,31(6): 533-555.
[9] 许进. DNA 计算与运筹学发展的新机遇. 《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company 香港,2000: 43-54(注:特邀大会主题报告).
[10] 许进, 张雷. DNA 计算机原理、进展及难点( Ⅰ):生物计算系统及其在图论中的应用. 计算机学报, 2003, 26(1):1-11.
[11] 许进, 董亚非,魏小鹏. 粘贴DNA 计算机模型(Ⅰ):理论. 科学通报, 2004,49(3):205-212.
[12] 许进, 李三平,董亚非,魏小鹏. 粘贴DNA 计算机模型(Ⅱ):应用. 科学通报, 2004,49(4):299-307.
[13] 丁永生,邵世煌,任立红. DNA 计算与软计算. 科学出版社,2002.10.
[14] Adleman L.. Molecular Computation of Solution to Combinatorial problems. Science. 1994,66 (11):1021-1024.
[15] Paun G., Rozenberg G., Salomaa A.. DNA Computing-New Computing Paradigms. Springer, 1998.
[ 16 ] Feyman R.P. There's plenty of room at the bottom, In Minaturization. D.H.Gilbert.ED. Reinhold, New York,1961, 282-296.
[17] Freund R., Paun G., Rozenberg G., et al.. Watson-Crick Finite Automata, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[18] Fu B., Beigel R.. Length bounded molecular computing. 4th Int. Meeting on DNA-Based Computing, Balti-more, Penns., (June, 1998).
[19] Fu B., Beigel R., Zhou F.. An O(2n) volume molecular algorithm for Hamiltonian Path. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[20] Roweis S., Winfree E., Burgoyne R., et al.. A sticker based architecture for DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996.
[21] Yoshikawa T.. Emergence of Effective Fuzzy Rules for Controling Mobile Robots Using DNA Coding Method. Proceeding of 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan ,1996, 5: 581-586.
[22] GuptaV., Parthasarathy S., Zaki M.J.. Arithmetic and Logic Operations with DNA. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[23] Hagiya M., Arita M., Kiga D., et al.. Towards Parallel Evaluation and Learning of Boolean -Formulas with Molecules. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June,1997).
[24] Gibbons A., Amos M., Hodgson D.. Models of DNA computation, Mathematical Foundations of Computer. Science. 1996, 1113: 18-36.
[25] Guarnieri Frank, Fliss M. and Bancroft C. Making DNA add. Science. 1996,273: 220-223.
[26] Rozen D. E., McGrew S., Ellington A. D.. Molecular computing: Does DNA computer. Current Biology, 1996, 6(3): 254-258.
[27] Adleman, L.M., Rothemun P.W.K., Roweis d. S., et al.. On Applying Molecular Computation To The Data Encryption Standard. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
[28] Lipton R. J.. DNA Solution of Hard Computation Problems. Science, 1995 , 268 (4) :542-545.
[29] 孟大志,曹海萍. DNA 计算与生物数学.生物物理学报, 2002, 18(2): 163-166.
[30] Roweis S., Winfree E., Burgoyne R., Chelyapov N., Goodman M., Rothemund P., Adleman L.. A sticker based arcchtecture for DNA computation.in: Baum E B et al(Eds),DNA Based Computers, Proc. 2nd Annual Meeting, Princeton, 1999: 1-27.
[31] Kari L., Paun G., Rozenberg G., et al.. DNA computing, sticker systems, and universality. Acta Informatica, 1998, 35: 401-420.
[32] Kazic T.. After the Turing machine: A meta model for molecular computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[33] Pixton D.. Linear and circular splicing systems, Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
[34] Mirkin C.A., Letsinger R.L., Mucic R.C., et al.. A DNA-based Method for Rationally Assembling Nanoparticles Into Macroscopic Materials. Nature, 1996, 382: 607-611.
[35] Gatterdam R. W.. DNA and twist free splicing systems, in words, languages andcombinatorics. Singapore, World Scienctific Publishers, 1994.
[36] Khodor J., and David K. G.. The Efficiency of Sequence-Specific Separation of DNA Mixtures for Biological Computing. 3rd DIMACS Meeting on DNA Based Computers,Univ. of Penns., (June,1997).
[37] Kari L.. DNA computers: tomorrow's reality. Tutorial in the Bulletin of EATCS, 1996, 59: 256-266.
[38] Kari L., Sakakibara. Y.. DNA Computers Journal of the Institute of Electronics, Information and Communication Engineers, 80: 935-939, (in Japanese,1997).
[39] Kari L., Gloor G., Yu S.. Using DNA to solve the Bounded Post Correspondence Problem. Theoretical Computer Science, 2000, 231(2): 193-203.
[40] Freund R., Kari L., Paun G.. DNA computing based on splicing: The existence of universal computers. Theory of Computing Systems, 1999,32(1): 69-112.
[41] Kari L.. DNA computing based on insertions and deletions. Proceedings of the conference Conceptual tools for understanding dynamics in biological systems, London, 1996. In COENOSES, C.E.T.A. Gorizia, Italy, N.Kenkel, ed., 1997, 12: 89-95.
[42] Deninnghoff K. L., Gatterdam R. W.. On the Undecidability of splicing systems. Int. J. Computer Math., 1989, 27: 133-145.
[43] Paun G.. On the power of splicing operation. Int. J. Computer Math.,1995, 59: 7-35. [ 44 ] Kobyshi S. S., Szkaibara Y. B.. Multiple splicing systems and universal computability. Theoretical Computer Science, 2001, 264(1): 3-23.
[45] Paun G.. DNA computing based on splicing: Universality results. Theoretical Computer Science, 2000, 231(2): 275-296.
[46] Sakakibara Y. B., Ferreti C.. Splicing on tree-like structures. Theoretical Computer Science, 1999, 210(2): 227-243.
[47] Paun G., Mauri G., Kobayashi S., Yokomori T.. On the universality of Post and splicing systems. Theoretical Computer Science, 2000, 231(2):157-170.
[48] Paun G.. Splicing systems with targets are computationally universal. Information Processing Letters, 1996, 59(3):129-133.
[49] Mateesu A., Paun G., Rozenberg G., Salomaa A., Simple splicing systems. Discrete Applied Mathematics, 1998, 84(1-3):145-163.
[50] Adleman L.. On Constructing a Molecular Computing. Technical Report TR 79-387, Computer science Department ,University of Southern California, USA, January 1995.
[51] RooβD. and Wagner K. W. On the power of DNA-computing. Information and Computation. 1996. 131(2):95-109. [ 52 ] Mark Daley, Lila Kari, Greg Gloor, Rani Siromoney. Circular Contextual Insertions-Deletions with Applications to Biomolecular Computation, Manuscript, 1998. [ 53 ] L.Kari, G..Thierrin. Contextual Insertions-Deletions and Computability. Inf. Comput., 1996, 131, 47–61.
[54] C. Martin-Vide, Gh.P?un, A. Salomaa. Characterizations of Recursively Enumerable Languages by means of Insertion Grammars. Theoretical Computer Science, 205,1-2 (1998), 195-205.
[55] L.Kari, G.P?un, G.Thierrin, S.Yu. At the Crossroads of DNA Computing and Formal Languages: Characterizing Recursively Enumerable Languages by Insertion-Deletion Systems. In DNA Based Computers III, H.Rubin, D.Wood, eds, DIMACS Series, vol.48, 1999, AMS Press, 329-347.
[56] A.Takahara. On the Computational Power of Insertion-Deletion Systems. Proc. of 8th International Meeting on DNA Based Computers, June, Sapporo, 139-150, 2002.
[57] Tiina Zingel. Formal Model of DNA Computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 49(2)(2000): 90–99.
[58] T. Head. Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors. Bull. Math. Bio., 1987, l49: 737-759.
[59] Kari L. DNA Computing: Arrival of Biological Mathematics. The Mathematical Intelligencer, 1997, 19(2): 9-22.
[60] P?un G., Rozenberg G., Salomaa A.. DNA Computing. Springer, 1998: 10-41.
[61] T. Head. Splicing Schemes and DNA, In: Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics and Developmental Biology, Ed. By G.Rozenberg and A.Salomaa, Springer-Verlag, 1992, 371-383.
[62] Gh.P?un, A.Salomaa. DNA Computing Based on the Splicing Operation. Math. Japonica 1996, 43(3): 607-632.
[63] Katrin Erk. Simulating Boolean Circuits by Finite Splicing. In Proceedings of the Congress on Evolutionary Computation (CEC'99), Washington D.C., USA, July 6-9, 1999.
[64] Yokomori, T., Kobayashi, S. DNA-EC: A Model of DNA-computing Based on Equality Checking. In 3rd DIMACS Workshop on DNA-Based Computers, 1997, 334–345.
[65] E.Csuhaj-Varju, R.Freund, F. Wachtler. Test Tube Distributed Systems based on Splicing. Computer and AI, 15, 2-3 (1996), 211-232.
[66] K.Culik II, T. Harju. Splicing Semigroups of Dominoes and DNA. Discrete Appl. Math., 31(1991), 261-277.
[67] J.Dassow, V.Mitrana. Splicing Grammar Systems. Computer and AI, 15, 2-3 (1996), 109-122.
[68] L.Kari, Gh.P?un, A. Salomaa. The Power of Restricted Splicing with Rules from a Regular Set. J. Universal Computer Sci., 2, 4(1996), 224-240.
[69] Pixton D. Linear and Circular Splicing Systems. Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
[70] Rudolf Freund. Splicing Systems on Graphs. Manuscript, 1995. [ 71 ] Y. Benenson, T. Paz-Elizur, R. Adar, E. Kelnan, Z. Livneh, E.Shapiro. Programmable and Autonomous Computing Machine Made of Biomolecules. Nature 414 (22), (2001) 430-434.
[72] Roweis, et al. A Sticker Based Model for DNA Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44, 1-27.
[73] P?un Gh, Rozenberg G. Sticker Systems. Theoretical Computer Science 204 (1998): 183-203.
[74] T.Lai, K.H. Zimmermann. A Software Platform for the Sticker Model. Techn. Report, No. 2001.2, Dept. Computer Engineering, TU Hamburg-Harburg, 2001.
[75] K.H. Zimmermann. DNA Sticker Algorithms for Binary Linear Codes. IEEE Trans. Infor. Theory, to appear. [ 76 ] Y.Sakakibara, S.Kobayashi. Sticker Systems with Complex Structures. Soft Computing 5 (2001): 114-120.
[77] Karl-Heinz Zimmerman. Efficient DNA Sticker Algorithms for NP-Complete Graph Problems. Computer Physics Communications, 2002,144: 297-309.
[78] Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002, 11(2): 280-284.
[79] 许进, 董亚非. 粘贴DNA 计算模型理论及应用. 科学通报, 2003, 48: (12).
[80] Wenbin Liu, Shudong Wang, Jin Xu. Solving the 3-SAT Problem Based on DNA Computing. J. Chem. Inf. Comput. Sci. 2003.11.
[81] Nishikawa A., Hagiya M., Yamamura M.. Virtul DNA Simulator and protocol design by GA. Proc. The Genetic and Evolutionary Computation Conference. Orlando. FL. USA. July 13-17,1999:1810-1816.
[82] Mulawka J. J., Wasiewicz P., Pietak K.. Virus-enhanced genetic algorithms inspired by DNA Computing. 11th International Symposium and Methodologies for Intelligent Systems. Warsaw. Poland. 8-11 June 1999: 529-537.
[83] Boneh D., and Lipton R. J.. A Divide and conquer approach to DNA sequencing. Princeton University, 1996.
[84] Lipton R.. A memory based attack on cryptosystems with application to DNA computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[85] Head T., Kaolan P. D., Bladergroen R. R., et al. Computing with DNA by operating on plasmids. Biosystem, 2000, 57: 87-93.
[86] 高琳, 马润年, 许进. 基于质粒DNA 匹配问题的分子算法. 生物化学与生物物理进展, 2002(5): 820-822.
[87] 张连珍, 许进. 基于质粒的DNA 计算模型研究. 计算机工程与应用, 2004, 40(1).
[88] Cukras A., Faulhammer D., Lipton R., et al.. Chess games: A model for RNA-based computation. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[89] Liu Q. H., Guo Z., Condon A. E., et al.. A surface-based approach to DNA computation. In Proceedings of the Second Annual Meeting on DNA Based Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Providence, PI: American Mathematical Society; 1996.
[90] Liu Q. H., Guo Z., Condon A. E., et al.. DNA Computing on Surfaces, Nature, 2000, 403: 175-179.
[91] Liu Q., Frutos A., Wang L., et al.. Progress towards demonstration of a surface based DNA computation: A one word approach to solve a model satiability problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998).
[ 92 ] Wu H. Y.. An improved surface-based method for DNA computation. Biosystems,2001, 59(1): 1-5.
[93] Sakamoto k.. Molecular Computation by DNA Hairpin Formation. Science, 2000,283: 1223-1227.
[94] Braich, R. S., Chelyapov, N., Johnson, C., Rothemund, P.W.K., Adleman, L.. Solution of a 20-Variable 3-SAT Problem on a DNA Computer. Science , 2002, 296: 499-502.
[95] Mccammon, J., and S. Harvey, Dynamics of Proteins and Nucleic Acids, Cambridge University Press, (1987).
[96] Plum, G.E., and D. S. Pilch, Nucleic Acid Hybridize: Triplex Stability and Energetics., Annu. Rev. Biophys. Biomol. Struct. , 24:, 319{350, (February 1997).
[97] Hartemink, A.J., D.K. Giord Thermodynamic Simulation of Deoxyoligonucleotide Hybridize for DNA Computation, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[98] Watson, J., M. Gilman, J. Witkowski, M. Zoller, Recombinant DNA (2nd ed.), Scientic American Books, W.H. Freeman and Co., (1992).
[99] Watson, J., N. Hoplins, J. Roberts, et. al., Molecular Biology of the Gene, Benjamin/Cummings, Menlo Park, CA, (1987).
[100] Alberts, B., Bray, D., Lewis, J., Raff, M., Roberts, K., Watson, J. 1994. Molecular Biology of the Cell. 3rd ed. New York: Garland Publishing.
[101] Sambrook, J., E. Fritsch, and T. Maniatis, Molecular Cloning: A Laboratory Manual, Cold Spring Harbor Laboratory Press, NY, Vol. 1,2,3 (1989).
[102] Boneh, D., and R. Lipton, Making DNA Computers Error Resistant, Princeton CS Tech-Report CS-TR-491-95 Also in 2nd Annual DIMACS Meeting on DNA Based Computers,, Princeton University, June 1996.
[103] Amos, M., A. Gibbons, D. Hodgson, Error-resistant Implementation of DNA Computations, 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
[104] Deputat, M., G. Hajduczok, E. Schmitt, On Error-Correcting Structures Derived from DNA, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[105] Freud. R, Freud. F. Proceeding of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97). Indian apolis, IN USA, 1997. 237-242.
[106] Cai, W., A. Condon, R.M. Corn, Z. Fei, T. Frutos, E. Glaser, Z. Guo, M.G. Lagally, Q. Liu, L.M. Smith, and A. Thiel, The Power of Surface-Based Computation, Proc. First International Conference on Computational Molecular Biology (RECOMB97), January, 1997.
[107] Smith L.M, Corn R.M., Condon A.E., et al. Journal of Computational Biology, 1998, 5(2):255—267.
[108] Liu, Q., A.J. Thiel, A.G. Frutos, R.M. Corn, L.M. Smith, Surface-Based DNA Computation: Hybridize and Destruction, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[109] Manca, V., C. Martin-Vide, G. Paun, New computing paradigms suggested by DNA computing by carving, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[110] Wang, L., Q. Liu, A. Frutos, S. Gillmor, A. Thiel, T. Strother, A. Condon, R. Corn, M. Lagally, L. Smith, Surface-based DNA computing operations: DESTROY and READOUT", 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[111] Eng, T., and B.M. Serridge, A Surface-Based DNA Algorithm for Minimal Set Cover, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[112] Liu, Q., A. Frutos, L. Wang, A. Thiel, S. Gillmor, T. Strother, A. Condon, R. Corn, M. Lagally, L. Smith, Progress towards demonstration of a surface based DNA computation: A one word approach to solve a model satiability problem, 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
[113] Smith L.M, Corn R.M., Condon A.E., et al. Journal of Computational Biology, 1998, 5(2):255—267.
[114] Frutos, A.G., A.J. Thiel, A.E. Condon, L.M. Smith, R.M. Corn, DNA Computing at Surfaces: 4 Base Mismatch Word Design, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
[115] Leonard M Adleman. Molecular Computation of Solutions to Combinatorial Problems, Science. November 1994, 266(11): 1021-1023.
[116] Lipton R. J.. DNA Solution of Hard Computation Problems. Science, 1995, 268 (4) : 542-545.
[117] Baum E B. DNA sequences useful for computation. In DNA based Computers:Proceedings of the DIMACS Workshop, June 10, 1996, Princeton University (eds Laura F. Landweber, Eric B. Baum)(DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44 :235-241).
[118] Deaton R. et al. Good Encodings for DNA-Based Solutions to Combinatorial Problems. In DNA based Computers:Proceedings of the DIMACS Workshop, June 10, 1996, Princeton University (eds Laura F. Landweber, Eric B. Baum)(DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44 :247-258).
[119] Baum E B. Building an associative memory vastly larger than the brain. Science, 268: 583-585, 1995.
[120] Garzon, M., Neathery, P., Deaton, R.J., Murphy, R..C., Franceschetti, D.R., Stevens, S.E.Jr.. A new metric for DNA Computing. Proceedings of the 2nd Annual Genetic Programming Conference, 1997,472-487.
[121] Garzon M., Deaton R., Nino L.F., Stevens S.E. , Wittner M.. Genome Encoding for DNA Computing. The Third DIMACS Workshop on DNA-based Computing, U of Pennsylvania, 1997, 230-237.
[122] Deaton R. and Garzon M.. Thermodynamic Constraints on DNA-based Computing, in Computing with Bio-Molecues: Theory and Expirements. ed. G. Paun, Springer-Verlag: Singapore, 1998, 138-152.
[123] Deaton R., Franceschetti D. R., Garzon M., Rose J. A., Murphy R. C., and Stevens S. E.. Information transfer through hybridyzation reaction in DNA based computing. Proceedings of the Second Annual Conference, 1997, July 13-16, Stanford University, (Morgan Kaufmann, San Francisco, 463-471.
[124] Deaton R. et al. A DNA Based Implementation of an Evolutionary Computation. Proceedings IEEE Conference on Evolutionary Computation. Indiana, 1997, 267-271.
[125] Rose J.A., The Fidelity of DNA computation, Ph. D thesis, The University of Memphis, 1999. 11.
[126] Rose J.A., Deaton R.J., Franceschetti D.R., Garzon M.H.. Statistical-mechanical Treatment of Error in the Annealing Biostep of DNA Computation, Proc. GECCO-99 conference, Morgan-Kaufmann, 1829-1834.
[127] Marathe, A.; Condon, A. E.; Corn, R. M. On Combinatorial DNA Code Design. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999; Vol. 44, pp75-87.
[128] Edge R. Wang, 夏令伟. 核酸探针的合成、标记及应用. 北京:科学出版社,1998.
[129] Qi Ouyang,Peter D.Kaplan,Shumao Liu,Albert Libchaber. DNA Solution of the Maximal Clique Problem. Science,October 1997,278(17): 446-449.
[130] Stemmer W. DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution. Proc. Natl. Acad. Sci. 1994, 91:10747-10751.
[131] Stemmer W. Rapid evolution of a protein in vitro by DNA shuffling. Nature, 1994, 370, 389-391.
[132] Stemmer,W.P., Crameri,A., Ha,K.D., Brennan,T.M. and Heyneker,H.L. (1995) Single-step assembly of a gene and entire plasmid from large numbers of oligonucleotides. Gene, 164, 49–53.
[133] Khorana H G. Total synthesis of a gene. Science, 1979, 203: 614~625.
[134] 吴乃虎. 基因工程原理(上册). 北京:科学出版社,2001,82~89.
[135] 沈同,王镜岩. 生物化学(第二版下册),302~315.
[136] Beaucage, S L and Caruthers M H. 1981, Tetrahedron Letters, 22: 1859.
[137] Smith,J., Cook,E., Fotheringham,I., Pheby,S., Derbyshire,R.,Eaton,M.A., Doel,M., Lilley,D.M., Pardon,J.F., Patel,T., Lewis,H. and Bell,L.D. (1982) Chemical synthesis and cloning of a gene for human beta-urogastrone. Nucleic Acids Res., 10, 4467–4482.
[138] Edge,M.D., Greene,A.R., Heathcliffe,G.R., Moore,V.E., Faulkner,N.J., Camble,R., Petter,N.N., Trueman,P., Schuch,W. and Hennam,J. (1983) Chemical synthesis of a human interferon-alpha 2 gene and its expression in Escherichia coli. Nucleic Acids Res., 11, 6419–6435. [ 139 ] Jay,E., MacKnight,D., Lutze-Wallace,C., Harrison,D., Wishart,P., Liu,W.Y., Asundi,V., Pomeroy-Cloney,L., Rommens,J. and Eglington,L. (1984) Chemical synthesis of a biologically active gene for human immune interferon-gamma. Prospect for site-specific mutagenesis and structure-function studies. J. Biol. Chem., 259, 6311–6317.
[140] Sproat,B.S. and Gait,M.J. (1985) Chemical synthesis of a gene for somatomedin C. Nucleic Acids Res., 13, 2959–2977.
[141] Ecker,D.J., Khan,M.I., Marsh,J., Butt,T.R. and Crooke,S.T. (1987) Chemical synthesis and expression of a cassette adapted ubiquitin gene. J. Biol. Chem., 262, 3524–3527.
[142] Ashman,K., Matthews,N. and Frank,R.W. (1989) Chemical synthesis, expression and product assessment of a gene coding for biologically active human tumour necrosis factor alpha. Protein Eng., 2, 387–391.
[143] Mandecki,W. and Bolling,T.J. (1988) FokI method of gene synthesis. Gene, 68, 101–107.
[144] Dillon,P.J. and Rosen,C.A. (1990)Arapid method for the construction of synthetic genes using the polymerase chain reaction. Biotechniques, 9, 298–300.
[145] Prodromou,C. and Pearl,L.H. (1992) Recursive PCR: a novel technique for total gene synthesis. Protein Eng., 5, 827–829. [ 146 ] Ciccarelli,R.B., Gunyuzlu,P., Huang,J., Scott,C. and Oakes,F.T. (1991) Construction of synthetic genes using PCR after automated DNA synthesis of their entire top and bottom strands. Nucleic Acids Res., 19, 6007–6013.
[147] Hayashi,N., Welschof,M., Zewe,M., Braunagel,M., Dubel,S., Breitling,F. and Little,M. (1994) Simultaneous mutagenesis of antibody CDRregions by overlap extension and PCR. Biotechniques, 17, 310–315.
[148] Strizhov,N., Keller,M., Mathur,J., Koncz-Kalman,Z., Bosch,D., Prudovsky,E., Schell,J., Sneh,B., Koncz,C. and Zilberstein,A. (1996) A synthetic cryIC gene, encoding a Bacillus thuringiensis delta-endotoxin, confers Spodoptera resistance in alfalfa and tobacco. Proc. Natl Acad. Sci. USA, 93, 15012–15017.
[149] Gao,X., Yo,P., Keith,A., Ragan,T.J. and Harris,T.K. (2003) Thermodynamically balanced inside-out (TBIO) PCR-based gene synthesis: a novel method of primer design for highfidelity assembly of longer gene sequences. Nucleic Acids Res., 31:143.
[150] David,M.H. and Jacek,L. (2002) DNAWorks: an automated method for designing oligonucleotides for PCR-based gene synthesis. Nucleic Acids Res., 30,:43.
[151] Peter D.Kaplan,Qi Ouyang et al. Parallel Overlap Assembly for the Construction of Computational DNA Libraries. J. theor. Biol., 1997, 188: 333~341.
[ 152 ] 刘文斌, 高琳等. 最大匹配问题的DNA 表面计算模型. 电子学报,2003,10:1496-1499.
[153] 王书栋,许进等.图的最小顶点覆盖问题的面上DNA 解法.小型微型计算机系统,2004,2:242-244.
[154] 高琳,马瑞年等.有向最短哈密尔顿路问题的DNA 算法.系统工程与电子技术2002,8:102-105.
[155] 殷志祥,张风月等.0-1 规划问题的DNA 计算.电子与信息学报,2003,1:62-66
[156] 刘文斌,王书栋等.可满足性(SAT)问题的几种DNA 计算模型.小型微型计算机系统, 2004, 7: 1321-1325
[157] G.Rozenberg, A.Salomaa. Watson-Crick complementarity, universal computations and genetic engineering. Techn. Report 96-28, Dept. of Computer Science, Leiden Univ., Oct. 1996.
[ 158 ] J.Engelfriet, G.Rozenberg, Fixed point languages, equality languages, and representations of recursively enumerable languages. Journal of the ACM, 27(1980), 499-518.
[159] A.Salomaa. Jewels of Formal Language Theory. Computer Science Press, Rockville, Md.,1981.
[160] Foder S P, Read J L, Pirrung M C, et al. Light-directed, spatially addressable parallel chemical synthesis. Science, 1991, 251(4995):767-773.
[161] Rehman F N, Audeh M, Abrams E S, et al. Immobilization of acrylamide-modified oligonucleotides by co-polymerization. Nucleic Acids Res, 1999, 27: 649-655.
[162] Marshall A and Hodgson J. DNA chips: an array of possibilities. Nat Biotechnol, 1998, 16: 27-31.
[163] Bobrow M N and Litt G J. Method for the detection or quantification of an analyte using an analyte dependent enzyme activation system. United State Patent, [5, 731,158].1993.
[164] Lizardi P M, Huang X, Zhu Z, et al. Mutation detection and single-molecule counting using isothermal rolling-circle amplification. Nat Genet, 1998, 19: 225-232.
[165] Schweitzer B, Wiltshire S, Lambert J et al. Inaugural article: immunoassays with rolling circle DNA amplification: a versatile platform for ultrasensitive antigen detection. P Natl Acad Sci USA 2000, 97: 10113-10119.
[166] Adrian J. Harwood. Basic DNA and RNA Protocols. 盛小禹等译.北京:科学出版社,2002:203-215.
[167] 邢婉丽,程京.生物芯片技术.北京:清华大学出版社, 2004.
[168] 刘文斌,王书栋等.DNA 计算中的编码方法研究.计算机工程与应用, 2003, 27: 118-121.
[169] 楼士林,杨盛昌等. 基因工程. 北京: 科学出版社, 2002.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |