四类DNA计算模型中一些理论与应用的研究
|
摘要
本文对四类DNA计算模型中的一些理论及其应用进行了研究和讨论,具体工作如下:
粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson- Crick互补性质进行退火操作的DNA计算抽象模型。本文将线性串的粘贴系统拓展到带有发夹结构的双向复杂结构粘贴系统,使粘贴系统的纯理论研究向实际生物操作技术研究迈进了一步。给出了双向复杂结构粘贴系统的定义及其基本运算;提出了双向复杂结构粘贴系统的分类;讨论了双向复杂结构粘贴系统的生成能力和计算能力;最后,通过双向复杂结构粘贴系统的弱编码刻画了递归可列语言,这表明双向复杂结构粘贴系统与递归可列语言族有相同的计算能力。
粘贴模型有一个随机存取存储器,所使用的DNA链具有固定长度,操作时不需扩展DNA链,也无需酶的参与,并且它的材料在理论上可以重复使用。本文给出了图顶点着色问题的DNA粘贴算法。在研究图顶点着色问题时,从问题的本质出发,先把图的顶点着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法以解决图的顶点着色问题。
图的全着色猜想是由M.Behzad和Vizing于1965年提出的。到目前为止,对于一般的图,全着色猜想仍然是一个公开的问题。本文从系列平行图的结构性质出发,利用双重归纳法和换色技巧确定了系列平行图的全色数。
剪接系统是将剪接运算当作基本算子的一种语言生成器,其中剪接运算是对在限制性内切酶、DNA连接酶、DNA聚合酶和外切酶作用下,DNA链进行重组过程的数学抽象。本文利用剪接系统的巨大并行性,首先设计了模拟有向哈密顿路问题的剪接系统;然后通过此剪接系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图的若干结构性质以及图中存在有向哈密顿路的充要条件。
图的最小顶点覆盖问题是图论中的一个NP完全问题。它在分子生物学、调度问题、错误诊断和恢复集装线平衡、油轮行程安排及开关理论中有着广泛的应
用。本文利用DNA表面计算模型对图的最小顶点覆盖问题进行了建模。构造了含有个顶点条边的图的顶点集子集对应的数据池之后,循环进行了合成、杂交、清洗、变性等生物操作,得到所有覆盖对应的DNA序列,然后通过编址过程得到我们所要求的最小顶点覆盖。最后通过个顶点条边的图对所建模型进行了验证。
In the thesis, some theories and applications in four types of DNA computation models are studied and discussed. The main results are summarized as follows:
The sticker system is a language generative mechanism based on sticking operations and a DNA computation abstract model that follows Watson-Crick complementarity relation to anneal. In this dissertation, the sticker systems of linear string are extended to bidirectional sticker systems with complex structures, which makes the pure theoretical study step forward to biologic operation techniques. The definition and basic operations of bidirectional sticker systems with complex structures are given out. The classifications of bidirectional sticker systems with complex structures are proposed. The generative and computational capacities of bidirectional sticker systems with complex structures are discussed. Finally, the characterization of recursively enumerable language is presented by means of weak coding of the above systems, which means that bidirectional sticker systems with complex structures have the same computational capacity as the family of recursively enumerable languages.
The sticker model has a random access memory and its DNA strands have a fixed length. The operations require no strands extension, use no enzymes, and its materials are reusable in theory. In the dissertation, DNA sticker algorithm of vertex-coloring problems is given out. When the vertex-coloring problems of graph being studied, they are decomposed into vertex-independent set problems and vertex-partition problems from the essence of problems and DNA sticker algorithms of the two problems are showed; Then the vertex-coloring problems of graph are solved by transferring the above two algorithms.
In 1965, M.Behzad and Vizing proposed the Total Coloring Conjecture of graphs. So far, for any graph, the Total Coloring Conjecture is still an open problem. In this dissertation, the total chromatic number of series-parallel graphs of maximum degree
greater than or equal to will be determined using the double inductions and the techniques of exchanging colors from the aspect of configuration property.
The splicing system is a language generative mechanism based on splicing operations, where splicing operations are the mathematical abstractions of DNA strands recombinant behaviors under restriction exonucleases, endonucleases, DNA ligases and DNA polymerases. In this dissertation, the ideas of simulating directed Hamilton path problems by splicing systems are designed using their massive parallelism; Then some properties of directed graphs and sufficiency and necessity conditions of existing Hamilton paths in graphs are presented based on the analysis to directed Hamilton path problems according to the properties of languages generated by the splicing systems. In our construction, the splicing systems simulating problems run at most steps, where is the size of problems.
The minimal vertex-covering problem of graph is a NP-complete problem of graph theory. It may apply widely to molecular biology, schedule problem, error diagnosis, the balance of resume and collection, the journey plan of oil tanker and switch theory. In the dissertation, the minimal vertex-covering problems are studied from the point of computational models based on surface. In the DNA computational models on surface, after a data pool being constructed corresponding to the subsets of a vertex-set of a graph with vertices and edges, a series of biochemical experiments: synthesis, hybridization, cleaning and denaturalization etc are proceeded and the DNA sequences corresponding to all the coverings are obtained; Then all the minimal coverings according to the encoding address procedure are listed. After all, the built models are verified by a graph with vertices and edges.
粘贴系统是建立在粘贴运算基础上的语言生成器,也是一种遵循Watson- Crick互补性质进行退火操作的DNA计算抽象模型。本文将线性串的粘贴系统拓展到带有发夹结构的双向复杂结构粘贴系统,使粘贴系统的纯理论研究向实际生物操作技术研究迈进了一步。给出了双向复杂结构粘贴系统的定义及其基本运算;提出了双向复杂结构粘贴系统的分类;讨论了双向复杂结构粘贴系统的生成能力和计算能力;最后,通过双向复杂结构粘贴系统的弱编码刻画了递归可列语言,这表明双向复杂结构粘贴系统与递归可列语言族有相同的计算能力。
粘贴模型有一个随机存取存储器,所使用的DNA链具有固定长度,操作时不需扩展DNA链,也无需酶的参与,并且它的材料在理论上可以重复使用。本文给出了图顶点着色问题的DNA粘贴算法。在研究图顶点着色问题时,从问题的本质出发,先把图的顶点着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法以解决图的顶点着色问题。
图的全着色猜想是由M.Behzad和Vizing于1965年提出的。到目前为止,对于一般的图,全着色猜想仍然是一个公开的问题。本文从系列平行图的结构性质出发,利用双重归纳法和换色技巧确定了系列平行图的全色数。
剪接系统是将剪接运算当作基本算子的一种语言生成器,其中剪接运算是对在限制性内切酶、DNA连接酶、DNA聚合酶和外切酶作用下,DNA链进行重组过程的数学抽象。本文利用剪接系统的巨大并行性,首先设计了模拟有向哈密顿路问题的剪接系统;然后通过此剪接系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图的若干结构性质以及图中存在有向哈密顿路的充要条件。
图的最小顶点覆盖问题是图论中的一个NP完全问题。它在分子生物学、调度问题、错误诊断和恢复集装线平衡、油轮行程安排及开关理论中有着广泛的应
用。本文利用DNA表面计算模型对图的最小顶点覆盖问题进行了建模。构造了含有个顶点条边的图的顶点集子集对应的数据池之后,循环进行了合成、杂交、清洗、变性等生物操作,得到所有覆盖对应的DNA序列,然后通过编址过程得到我们所要求的最小顶点覆盖。最后通过个顶点条边的图对所建模型进行了验证。
In the thesis, some theories and applications in four types of DNA computation models are studied and discussed. The main results are summarized as follows:
The sticker system is a language generative mechanism based on sticking operations and a DNA computation abstract model that follows Watson-Crick complementarity relation to anneal. In this dissertation, the sticker systems of linear string are extended to bidirectional sticker systems with complex structures, which makes the pure theoretical study step forward to biologic operation techniques. The definition and basic operations of bidirectional sticker systems with complex structures are given out. The classifications of bidirectional sticker systems with complex structures are proposed. The generative and computational capacities of bidirectional sticker systems with complex structures are discussed. Finally, the characterization of recursively enumerable language is presented by means of weak coding of the above systems, which means that bidirectional sticker systems with complex structures have the same computational capacity as the family of recursively enumerable languages.
The sticker model has a random access memory and its DNA strands have a fixed length. The operations require no strands extension, use no enzymes, and its materials are reusable in theory. In the dissertation, DNA sticker algorithm of vertex-coloring problems is given out. When the vertex-coloring problems of graph being studied, they are decomposed into vertex-independent set problems and vertex-partition problems from the essence of problems and DNA sticker algorithms of the two problems are showed; Then the vertex-coloring problems of graph are solved by transferring the above two algorithms.
In 1965, M.Behzad and Vizing proposed the Total Coloring Conjecture of graphs. So far, for any graph, the Total Coloring Conjecture is still an open problem. In this dissertation, the total chromatic number of series-parallel graphs of maximum degree
greater than or equal to will be determined using the double inductions and the techniques of exchanging colors from the aspect of configuration property.
The splicing system is a language generative mechanism based on splicing operations, where splicing operations are the mathematical abstractions of DNA strands recombinant behaviors under restriction exonucleases, endonucleases, DNA ligases and DNA polymerases. In this dissertation, the ideas of simulating directed Hamilton path problems by splicing systems are designed using their massive parallelism; Then some properties of directed graphs and sufficiency and necessity conditions of existing Hamilton paths in graphs are presented based on the analysis to directed Hamilton path problems according to the properties of languages generated by the splicing systems. In our construction, the splicing systems simulating problems run at most steps, where is the size of problems.
The minimal vertex-covering problem of graph is a NP-complete problem of graph theory. It may apply widely to molecular biology, schedule problem, error diagnosis, the balance of resume and collection, the journey plan of oil tanker and switch theory. In the dissertation, the minimal vertex-covering problems are studied from the point of computational models based on surface. In the DNA computational models on surface, after a data pool being constructed corresponding to the subsets of a vertex-set of a graph with vertices and edges, a series of biochemical experiments: synthesis, hybridization, cleaning and denaturalization etc are proceeded and the DNA sequences corresponding to all the coverings are obtained; Then all the minimal coverings according to the encoding address procedure are listed. After all, the built models are verified by a graph with vertices and edges.
引文
许进, 保铮. 神经网络与图论. 中国科学(E辑), 2001, 31(6): 533-555.
李承祖. 量子通信和量子计算机. 国防科技大学出版社, 2000.
许进. DNA计算与运筹学发展的新机遇. 《中国运筹学会第六届学术交流会论文集》(上卷)(主编: 章祥荪, 王建方, 刘宝碇, 刘德刚), Global-Link Publishing Company 香港, 2000: 43-54(注:特邀大会主题报告) .
Gao F., Niu H., Zhao H. A Study on Numerical Simulation of Imager Construction in Optical Computer Tomography. Bioimaging, 1997, 5(2): 51-57.
邱道文. 量子计算机的刻画. 软件学报, 14,1(2003), 9-15.
Vlatko V., Martin B. Basic of Quantum Computation. Progress in Quantum Electronics, 1998, 22: 1-39.
邱道文. 基于量子逻辑的自动机和文法理论. 软件学报, 14,1(2003), 23-27.
Kari L.. DNA Computers: Tomorrow's Reality. Tutorial in the Bulletin of EATCS, 1996, 59: 256-266.
许进等. DNA 计算机原理、进展及难点(Ⅰ): 生物计算系统及其在图论中的应用. 计算机学报, 2003, 26(1):1-11.
Adleman L. Molecular Computation of Solution to Combinatorial problems. Science. 1994, 66 (11): 1021-1024.
Lipton R. J. DNA Solution of Hard Computation Problems. Science, 1995, 268 (4): 542-545.
任立红等. DNA计算研究的现状与展望. 信息与控制, 1999, 28 (4): 241-247.
Deaton R et al. A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Computation. Proceeding of 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, IN, USA, 13-16 April 1997: 267-271.
Manganaro G, Gyvez J.P.D. DNA Computing Based on Chaos, Proceeding of
1997 IEEE International Conference on Evolutionary Computation, Indianapolis, IN, USA, 13-16 April 1997: 255-260.
Russo M F et al. An Improved DNA Encoding Scheme for Neural Network Modeling. World Congress on Neural Networks–San Diego. 1994 International Neural Networks Society Annual Meeting, CA, USA, 5-9 June 1994:354-359.
Yoshikawa T et al. Emergence of Effective Fuzzy Rules for Controlling Mobile Robots Using DNA Coding Method. Proceeding of 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996, 5: 581-586.
Hofmeister T., Sch?ning U., Rainer Schuler und Osamu Watanabe. A probabilistic 3-SAT algorithm further improved, Proc. of the 19. Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2002, 192-202.
Roweis, et al. A Sticker Based Model for DNA Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44, 1-27.
Qi Ouyang, et al. DNA Solution of the Maximal Clique Problem, Science, 1997, 278: 446- 449.
Sakamoto et al. Molecular Computation by Hairpin Formation. Science, 2000, 288: 1223-1226.
Liu Qinghua, et al. DNA Computing on Surfaces. Nature, 2000, 403: 175-179.
Liu Qinghua., 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
Liu Qinghua, Frutos A., Wang L., et al. Progress towards Demonstration of a Surface Based on DNA computation: A One-word Approach to Solve a Model Satisability Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998)
Haoyang Wu. An Improved Surface-Based Method for DNA Computation. Biosystems, 2001, 59: 1-5.
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.
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.
Sakakibara Y. et al. Intelligent DNA Chips: Logical Operation of Gene Expression Profiles on DNA Computers. Geneme Informatics, 2002, 11: 33-42.
Eng. T., B.M. Serridge. A Surface-Based DNA Algorithm for Minimal Set Cover, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
Cukras A., Faulhammer D., Lipton R. et al. Chess Games: A Model for RNA-based Computation. 4th Int. Meeting on DNA-Based Computers, Baltimore, Penns., (June, 1998).
Oliver J.S.. Computation With DNA-Matrix Multiplication. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
Head T., Kaolan P. D., Bladergroen R. R., et al. Computing with DNA by Operating on Plasmids. Biosystems, 2000, 57: 87-93.
高琳, 马润年, 许进. 基于质粒DNA匹配问题的分子算法. 生物化学与生物物理进展, 2002(5): 820-822.
Freund R., P?un G., Rozenberg G., et al.. Watson-Crick Finite Automata, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
Fu B., Beigel R.. Length Bounded Molecular Computing. 4th Int. Meeting on DNA-Based Computing, Balti-more, Penns., (June, 1998).
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.
GuptaV., Parthasarathy S., Zaki M.J.. Arithmetic and Logic Operations with DNA. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
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).
Gibbons A., Amos M., Hodgson D. Models of DNA Computation, Mathematical Foundations of Computer Science. 1996, 1113: 18-36.
Guarnieri F., Fliss M., Bancroft C.. Making DNA Add. Science, 1996, 273: 220-223.
Rozen D. E., McGrew S., Ellington A. D.. Molecular Computing: Does DNA Computer. Current Biology, 1996, 6(3): 254-258.
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.
Boneh D., Dunworth C., Lipton R. J.. Breaking DES Using a Molecular Computer. Princeton CS Tech-Report number CS-TR-489-95 (1995).
Lipton R.. A Memory Based Attack on Cryptosystems with Application to DNA Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
L.Kari, G..P?un, G.Rozenberg, A.Salomaa, S.Yu. DNA Computing, Sticker Systems and Universality. Acta Informatica, 1998, 35, 401-420.
P?un Gh, Rozenberg G. Sticker Systems. Theoretical Computer Science 204 (1998): 183-203.
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.
T.Lai, K.H. Zimmermann. A Software Platform for the Sticker Model. Techn. Report, No. 2001.2, Dept. Computer Engineering, TU Hamburg-Harburg, 2001.
K.H. Zimmermann. DNA Sticker Algorithms for Binary Linear Codes. IEEE Trans. Infor. Theory, to appear.
Y.Sakakibara, S.Kobayashi. Sticker Systems with Complex Structures. Soft Computing 5 (2001): 114-120.
Karl-Heinz Zimmerman. Efficient DNA Sticker Algorithms for NP-Complete Graph Problems. Computer Physics Communications, 2002,144: 297-309.
Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002, 11(2): 280-284.
许进, 董亚非. 粘贴DNA计算和模型; (I) 理论 (II) 应用. 科学通报, 2003, 48: (12).
Xu Jin. A -bits Sticker Based Model for DNA Computation. (submitted to IEEE Trans. On EA)
T. Head. Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors. Bull. Math. Bio., 1987, l49: 737-759.
Kari L. DNA Computing: Arrival of Biological Mathematics. The Mathematical Intelligencer, 1997, 19(2): 9-22.
P?un G., Rozenberg G., Salomaa A.. DNA Computing. Springer, 1998: 10-41.
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 .
E.Csuhaj-Varju, L.Freund, L.Kari, Gh.P?un. DNA Computing Based on Splicing: Universality Results. Proceedings of 1st Annual Pacific Symposium on Biocomputing, Hawaii, Jan. 1996.
Gh.P?un, A.Salomaa. DNA Computing Based on the Splicing Operation. Math. Japonica 1996, 43(3): 607-632.
Gh.P?un, R. Freund, L. Kari. DNA Computing Based on Splicing: The Existence of Universal Computers. Theory of Computing Systems, 032:69–112, 1999.
Sakakibara Y. B., Ferreti C. Splicing on Tree-like Structures. Theoretical Computer Science, 1999, 210(2): 227-243.
Gh.P?un, Mauri G., Kobayashi S., Yokomori T.. On the Universality of Post and Splicing Systems. Theoretical Computer Science, 2000, 231(2): 157-170.
Gh.P?un.. Splicing Systems with Targets are Computationally Universal. Information Processing Letters, 1996, 59(3): 129-133.
Mateesu A., Gh.P?un, Rozenberg G., Salomaa A., Simple Splicing Systems. Discrete Applied Mathematics, 1998, 84(1-3): 145-163.
Head T.. Splicing System and Molecular Processes. ICEC'97 Special Session on DNA Based Computation, Indiana, April, 1997.
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.
Mark Daley, Lila Kari, Greg Gloor, Rani Siromoney. Circular Contextual Insertions-Deletions with Applications to Biomolecular Computation, Manuscript, 1998.
L.Kari, G..Thierrin. Contextual Insertions-Deletions and Computability. Inf. Comput., 1996, 131, 47–61.
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.
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.
A.Takahara. On the Computational Power of Insertion-Deletion Systems. Proc. of 8th International Meeting on DNA Based Computers, June, Sapporo, 139-150, 2002.
Tiina Zingel. Formal Model of DNA Computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 49(2)(2000): 90–99.
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.
E.Csuhaj-Varju, R.Freund, F. Wachtler. Test Tube Distributed Systems based on Splicing. Computer and AI, 15, 2-3 (1996), 211-232.
K.Culik II, T. Harju. Splicing Semigroups of Dominoes and DNA. Discrete Appl. Math., 31(1991), 261-277.
J.Dassow, V.Mitrana. Splicing Grammar Systems. Computer and AI, 15, 2-3 (1996), 109-122.
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.
Gh.P?un, Rozenberg G, Salomaa A. DNA Computing: New Computing Paradigms. Spring-Verlag, Berlin Heidelberg, 1998.
R.Freund, Gh. P?un, G. Rozenberg, A. Salomaa. Bidirectional Sticker Systems. Third Annual Pacific Conf. On Biocomputing, Hawaii, 1998.
Winfree E. Complexity of Restricted and Unrestricted Models of Molecular
Computation. In DNA Based Computer: Proceeding of a DIMACS Worshop, April 4,1995, Princeton Universtiy (Volume 27 in DIMACS). Richard J. Lipton and Eric B.Baum, Editors. American Mathematical Society, 1996, 199-221.
John E. Hopcroft, Rajeev Motwani, Jeffreyd. Ullman. Introduction to Automata Theory, Languages, and Computation. 清华大学出版社, 2002.
J. Dassow, Gh.P?un. Regulated Rewriting in Formal Language Theory. Spring-Verlag, Berlin, 1989.
J. E. Hopcroft, J.D.Ullman. Introduction to Automata Theory, language and Computation. Addison-Wesley, Reading, Mass., 1979.
任立红. 基于人工DNA 计算模型的智能系统及其应用. 东华大学博士学位论文, 上海, 2000.
陆维明. Petri网与DNA计算. 计算机科学, 25(1)(1998) 1-3.
Boneh D., and Lipton R. J.. A Divide and Conquer Approach to DNA Sequencing. Princeton University, 1996.
张连珍, 许进. 基于质粒的DNA计算模型研究. 计算机工程与应用, 2004, 40(1).
Pixton D. Linear and Circular Splicing Systems. Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
Gatterdam R. W.. DNA and Twist Free Splicing Systems, in Words, Languages and Combinatorics. Singapore, World Scienctific Publishers, 1994.
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.
Ma, R. I. Kallenbach N. R., Sheardy R. D., et al. Three-arm Nucleic Acid Junctions are Flexible. Nucleic Acids Res 1996, 14: 9745-9753.
Jonoska N., Karl S. A., Saito M.. Three-dimensional DNA Structures in Computing, Biosystems, 1999, 52(1): 143-153.
Fu T. J., Seeman N.C.. DNA Double Crossover Molecules. Biochemistry, 1993, 32: 3211-3220.
Hussinia S., Kari L., Stavros K. Coding Properties of DNA Languages, Theoretical Computer Science, 2003, 290: 1557-1579.
Gifford D.K.. On the Path to Computation with DNA. Science, 1994, 266: 993-994.
Bach, E., Condon A., Glaser E., et al.. Improved Models and Algorithms for DNA Computation. Proc. 11th Annual IEEE Conference on Computational Complexity, 1996.
Landweber L., Kari L.. The Evolution of Cellular Computing: Nature's solution to a computational Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998). Also, Proceedings of the 3rd Annual Genetic Programming Conference, Morgan Kaufmann Publishers, San Francisco, July 22-25, 1998 : 700-708.
Gloor G., L. Kari, M. Gaasenbeek, S. Yu. Towards a DNA Solution to the Shortest Common Superstring Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
GrayJ. M., Frutos T. G., Berman A.M.. Reducing Errors in DNA Computing by Appropriate Word Design. University of Wisconsin, Department of Chemistry, October 9, 1996.
Zimmermann K. H.. On Applying Molecular Computation to Binary Linear, IEEE, Transactions on information theory, 2002, 48(2): 505-510.
Jonoska N., Karl S. A.. A Molecular Computation of the Road Coloring Problem. 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.
Bach E., Condon A., Glaser E., Tanguay C.. DNA Models and Algorithms for
NP- complete Problems. Journal of Computer and System Sciences, 1998, 57(2): 172-186.
Guarnieri, F., C. Bancroft. Use of a Horizontal Chain Reaction for DNA- Based Addition. Proceedings of the 2nd Annual DIMACS Meeting on DNA Based Computers., June 10-12,1996
Williams R., Wood H.. Extracale Computer Algebra Problems Interconnect with Molecular Reactions and Complexity Theory. In Proceeding Soft the 2nd DIMACS workshop on DNA-based computers, 1996.
Garzon M., Jonoska N.. The Bounded Complexity of DNA Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore,Penns., (June, 1998). To appear in DNA Based Computers, IV, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (ed. H. Rubin), American Mathematical Society, 1999.
Cox J. C.,Cohen D. S. Ellington A. D.. The Complexities of DNA Computation, Trends in Biotechnology, 1999, 17(4): 151-154.
Boneh D., Lipton R.. On The Computational Power of DNA. Discrete Appl. Math., 1996, 71: 79-94.
Tony L. E.. Linear DNA Self-Assembly with Hairpins Linear Context Free Grammars. DIMACS series in discrete in proceedings of the 2nd DIMACS workshop on DNA- based computers, 1996, 7: 122-127.
Amose M.. Theoretical and Experimental DNA Computation. In the Bulletin of EATCS, 1999, 67: 125-138.
陈惟昌, 陈志华, 邱红霞, 王自强. DNA计算机的研究和展望. 生物化学与生物物理进展, 2001, 28(2): 156-159.
李人厚, 余文. 关于DNA计算的基本原理与探讨. 计算机学报, 2001, 9: 972- 978.
James K. D., Boles A. R., Henckel D., et al. The Fidellity of Templated-directed
Oligonucleotide Ligation an its Relevance to DNA Computation. Nucleic Acids Res. 1998, 26:5203-5211.
Hwang K. Advanced Computer Architecture. NewYork, McGrawHill, 1991.
邱道文. 基于完备剩余格值逻辑的自动机理论-拓扑刻画. 中国科学, 33, 2(2003), 137-146.
陈虎, 戴葵, 胡守仁. 环行阵列神经网络计算机系统. 计算机研究与发展, 1999, 36(2):144-149.
郑俊, 蔡绍皙. DNA计算机: 现况与未来. 自然杂志, 1998, 2: 91-92.
尹屹梅, 林祥钦. 分子计算机的研究进展. 化学进展, 2001, 5: 337-342.
Netterer F. The Mathematics of Computerized Tomography. NewYork, Wiley, 1986: 114-126.
高琳, 许进, 张军英. DNA计算的研究进展与展望. 电子学报, 2001, 7: 973-975.
强晓艺. DNA计算的研究与尚待解决的问题. 微电子学与计算机, 2002, 6: 22-26.
强晓艺. DNA计算机与DNA序列及计算. 微电子学与计算机, 2002, 3:70-74.
庄新田, 黄小原. 分子计算及其应用. 科技进步与对策, 2002, 1: 64-67.
邵学广, 姜海燕, 蔡文生. 生物分子计算进展. 化学进展, 2002, 2: 37-40.
莫宏伟, 金鸿章, 王科俊. 基于生物体系的计算智能研究. 信息技术, 2002, 2: 25- 29.
Adleman L. On Constructing a Molecular Computing. Technical Report TR 79-387, Computer science Department, University of Southern California, USA, January 1995.
Li D. F.. Is DNA Computing Viable for 3-SAT Problems? Theoretical Computer Science, 2003, 290: 2095- 2107.
丁永生, 任立红, 邵世煌. DNA计算与软计算. 系统仿真学报, 13(2001),
(supp):198-203.
孟大志, 曹海萍. DNA计算与生物数学. 生物物理学报, 2002, 18(2): 163-166.
庄新田, 黄小原. 分子计算及其应用. 科技进步与对策, 2002, 1: 64-67.
邵学广, 姜海燕, 蔡文生. 生物分子计算进展. 化学进展, 2002, 2: 37-40.
莫宏伟, 金鸿章, 王科俊. 基于生物体系的计算智能研究. 信息技术, 2002, 2: 25- 29.
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): 224-224.
Liu Y C, Pan L.Q., Xu J., et al. DNA Solution of Graph Coloring Problem. Journal of Chemical Information and Computer Sciences, 2002, 42(3): 529-534.
Pan L.Q., Liu Y C, Pan L. Q., Xu J.. A Surface-Based DNA Algorithm for the Maximal Clique Problem. The Chinese Journal of Electronics, 2002, 4: 469.
Liu W. B., Xu J.. A DNA Algorithm for the Graph Coloring Problem. Journal of Chemical Information and Computers, 2002, 42 (5): 1176-1178.
Pan L.Q., Xu J.. A Surface-Based DNA Algorithm for the Minimal Vertex Cover Problem. Progress in Natural Science, 2003, 13 (1): 81-84.
Yin Zhixiang, Zhang Fengyue, Xu Jin. The General Form of 0-1 Programming Problem Based on DNA Computing. Biosystems, 2003, 70(1): 73-79.
Wenbin Liu, Shudong Wang and Jin Xu. DNA Sequence Design Based on Template Strategy. J. Chem. Inf. Comput. Sci. 2003.11.
Wenbin Liu, Shudong Wang, Jin Xu. Solving the 3-SAT Problem Based on DNA Computing. J. Chem. Inf. Comput. Sci. 2003.11.
Wenbin Liu, Jin Xu. The Hamiltonian Cycle Problem Based on DNA Computing. Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution And Learning, 2002, 1: 313-317.
殷志祥, 董亚非, 许进. 组合优化中的DNA计算, 计算机工程与应用 2002, 38(19): 65-67.
殷志祥, 张凤月, 许进. 0-1规划问题的DNA计算. 电子与信息学报, 2003, 25(1): 62-66.
张凤月, 殷志祥, 许进. 基于芯片上的DNA计算. 生物化学与生物物理进展, 2003, 30(3):412-415.
刘文斌, 王淑栋, 许进. 最大匹配问题的DNA表面计算模型. 电子学报, 2003.10.
Winfree.E.. On the Computational Power of DNA Annealing and Ligation. In DNA Based Computers, American Mathematical Society, 1996.
Baum E. B.. DNA Sequences Useful for Computation. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
马立人, 蒋中华. 生物芯片. 化学工业出版社, 1999.
Kari L., Sakakibara.Y.. DNA Computers Journal of the Institute of Electronics, Information and Communication Engineers, 80: 935-939, (in Japanese, 1997).
Kari L., Gloor G., Yu S.. Using DNA to Solve the Bounded Post Correspondence Problem. Theoretical Computer Science, 2000, 231(2): 193-203.
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.
Deninnghoff K. L., Gatterdam R. W.. On the Undecidability of Splicing Systems. Int. J. Computer Math., 1989, 27: 133-145.
Kobyshi S. S., Szkaibara Y. B.. Multiple Splicing Systems and Universal Computability. Theoretical Computer Science, 2001, 264(1): 3-23.
Christos H., Papadimitriou, T.. Combinatorial Optimization: Algorithms and
Complexity. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
Gass, S.L.. Linear Programming Methods and Applications. Fifth Edition, Mc Graw Hill Book Company, 1984.
Garey M., Johnson D. Computers and Intractability. A Guide to the Theory of NP-completeness, USA, New York, 1979: 192-193.
Landweber L. F.. The Evolution of Cellular Computing. Biological Bulletin, 1999, 196(3): 324-325.
Leete T.H., Schwartz M.D., Williams R.M., et al.. Massively Parallel DNA Computation: Expansion of Symbolic Determinants. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
Guo Z., Guilfoyle R. A. Direct Fluorescence Analysis of Genetic Polymorphisms by Hybridization with Oligonecleotide Arrays on Glass Supports. Nucl. Acid. Res., 1994, 22: 5456-5465.
Boneh D., Dunworth C., Lipton R. J., et al.. Making DNA Computers Error Resistant. 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.
Kazic T.. After the Turing Machine: A Metal Model for Molecular Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998)
John E.H., Jeffrey D. U.. Formal Languages and Relation to Automata. Addison-Wesley Publishing Company, 1969.
Doi H., Furusawa M.. Evolution is Promoted by Asymmetrical Mutations in DNA Replication-Genetic Algorithm with Double-Stranded DNA. Fujitsu Scientific and technical Journal, 1996, 32(2): 248-255.
Amenyo, J.T.. Mesoscopic Computer Engineering: Automating DNA-based Molecular Computing via Traditional Practices of Parallel Computer Architecture Design. Proceedings of the 2nd Annual DIMACS Meeting on
DNA Based Computers, June 1996.
Adey R. A., Lahrmann A., LeBmollmann C.. Simulation and Design of Micro- systems and Micro-structures,Computational Mechanics Publication,1995.
Seeman N. C.. Nucleic Acid Junctions and Lattices. J Theor Biol 1982, 99:237-247.
Labean T. H., Yan H., Kopatsch J., et al.. The Construction, Analysis, Ligation and Self-assembly of DNA Triple Crossover Complexes. J. Am. Chem. Soc. 2000, 122: 1848-1860.
Kurtz S., Mahaney S., Royer J., et al.. Active Transport in Biological Computing. In proceeding of the 2nd DIMCS Workshop on DNA-based Computers, 1996.
Freund R.. Test Tube Systems with Controlled Applications of Rules. CEC'97 Special Session on DNA Based Computation, Indiana, April, 1997.
Beigel R., Fu B.. Molecular Approximation Algorithm for NP Optimization Problems. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June,1997).
Smith.w, Schweitzer.A.. DNA Computers in Vivo. DIMACS Workshop on DNA Bead Computing, Princeton April 1995.
Mirzabekov A. D.. DNA Sequencing by Hybridization a Megasequencing Method and Adiagnostic Tool. Tibtech., 1994, 12: 27-32.
Baum E. B.. DNA Sequences Useful for Computation. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
Sambrook J., Fritsch E. F., Maniatis T.. Molecular Cloning: A Laboratory Manual. Cold Spring Harbor Laboratory Press, 1989.
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).
殷志祥, 张家秀, 许进. 案例分析中的DNA计算. 系统仿真学报, 2003, 15(10) .
殷志祥, 董亚非, 许进. DNA计算在组合优化中的应用及其复杂性. 系统工程与电子技术, 2003, 25(4): 427-431.
Fengyue Zhang, Bo Liu, Zhixiang Yin, Jin Xu. A DNA Computing Model Based on Acrydite TM Gel Technology to Solve the Timetabling Problem. Journal of Chemical Information and Computer Science (Submitted).
殷志祥, 许进. DNA计算在图论中的应用. 自然科学进展, 2003, 13(5): 462-465.
Landweber L.F., Gilbert W.. RNA Editing as a Source of Genetic Variation, Nature, 1993, 363: 179-182.
Landweber L.F., Gilbert W.. Phylogenetic Analysis of RNA Editing: A Primitive Genetic Phenomenon. Proc. Natl. Acad. Sci., 1994, 91: 918-921.
Smith L.M.. Automated Synthesis and Sequence Analysis of Biological Macromolecules. Anal. Chem., 1988, 60: 381A-390A.
Takashi Yokomori. YAC: Yet Another Computation Model of Self-Assembly. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
W. Smith, A. Schweitzer. DNA Computer in Vitro and Vivo. Technical Report, NEC, 1995.
D. Roos, K. Wagner. On the Power of DNA Computing. Information and Computation, 1996, 131: 95-109.
Bondy J.A. and Murty U.S.R. Graph Theory with Application. The Macmillan Press LTD, 1976.
Yin Zhixiang, Zhang Fengyue, Xu Jin. A Surface Based DNA Computing for the Simple 0-1 Programming Problem. Bulletin of Mathematical Biology (Accepted).
Yin Zhixiang, Tang Shuangqing, Dong Yafei, Zhang Yumin. Working Operation
Problem Based on DNA Computing. Proc. SPIE, 5253: 870-873, Fifth International Symposium on Instrumentation and Control Technology, Oct. 2003, Beijing (ISICT, 2003).
Dong Yafei, Yin Zhixiang, Wang Shudong. DNA Solution of the Minimal Covering Problem. Advances in Systems Science and Applications, 2003, 3(2): 152-156.
Fengyue Zhang, Zhixiang Yin, Bo Liu, Jin Xu. DNA Computing Model to Solve 0-1 Program Problem. Biosystems (Submitted).
Rudolf Freund. Splicing Systems on Graphs. Manuscript, 1995.
Rose J.A., Deaton R.J., Hagiya M., Suyama A. Equilibrium Analysis of an Autonomous Molecular Computer, Physical Review, 2002 (65): 1-13.
刘文斌, 王淑栋, 许进. 可满足性(SAT)问题的几种DNA 计算模型. 小型微型计算机系统, 2004.
Morimoto N., Arita M. and Suyama A.. Solid-Phase DNA Solution to the Hamiltonian Path Problem. DIMACS, Series in Discrete Mathematics and Theoretical Computer Science, 1999, 48,193-206.
Rose. J. A, Hagiya. M, Deaton. R. J and Suyama. A. A DNA-based in vitro Genetic Program. Journal of Biological Physics, 2002, 28: 493–498.
Ogihara M., and Ray A.. Simulating Boolean circuits on a DNA computer. Technical Report 631, University of Rochester, August 1996.
Duffin. R.J.Topology of Series-Parallel Networks. J.Math Analy. App.10: 303–318 (1965).
Jian Liang Wu. The Linear Arboricity of Series-Parallel. Graphs and Combinatorics, 16(2000): 367–371.
Behzad.M. Graph and their Chromatic Number. Doctorial Thesis (Michigan State University), 1965.
Vijayditya.N. On Total Chromatic Number of a Graph. J. London. Math. Soc.
1971, 3(2): 405–408.
Bollobas.B and Harris A.J. List Coloring of Graphs. Graphs and Combinatorics, 1985(1): 115–127.
Zhang Zhongfu, Zhang Jianxun and Wang Jianfang. The Total Chromatic Number of Some Graphs. Scienta Sinica, Series A, 1988, 1434–1443.
Dong-Ling Chen and Jian-Liang Wu. The Total Chromatic Number of Descartes Product Graphs. Journal of TaiYuan Mechanism Institute, 1994 Vol.15 Supp.
H.P.Yap. Some Topics in Graph Theory. London: Combridge, 1986. Chinese Version: Press of University of Science and Technology of China, 1992.
Z.F.Zhang and J.F.Wang. The Progress of Total Coloring Graphs. Advances in Math, 21(1992): 390–397.
D.L.Chen and J.L.Wu. The Total Coloring of Some Graphs, Combinatorics, Graph Theory Algorithms and Applications (Beijing, 1993). World Sci. Publishing, River Edge, N.J, 1994, supp.17–20.
H.P.Yap. The Total Coloring of Graphs. Lecture Notes in Mathematics 1623, Springer 1996, Printed in Germany.
Jurgen Eckhoff. the Maximum Number of Triangles in a -free Graph, Discrete Mathematics 194: 95–106.
G.A.Dirac. A Property of -Chromatic Graphs and some Results on Critical Graphs. J.London Math. Soc. 27(1952): 85–92.
P.D.Seymour. Coloring the Series-Parallel Graphs. Combinatorica, 10(4)(1990): 379–392.
李承祖. 量子通信和量子计算机. 国防科技大学出版社, 2000.
许进. DNA计算与运筹学发展的新机遇. 《中国运筹学会第六届学术交流会论文集》(上卷)(主编: 章祥荪, 王建方, 刘宝碇, 刘德刚), Global-Link Publishing Company 香港, 2000: 43-54(注:特邀大会主题报告) .
Gao F., Niu H., Zhao H. A Study on Numerical Simulation of Imager Construction in Optical Computer Tomography. Bioimaging, 1997, 5(2): 51-57.
邱道文. 量子计算机的刻画. 软件学报, 14,1(2003), 9-15.
Vlatko V., Martin B. Basic of Quantum Computation. Progress in Quantum Electronics, 1998, 22: 1-39.
邱道文. 基于量子逻辑的自动机和文法理论. 软件学报, 14,1(2003), 23-27.
Kari L.. DNA Computers: Tomorrow's Reality. Tutorial in the Bulletin of EATCS, 1996, 59: 256-266.
许进等. DNA 计算机原理、进展及难点(Ⅰ): 生物计算系统及其在图论中的应用. 计算机学报, 2003, 26(1):1-11.
Adleman L. Molecular Computation of Solution to Combinatorial problems. Science. 1994, 66 (11): 1021-1024.
Lipton R. J. DNA Solution of Hard Computation Problems. Science, 1995, 268 (4): 542-545.
任立红等. DNA计算研究的现状与展望. 信息与控制, 1999, 28 (4): 241-247.
Deaton R et al. A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Computation. Proceeding of 1997 IEEE International Conference on Evolutionary Computation, Indianapolis, IN, USA, 13-16 April 1997: 267-271.
Manganaro G, Gyvez J.P.D. DNA Computing Based on Chaos, Proceeding of
1997 IEEE International Conference on Evolutionary Computation, Indianapolis, IN, USA, 13-16 April 1997: 255-260.
Russo M F et al. An Improved DNA Encoding Scheme for Neural Network Modeling. World Congress on Neural Networks–San Diego. 1994 International Neural Networks Society Annual Meeting, CA, USA, 5-9 June 1994:354-359.
Yoshikawa T et al. Emergence of Effective Fuzzy Rules for Controlling Mobile Robots Using DNA Coding Method. Proceeding of 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996, 5: 581-586.
Hofmeister T., Sch?ning U., Rainer Schuler und Osamu Watanabe. A probabilistic 3-SAT algorithm further improved, Proc. of the 19. Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2002, 192-202.
Roweis, et al. A Sticker Based Model for DNA Computation. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 44, 1-27.
Qi Ouyang, et al. DNA Solution of the Maximal Clique Problem, Science, 1997, 278: 446- 449.
Sakamoto et al. Molecular Computation by Hairpin Formation. Science, 2000, 288: 1223-1226.
Liu Qinghua, et al. DNA Computing on Surfaces. Nature, 2000, 403: 175-179.
Liu Qinghua., 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
Liu Qinghua, Frutos A., Wang L., et al. Progress towards Demonstration of a Surface Based on DNA computation: A One-word Approach to Solve a Model Satisability Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998)
Haoyang Wu. An Improved Surface-Based Method for DNA Computation. Biosystems, 2001, 59: 1-5.
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.
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.
Sakakibara Y. et al. Intelligent DNA Chips: Logical Operation of Gene Expression Profiles on DNA Computers. Geneme Informatics, 2002, 11: 33-42.
Eng. T., B.M. Serridge. A Surface-Based DNA Algorithm for Minimal Set Cover, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
Cukras A., Faulhammer D., Lipton R. et al. Chess Games: A Model for RNA-based Computation. 4th Int. Meeting on DNA-Based Computers, Baltimore, Penns., (June, 1998).
Oliver J.S.. Computation With DNA-Matrix Multiplication. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
Head T., Kaolan P. D., Bladergroen R. R., et al. Computing with DNA by Operating on Plasmids. Biosystems, 2000, 57: 87-93.
高琳, 马润年, 许进. 基于质粒DNA匹配问题的分子算法. 生物化学与生物物理进展, 2002(5): 820-822.
Freund R., P?un G., Rozenberg G., et al.. Watson-Crick Finite Automata, 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
Fu B., Beigel R.. Length Bounded Molecular Computing. 4th Int. Meeting on DNA-Based Computing, Balti-more, Penns., (June, 1998).
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.
GuptaV., Parthasarathy S., Zaki M.J.. Arithmetic and Logic Operations with DNA. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June, 1997).
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).
Gibbons A., Amos M., Hodgson D. Models of DNA Computation, Mathematical Foundations of Computer Science. 1996, 1113: 18-36.
Guarnieri F., Fliss M., Bancroft C.. Making DNA Add. Science, 1996, 273: 220-223.
Rozen D. E., McGrew S., Ellington A. D.. Molecular Computing: Does DNA Computer. Current Biology, 1996, 6(3): 254-258.
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.
Boneh D., Dunworth C., Lipton R. J.. Breaking DES Using a Molecular Computer. Princeton CS Tech-Report number CS-TR-489-95 (1995).
Lipton R.. A Memory Based Attack on Cryptosystems with Application to DNA Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
L.Kari, G..P?un, G.Rozenberg, A.Salomaa, S.Yu. DNA Computing, Sticker Systems and Universality. Acta Informatica, 1998, 35, 401-420.
P?un Gh, Rozenberg G. Sticker Systems. Theoretical Computer Science 204 (1998): 183-203.
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.
T.Lai, K.H. Zimmermann. A Software Platform for the Sticker Model. Techn. Report, No. 2001.2, Dept. Computer Engineering, TU Hamburg-Harburg, 2001.
K.H. Zimmermann. DNA Sticker Algorithms for Binary Linear Codes. IEEE Trans. Infor. Theory, to appear.
Y.Sakakibara, S.Kobayashi. Sticker Systems with Complex Structures. Soft Computing 5 (2001): 114-120.
Karl-Heinz Zimmerman. Efficient DNA Sticker Algorithms for NP-Complete Graph Problems. Computer Physics Communications, 2002,144: 297-309.
Gao Lin, Xu Jin. DNA Solution of Vertex Cover Problem Based on Sticker Model. Chinese Journal of Electronics, 2002, 11(2): 280-284.
许进, 董亚非. 粘贴DNA计算和模型; (I) 理论 (II) 应用. 科学通报, 2003, 48: (12).
Xu Jin. A -bits Sticker Based Model for DNA Computation. (submitted to IEEE Trans. On EA)
T. Head. Formal Language Theory and DNA: an Analysis of the Generative Capacity of Specific Recombinant Behaviors. Bull. Math. Bio., 1987, l49: 737-759.
Kari L. DNA Computing: Arrival of Biological Mathematics. The Mathematical Intelligencer, 1997, 19(2): 9-22.
P?un G., Rozenberg G., Salomaa A.. DNA Computing. Springer, 1998: 10-41.
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 .
E.Csuhaj-Varju, L.Freund, L.Kari, Gh.P?un. DNA Computing Based on Splicing: Universality Results. Proceedings of 1st Annual Pacific Symposium on Biocomputing, Hawaii, Jan. 1996.
Gh.P?un, A.Salomaa. DNA Computing Based on the Splicing Operation. Math. Japonica 1996, 43(3): 607-632.
Gh.P?un, R. Freund, L. Kari. DNA Computing Based on Splicing: The Existence of Universal Computers. Theory of Computing Systems, 032:69–112, 1999.
Sakakibara Y. B., Ferreti C. Splicing on Tree-like Structures. Theoretical Computer Science, 1999, 210(2): 227-243.
Gh.P?un, Mauri G., Kobayashi S., Yokomori T.. On the Universality of Post and Splicing Systems. Theoretical Computer Science, 2000, 231(2): 157-170.
Gh.P?un.. Splicing Systems with Targets are Computationally Universal. Information Processing Letters, 1996, 59(3): 129-133.
Mateesu A., Gh.P?un, Rozenberg G., Salomaa A., Simple Splicing Systems. Discrete Applied Mathematics, 1998, 84(1-3): 145-163.
Head T.. Splicing System and Molecular Processes. ICEC'97 Special Session on DNA Based Computation, Indiana, April, 1997.
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.
Mark Daley, Lila Kari, Greg Gloor, Rani Siromoney. Circular Contextual Insertions-Deletions with Applications to Biomolecular Computation, Manuscript, 1998.
L.Kari, G..Thierrin. Contextual Insertions-Deletions and Computability. Inf. Comput., 1996, 131, 47–61.
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.
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.
A.Takahara. On the Computational Power of Insertion-Deletion Systems. Proc. of 8th International Meeting on DNA Based Computers, June, Sapporo, 139-150, 2002.
Tiina Zingel. Formal Model of DNA Computing: A Survey. Proc. Estonian Acad. Sci. Phys. Math., 49(2)(2000): 90–99.
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.
E.Csuhaj-Varju, R.Freund, F. Wachtler. Test Tube Distributed Systems based on Splicing. Computer and AI, 15, 2-3 (1996), 211-232.
K.Culik II, T. Harju. Splicing Semigroups of Dominoes and DNA. Discrete Appl. Math., 31(1991), 261-277.
J.Dassow, V.Mitrana. Splicing Grammar Systems. Computer and AI, 15, 2-3 (1996), 109-122.
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.
Gh.P?un, Rozenberg G, Salomaa A. DNA Computing: New Computing Paradigms. Spring-Verlag, Berlin Heidelberg, 1998.
R.Freund, Gh. P?un, G. Rozenberg, A. Salomaa. Bidirectional Sticker Systems. Third Annual Pacific Conf. On Biocomputing, Hawaii, 1998.
Winfree E. Complexity of Restricted and Unrestricted Models of Molecular
Computation. In DNA Based Computer: Proceeding of a DIMACS Worshop, April 4,1995, Princeton Universtiy (Volume 27 in DIMACS). Richard J. Lipton and Eric B.Baum, Editors. American Mathematical Society, 1996, 199-221.
John E. Hopcroft, Rajeev Motwani, Jeffreyd. Ullman. Introduction to Automata Theory, Languages, and Computation. 清华大学出版社, 2002.
J. Dassow, Gh.P?un. Regulated Rewriting in Formal Language Theory. Spring-Verlag, Berlin, 1989.
J. E. Hopcroft, J.D.Ullman. Introduction to Automata Theory, language and Computation. Addison-Wesley, Reading, Mass., 1979.
任立红. 基于人工DNA 计算模型的智能系统及其应用. 东华大学博士学位论文, 上海, 2000.
陆维明. Petri网与DNA计算. 计算机科学, 25(1)(1998) 1-3.
Boneh D., and Lipton R. J.. A Divide and Conquer Approach to DNA Sequencing. Princeton University, 1996.
张连珍, 许进. 基于质粒的DNA计算模型研究. 计算机工程与应用, 2004, 40(1).
Pixton D. Linear and Circular Splicing Systems. Proc. 1st Intn. Symp. on Intelligence in Neural and Biological Systems, IEEE Press, 1995:181-188.
Gatterdam R. W.. DNA and Twist Free Splicing Systems, in Words, Languages and Combinatorics. Singapore, World Scienctific Publishers, 1994.
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.
Ma, R. I. Kallenbach N. R., Sheardy R. D., et al. Three-arm Nucleic Acid Junctions are Flexible. Nucleic Acids Res 1996, 14: 9745-9753.
Jonoska N., Karl S. A., Saito M.. Three-dimensional DNA Structures in Computing, Biosystems, 1999, 52(1): 143-153.
Fu T. J., Seeman N.C.. DNA Double Crossover Molecules. Biochemistry, 1993, 32: 3211-3220.
Hussinia S., Kari L., Stavros K. Coding Properties of DNA Languages, Theoretical Computer Science, 2003, 290: 1557-1579.
Gifford D.K.. On the Path to Computation with DNA. Science, 1994, 266: 993-994.
Bach, E., Condon A., Glaser E., et al.. Improved Models and Algorithms for DNA Computation. Proc. 11th Annual IEEE Conference on Computational Complexity, 1996.
Landweber L., Kari L.. The Evolution of Cellular Computing: Nature's solution to a computational Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998). Also, Proceedings of the 3rd Annual Genetic Programming Conference, Morgan Kaufmann Publishers, San Francisco, July 22-25, 1998 : 700-708.
Gloor G., L. Kari, M. Gaasenbeek, S. Yu. Towards a DNA Solution to the Shortest Common Superstring Problem. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June, 1998).
GrayJ. M., Frutos T. G., Berman A.M.. Reducing Errors in DNA Computing by Appropriate Word Design. University of Wisconsin, Department of Chemistry, October 9, 1996.
Zimmermann K. H.. On Applying Molecular Computation to Binary Linear, IEEE, Transactions on information theory, 2002, 48(2): 505-510.
Jonoska N., Karl S. A.. A Molecular Computation of the Road Coloring Problem. 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.
Bach E., Condon A., Glaser E., Tanguay C.. DNA Models and Algorithms for
NP- complete Problems. Journal of Computer and System Sciences, 1998, 57(2): 172-186.
Guarnieri, F., C. Bancroft. Use of a Horizontal Chain Reaction for DNA- Based Addition. Proceedings of the 2nd Annual DIMACS Meeting on DNA Based Computers., June 10-12,1996
Williams R., Wood H.. Extracale Computer Algebra Problems Interconnect with Molecular Reactions and Complexity Theory. In Proceeding Soft the 2nd DIMACS workshop on DNA-based computers, 1996.
Garzon M., Jonoska N.. The Bounded Complexity of DNA Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore,Penns., (June, 1998). To appear in DNA Based Computers, IV, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (ed. H. Rubin), American Mathematical Society, 1999.
Cox J. C.,Cohen D. S. Ellington A. D.. The Complexities of DNA Computation, Trends in Biotechnology, 1999, 17(4): 151-154.
Boneh D., Lipton R.. On The Computational Power of DNA. Discrete Appl. Math., 1996, 71: 79-94.
Tony L. E.. Linear DNA Self-Assembly with Hairpins Linear Context Free Grammars. DIMACS series in discrete in proceedings of the 2nd DIMACS workshop on DNA- based computers, 1996, 7: 122-127.
Amose M.. Theoretical and Experimental DNA Computation. In the Bulletin of EATCS, 1999, 67: 125-138.
陈惟昌, 陈志华, 邱红霞, 王自强. DNA计算机的研究和展望. 生物化学与生物物理进展, 2001, 28(2): 156-159.
李人厚, 余文. 关于DNA计算的基本原理与探讨. 计算机学报, 2001, 9: 972- 978.
James K. D., Boles A. R., Henckel D., et al. The Fidellity of Templated-directed
Oligonucleotide Ligation an its Relevance to DNA Computation. Nucleic Acids Res. 1998, 26:5203-5211.
Hwang K. Advanced Computer Architecture. NewYork, McGrawHill, 1991.
邱道文. 基于完备剩余格值逻辑的自动机理论-拓扑刻画. 中国科学, 33, 2(2003), 137-146.
陈虎, 戴葵, 胡守仁. 环行阵列神经网络计算机系统. 计算机研究与发展, 1999, 36(2):144-149.
郑俊, 蔡绍皙. DNA计算机: 现况与未来. 自然杂志, 1998, 2: 91-92.
尹屹梅, 林祥钦. 分子计算机的研究进展. 化学进展, 2001, 5: 337-342.
Netterer F. The Mathematics of Computerized Tomography. NewYork, Wiley, 1986: 114-126.
高琳, 许进, 张军英. DNA计算的研究进展与展望. 电子学报, 2001, 7: 973-975.
强晓艺. DNA计算的研究与尚待解决的问题. 微电子学与计算机, 2002, 6: 22-26.
强晓艺. DNA计算机与DNA序列及计算. 微电子学与计算机, 2002, 3:70-74.
庄新田, 黄小原. 分子计算及其应用. 科技进步与对策, 2002, 1: 64-67.
邵学广, 姜海燕, 蔡文生. 生物分子计算进展. 化学进展, 2002, 2: 37-40.
莫宏伟, 金鸿章, 王科俊. 基于生物体系的计算智能研究. 信息技术, 2002, 2: 25- 29.
Adleman L. On Constructing a Molecular Computing. Technical Report TR 79-387, Computer science Department, University of Southern California, USA, January 1995.
Li D. F.. Is DNA Computing Viable for 3-SAT Problems? Theoretical Computer Science, 2003, 290: 2095- 2107.
丁永生, 任立红, 邵世煌. DNA计算与软计算. 系统仿真学报, 13(2001),
(supp):198-203.
孟大志, 曹海萍. DNA计算与生物数学. 生物物理学报, 2002, 18(2): 163-166.
庄新田, 黄小原. 分子计算及其应用. 科技进步与对策, 2002, 1: 64-67.
邵学广, 姜海燕, 蔡文生. 生物分子计算进展. 化学进展, 2002, 2: 37-40.
莫宏伟, 金鸿章, 王科俊. 基于生物体系的计算智能研究. 信息技术, 2002, 2: 25- 29.
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): 224-224.
Liu Y C, Pan L.Q., Xu J., et al. DNA Solution of Graph Coloring Problem. Journal of Chemical Information and Computer Sciences, 2002, 42(3): 529-534.
Pan L.Q., Liu Y C, Pan L. Q., Xu J.. A Surface-Based DNA Algorithm for the Maximal Clique Problem. The Chinese Journal of Electronics, 2002, 4: 469.
Liu W. B., Xu J.. A DNA Algorithm for the Graph Coloring Problem. Journal of Chemical Information and Computers, 2002, 42 (5): 1176-1178.
Pan L.Q., Xu J.. A Surface-Based DNA Algorithm for the Minimal Vertex Cover Problem. Progress in Natural Science, 2003, 13 (1): 81-84.
Yin Zhixiang, Zhang Fengyue, Xu Jin. The General Form of 0-1 Programming Problem Based on DNA Computing. Biosystems, 2003, 70(1): 73-79.
Wenbin Liu, Shudong Wang and Jin Xu. DNA Sequence Design Based on Template Strategy. J. Chem. Inf. Comput. Sci. 2003.11.
Wenbin Liu, Shudong Wang, Jin Xu. Solving the 3-SAT Problem Based on DNA Computing. J. Chem. Inf. Comput. Sci. 2003.11.
Wenbin Liu, Jin Xu. The Hamiltonian Cycle Problem Based on DNA Computing. Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution And Learning, 2002, 1: 313-317.
殷志祥, 董亚非, 许进. 组合优化中的DNA计算, 计算机工程与应用 2002, 38(19): 65-67.
殷志祥, 张凤月, 许进. 0-1规划问题的DNA计算. 电子与信息学报, 2003, 25(1): 62-66.
张凤月, 殷志祥, 许进. 基于芯片上的DNA计算. 生物化学与生物物理进展, 2003, 30(3):412-415.
刘文斌, 王淑栋, 许进. 最大匹配问题的DNA表面计算模型. 电子学报, 2003.10.
Winfree.E.. On the Computational Power of DNA Annealing and Ligation. In DNA Based Computers, American Mathematical Society, 1996.
Baum E. B.. DNA Sequences Useful for Computation. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
马立人, 蒋中华. 生物芯片. 化学工业出版社, 1999.
Kari L., Sakakibara.Y.. DNA Computers Journal of the Institute of Electronics, Information and Communication Engineers, 80: 935-939, (in Japanese, 1997).
Kari L., Gloor G., Yu S.. Using DNA to Solve the Bounded Post Correspondence Problem. Theoretical Computer Science, 2000, 231(2): 193-203.
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.
Deninnghoff K. L., Gatterdam R. W.. On the Undecidability of Splicing Systems. Int. J. Computer Math., 1989, 27: 133-145.
Kobyshi S. S., Szkaibara Y. B.. Multiple Splicing Systems and Universal Computability. Theoretical Computer Science, 2001, 264(1): 3-23.
Christos H., Papadimitriou, T.. Combinatorial Optimization: Algorithms and
Complexity. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982.
Gass, S.L.. Linear Programming Methods and Applications. Fifth Edition, Mc Graw Hill Book Company, 1984.
Garey M., Johnson D. Computers and Intractability. A Guide to the Theory of NP-completeness, USA, New York, 1979: 192-193.
Landweber L. F.. The Evolution of Cellular Computing. Biological Bulletin, 1999, 196(3): 324-325.
Leete T.H., Schwartz M.D., Williams R.M., et al.. Massively Parallel DNA Computation: Expansion of Symbolic Determinants. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton, June, 1996.
Guo Z., Guilfoyle R. A. Direct Fluorescence Analysis of Genetic Polymorphisms by Hybridization with Oligonecleotide Arrays on Glass Supports. Nucl. Acid. Res., 1994, 22: 5456-5465.
Boneh D., Dunworth C., Lipton R. J., et al.. Making DNA Computers Error Resistant. 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.
Kazic T.. After the Turing Machine: A Metal Model for Molecular Computing. 4th Int. Meeting on DNA-Based Computing, Baltimore, Penns., (June,1998)
John E.H., Jeffrey D. U.. Formal Languages and Relation to Automata. Addison-Wesley Publishing Company, 1969.
Doi H., Furusawa M.. Evolution is Promoted by Asymmetrical Mutations in DNA Replication-Genetic Algorithm with Double-Stranded DNA. Fujitsu Scientific and technical Journal, 1996, 32(2): 248-255.
Amenyo, J.T.. Mesoscopic Computer Engineering: Automating DNA-based Molecular Computing via Traditional Practices of Parallel Computer Architecture Design. Proceedings of the 2nd Annual DIMACS Meeting on
DNA Based Computers, June 1996.
Adey R. A., Lahrmann A., LeBmollmann C.. Simulation and Design of Micro- systems and Micro-structures,Computational Mechanics Publication,1995.
Seeman N. C.. Nucleic Acid Junctions and Lattices. J Theor Biol 1982, 99:237-247.
Labean T. H., Yan H., Kopatsch J., et al.. The Construction, Analysis, Ligation and Self-assembly of DNA Triple Crossover Complexes. J. Am. Chem. Soc. 2000, 122: 1848-1860.
Kurtz S., Mahaney S., Royer J., et al.. Active Transport in Biological Computing. In proceeding of the 2nd DIMCS Workshop on DNA-based Computers, 1996.
Freund R.. Test Tube Systems with Controlled Applications of Rules. CEC'97 Special Session on DNA Based Computation, Indiana, April, 1997.
Beigel R., Fu B.. Molecular Approximation Algorithm for NP Optimization Problems. 3rd DIMACS Meeting on DNA Based Computers, Univ. of Penns., (June,1997).
Smith.w, Schweitzer.A.. DNA Computers in Vivo. DIMACS Workshop on DNA Bead Computing, Princeton April 1995.
Mirzabekov A. D.. DNA Sequencing by Hybridization a Megasequencing Method and Adiagnostic Tool. Tibtech., 1994, 12: 27-32.
Baum E. B.. DNA Sequences Useful for Computation. 2nd Annual DIMACS Meeting on DNA Based Computers, Princeton University, June 1996.
Sambrook J., Fritsch E. F., Maniatis T.. Molecular Cloning: A Laboratory Manual. Cold Spring Harbor Laboratory Press, 1989.
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).
殷志祥, 张家秀, 许进. 案例分析中的DNA计算. 系统仿真学报, 2003, 15(10) .
殷志祥, 董亚非, 许进. DNA计算在组合优化中的应用及其复杂性. 系统工程与电子技术, 2003, 25(4): 427-431.
Fengyue Zhang, Bo Liu, Zhixiang Yin, Jin Xu. A DNA Computing Model Based on Acrydite TM Gel Technology to Solve the Timetabling Problem. Journal of Chemical Information and Computer Science (Submitted).
殷志祥, 许进. DNA计算在图论中的应用. 自然科学进展, 2003, 13(5): 462-465.
Landweber L.F., Gilbert W.. RNA Editing as a Source of Genetic Variation, Nature, 1993, 363: 179-182.
Landweber L.F., Gilbert W.. Phylogenetic Analysis of RNA Editing: A Primitive Genetic Phenomenon. Proc. Natl. Acad. Sci., 1994, 91: 918-921.
Smith L.M.. Automated Synthesis and Sequence Analysis of Biological Macromolecules. Anal. Chem., 1988, 60: 381A-390A.
Takashi Yokomori. YAC: Yet Another Computation Model of Self-Assembly. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
W. Smith, A. Schweitzer. DNA Computer in Vitro and Vivo. Technical Report, NEC, 1995.
D. Roos, K. Wagner. On the Power of DNA Computing. Information and Computation, 1996, 131: 95-109.
Bondy J.A. and Murty U.S.R. Graph Theory with Application. The Macmillan Press LTD, 1976.
Yin Zhixiang, Zhang Fengyue, Xu Jin. A Surface Based DNA Computing for the Simple 0-1 Programming Problem. Bulletin of Mathematical Biology (Accepted).
Yin Zhixiang, Tang Shuangqing, Dong Yafei, Zhang Yumin. Working Operation
Problem Based on DNA Computing. Proc. SPIE, 5253: 870-873, Fifth International Symposium on Instrumentation and Control Technology, Oct. 2003, Beijing (ISICT, 2003).
Dong Yafei, Yin Zhixiang, Wang Shudong. DNA Solution of the Minimal Covering Problem. Advances in Systems Science and Applications, 2003, 3(2): 152-156.
Fengyue Zhang, Zhixiang Yin, Bo Liu, Jin Xu. DNA Computing Model to Solve 0-1 Program Problem. Biosystems (Submitted).
Rudolf Freund. Splicing Systems on Graphs. Manuscript, 1995.
Rose J.A., Deaton R.J., Hagiya M., Suyama A. Equilibrium Analysis of an Autonomous Molecular Computer, Physical Review, 2002 (65): 1-13.
刘文斌, 王淑栋, 许进. 可满足性(SAT)问题的几种DNA 计算模型. 小型微型计算机系统, 2004.
Morimoto N., Arita M. and Suyama A.. Solid-Phase DNA Solution to the Hamiltonian Path Problem. DIMACS, Series in Discrete Mathematics and Theoretical Computer Science, 1999, 48,193-206.
Rose. J. A, Hagiya. M, Deaton. R. J and Suyama. A. A DNA-based in vitro Genetic Program. Journal of Biological Physics, 2002, 28: 493–498.
Ogihara M., and Ray A.. Simulating Boolean circuits on a DNA computer. Technical Report 631, University of Rochester, August 1996.
Duffin. R.J.Topology of Series-Parallel Networks. J.Math Analy. App.10: 303–318 (1965).
Jian Liang Wu. The Linear Arboricity of Series-Parallel. Graphs and Combinatorics, 16(2000): 367–371.
Behzad.M. Graph and their Chromatic Number. Doctorial Thesis (Michigan State University), 1965.
Vijayditya.N. On Total Chromatic Number of a Graph. J. London. Math. Soc.
1971, 3(2): 405–408.
Bollobas.B and Harris A.J. List Coloring of Graphs. Graphs and Combinatorics, 1985(1): 115–127.
Zhang Zhongfu, Zhang Jianxun and Wang Jianfang. The Total Chromatic Number of Some Graphs. Scienta Sinica, Series A, 1988, 1434–1443.
Dong-Ling Chen and Jian-Liang Wu. The Total Chromatic Number of Descartes Product Graphs. Journal of TaiYuan Mechanism Institute, 1994 Vol.15 Supp.
H.P.Yap. Some Topics in Graph Theory. London: Combridge, 1986. Chinese Version: Press of University of Science and Technology of China, 1992.
Z.F.Zhang and J.F.Wang. The Progress of Total Coloring Graphs. Advances in Math, 21(1992): 390–397.
D.L.Chen and J.L.Wu. The Total Coloring of Some Graphs, Combinatorics, Graph Theory Algorithms and Applications (Beijing, 1993). World Sci. Publishing, River Edge, N.J, 1994, supp.17–20.
H.P.Yap. The Total Coloring of Graphs. Lecture Notes in Mathematics 1623, Springer 1996, Printed in Germany.
Jurgen Eckhoff. the Maximum Number of Triangles in a -free Graph, Discrete Mathematics 194: 95–106.
G.A.Dirac. A Property of -Chromatic Graphs and some Results on Critical Graphs. J.London Math. Soc. 27(1952): 85–92.
P.D.Seymour. Coloring the Series-Parallel Graphs. Combinatorica, 10(4)(1990): 379–392.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |