DNA计算中若干问题的研究
|
摘要
DNA计算是以生物分子作为计算介质,生物化学反应作为计算工具的一种新型计算方法。一般认为,电子计算机执行串行任务的能力是不容置疑的。而DNA计算在求解NP困难问题上,具有电子计算机所无法比拟的天然优势。本文对DNA计算中若干问题进行了研究和探讨,主要工作如下:
最短有向路问题是指在一个有向网络中的两个指定项点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算中两种抽象模型。本文利用粘贴与删除系统的巨大并行性给出了求解最短有向路问题的DNA计算模型及其实现算法,并通过实例分析说明了粘贴与删除系统求解最短有向路问题的整个过程。
DNA编码问题是DNA计算中初始数据库的设计问题,DNA编码优劣直接影响DNA计算的成功与否。本文将DNA编码看成是文法产生的语言,证明了DNA编码文法的存在性;通过简化文法的字母表,将DNA编码文法的设计问题转化为二进制文法的设计问题,得到了DNA编码文法的两个性质。
DNA computing is a new computing paradigm which uses biological molecules as calculation medium and biochemical reaction as calculation tool. Generally considering, although the ability of the classical electronic computer is un-assailable when it executes serial tasks. DNA computing shows natural advantages compared with the classical electronic computer in solving NP hard problems. In this thesis, some problems in DNA computing are discussed and studied. The main results are as follows:
The shortest directed path problem is to find a directed path with minimum weight in two pointed vertices of a directed network. It has extensive applications in engineering practice. Sticker system and delete system are two abstract models in DNA computing. In this thesis, we propose DNA computing model and realization algorithm of the shortest directed path problem using the high parallelism of sticker system and delete system and give an example to show the whole process.
DNA encoding problem is to design the initial solutions of DNA computing, and the quality of DNA codes could determine whether the DNA computing is successful or not. In this thesis, we view DNA code as a language generated by some grammar and prove the existence of the DNA encoding grammar. Then, by simplifying the alphabet of the grammar, we transform the grammar design of DNA code to that of the binary, and obtain two properties of the DNA encoding grammar.
最短有向路问题是指在一个有向网络中的两个指定项点之间找出一条具有最小权的有向路,它在工程实践中具有广泛的应用。粘贴系统与删除系统是DNA计算中两种抽象模型。本文利用粘贴与删除系统的巨大并行性给出了求解最短有向路问题的DNA计算模型及其实现算法,并通过实例分析说明了粘贴与删除系统求解最短有向路问题的整个过程。
DNA编码问题是DNA计算中初始数据库的设计问题,DNA编码优劣直接影响DNA计算的成功与否。本文将DNA编码看成是文法产生的语言,证明了DNA编码文法的存在性;通过简化文法的字母表,将DNA编码文法的设计问题转化为二进制文法的设计问题,得到了DNA编码文法的两个性质。
DNA computing is a new computing paradigm which uses biological molecules as calculation medium and biochemical reaction as calculation tool. Generally considering, although the ability of the classical electronic computer is un-assailable when it executes serial tasks. DNA computing shows natural advantages compared with the classical electronic computer in solving NP hard problems. In this thesis, some problems in DNA computing are discussed and studied. The main results are as follows:
The shortest directed path problem is to find a directed path with minimum weight in two pointed vertices of a directed network. It has extensive applications in engineering practice. Sticker system and delete system are two abstract models in DNA computing. In this thesis, we propose DNA computing model and realization algorithm of the shortest directed path problem using the high parallelism of sticker system and delete system and give an example to show the whole process.
DNA encoding problem is to design the initial solutions of DNA computing, and the quality of DNA codes could determine whether the DNA computing is successful or not. In this thesis, we view DNA code as a language generated by some grammar and prove the existence of the DNA encoding grammar. Then, by simplifying the alphabet of the grammar, we transform the grammar design of DNA code to that of the binary, and obtain two properties of the DNA encoding grammar.
引文
1.李承祖.量子通信和量子计算机[M].国防科技大学出版社,2000.
2.陈虎,戴葵,胡守仁.环行阵列神经网络计算机系统[J].计算机研究与发展,1999,36(2):144-149.
3.Vlatko V.,Martin B.Basic of Quantum Computation[J].Progress in Quantum Electronics,1998,22:1-39.
4.许进.DNA计算与运筹学发展的新机遇[J].《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company 香港,2000:43-54(注:特邀大会主题报告).
5.Adleman L.Molecular Computation of Solution to Combinatorial Problems[J].Science.1994,66(11):1021-1024.
6.Paun G.,Rozenberg G.,Salomaa.DNA Computing-A New Computing Paradigms[M].Springer,1998.
7.Feyman R.P.There's Plenty of Room at the Bottom,In Minaturization[J].D.H.Gilbert.ED.Reinhold,New York,1961,282-296.
8.Roweis S,Winfree E,Burgoyne R,et al.A Sticker Based Architecture for DNA Computation[J].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.
9.Lipton R.J.DNA Solution of Hard Computation Problems.Science,1995,268(4):542-545.
10.Qi Ouyang,et al.DNA Solution of the Maximal Clique Problem,Science,1997,278:446-449.
11.Sakamoto et al.Molecular Computation by Hairpin Formation.Science,2000,288:1223-1226.
12.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.
13.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[J].Science,2002,296:499-502.
14.Luca Bortolussi,Andrea Sgarro.Possibilistic Channels for DNA Computing.Submitted to Journal of Discrete Mathematical Sciences and Cryptography,pp.178-186,2005.
15.Christiaan,V.Thomas,N.Kok.DNA Computing of Solutions to Knapsack Problems.Bio-Systems.88(2007) 156-1.
16.张凤月,殷志祥,许进.基于芯片上的DNA计算.生物化学与生物物理进展[J],2003,30(3):412-415.
17.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[J].4th Int.Meeting on DNA-Based Computing,Baltimore,Penns(June,1998)
18.Yin Z.X.,Zhang F.Y,Xu Jin.A Chinese Postman Problem Based on DNA Computing [J].Journal of Chemical Information and Computer Sciences,2002,42(2):224-224.
19.Yin Zhixiang,Tang Shuangqing,Dong Yafei,Zhang Yumin.Working Operation Problem Based on DNA Computing[J].Proc.SPIE,5253:870-873,FifthInternational Symposium on Instrumentation and Control Technology,Oct.2003,Beijing(ISICT,2003).
20.Kari L.,Gloor G.,Yu S.Using DNA to Solve the Bounded Post Correspondence Problem [J].Theoretical Computer Science,2000,231(2):193-203.
21.Guarnieri F.,Fliss M.,Bancroft Making DNAAdd[J].Science,1996,273:220-223.
22.Boneh D.,Dunworth C.,Lipton R.J.Breaking DES Using a Molecular Computer[J].Princeton CS Tech-Report number CS-TR-489-95(1995).
23.Williams R.,Wood H.Computer Algebra Problems Interconnect with Molecular Reactions and Complexity Theory[J].In Proceeding Soft the 2ndDIMACS workshop on DNA-based computers,1996.
24.陆维明.Petri网与DNA计算[J].计算机科学,25(1)(1998)1-3.
25.Freund R,Paun G.,Rozenberg G.,et al.Watson-Crick Finite Automata[J],3~(rd)DIMACS Meeting on DNA Based Computers,Univ of Penns(June,1997).
26.Head T.Formal Language Theory and DNA:An Analysis of The Generative Capacity of Spastic Recombinant Behaviors[J],Bull.Math.Biology,1987,49:737-759.
27.Head T.Splicing System and Molecular Processes[J].ICEC'97 Special Session on DNA Based Computation,Indiana,April,1997.
28.Paun G..DNA Computing Based on Splicing:Universality Results[J].Theoretical Computer Science,2000,231(2):275-296
29. Mateesu A., Paun G, Rozenberg G, Salomaa A .,SimpIe Splicing Systems[J].Discrete Applied Mathematics,1998,84(1-3):145-163.
30. Benenson Y., Paz-Elizur T., Adar R., et al.. Programmable and Autonomous Computing Machine Made of Biomolecules [J], Nature, 2001, 414(6862):430-434.
31. Roweis S., Winfree E., Burgoyne R., et al.. A Sticker Based Architecture for DNA Computation [J]. 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.
32. Kari L., Paun G, Rozenberg G, et al. DNA Computing, Sticker Systems and Universality [J]. Acta Informatica, 1998,35:401-420.
33. Gheorghe Paun and Grzegorz Rozenberg, Sticker systems [J].Theoretical computer science, 1998 (204):183-203.
34. L.Kari, G. Thierrin. Contextual Insertions-Deletions and Computability [J]. Inf. Comput.,1996,131,47-61.
35. C.Martin-Vide, Gh.Paun, Salomaa. Characterizations of Recursively Enumerable Languages by means of Insertion Grammars[J] .Theoretical Computer Science ,205,1-2(1998),195-205.
36. L.Kari, GPaun, GThierrin, 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.
37. A. Takahara. On the Computational Power of Insertion-Deletion Systems [J].Proc .of 8th International Meeting on DNA Based Computers June, Sapporo,139-150,2002.
38. 朱玉贤,李毅.现代分子生物学[M].北京:高等教育出版社, 2002.7.
39. Zuwairie Ibrahim, Yusei Tsuboi, et al. A Study on Lower Bound of Direct Proportional Length-Based DNA Computing for Shortest Path Problem [J].CIS2004, LNCS3314,pp.71-76,2004
40. Zuwairie Ibrahim, Yusei Tsuboi, et al. Molecular Computation Approach to Compete Dijkstra's Algorithm [C]. 5th Asian Control Conference, 2005:22-28.
41. Garzon M, Deaton R, Nino L F, Stevens S E , Wittner M. Genome Encoding for DNA Computing[A].The Third DIMACS Workshop on DNA 2based Computing[J].U of Pennsylvania,1997.230-237.
42.E B Baum.DNA Sequences Useful for Computation[A].P roc Second Annual Meeting on DNA Based Computers[C].American Mathematical Society,1996.
43.A G Frutos,et al.Demonstration of a Word Design Strategy for DNA Computing on Surface[J].Nucleic Acids Research,1997,25(23):4748-4757.
44.Ravinderjit Braich,Cli-Johnson,Paul W K Rothemund,Leonard M Adleman.Solution of a Satisfiability Problem Based on DNA Computer[J].The 6th International Workshop on DNA Based Computers[J].London Springer Verlag,2001.27-42.
45.Deaton R,et al.A DNA Based Implementation of An Evolutionary Search for Good Encodings for DNA Computation[A].Proceedings IEEE Conference on Evolutionary Computation[C].IEEE Press,1997.267-271.
46.Deaton R,et al.Genetic Search of Reliable Encodings for DNA Based Computation[A].1st Genetic Programming Conference[C].Stanford Bookstore,1996.9-15.
47.John SantaLucia,Jr,Hatim T Allawi,P Ananda Seneviratne.Improved Nearest-neighbor Parameters for Predicting DNA Duplex Stability[J].Biochemistry 1996,35(11),3555-3562.
48.吴哲辉,吴振寰.形式语言与自动机理论[M].北京:机械工业出版社,2007年4月,104-119.
2.陈虎,戴葵,胡守仁.环行阵列神经网络计算机系统[J].计算机研究与发展,1999,36(2):144-149.
3.Vlatko V.,Martin B.Basic of Quantum Computation[J].Progress in Quantum Electronics,1998,22:1-39.
4.许进.DNA计算与运筹学发展的新机遇[J].《中国运筹学会第六届学术交流会论文集》(上卷)(主编:章祥荪,王建方,刘宝碇,刘德刚),Global-Link Publishing Company 香港,2000:43-54(注:特邀大会主题报告).
5.Adleman L.Molecular Computation of Solution to Combinatorial Problems[J].Science.1994,66(11):1021-1024.
6.Paun G.,Rozenberg G.,Salomaa.DNA Computing-A New Computing Paradigms[M].Springer,1998.
7.Feyman R.P.There's Plenty of Room at the Bottom,In Minaturization[J].D.H.Gilbert.ED.Reinhold,New York,1961,282-296.
8.Roweis S,Winfree E,Burgoyne R,et al.A Sticker Based Architecture for DNA Computation[J].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.
9.Lipton R.J.DNA Solution of Hard Computation Problems.Science,1995,268(4):542-545.
10.Qi Ouyang,et al.DNA Solution of the Maximal Clique Problem,Science,1997,278:446-449.
11.Sakamoto et al.Molecular Computation by Hairpin Formation.Science,2000,288:1223-1226.
12.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.
13.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[J].Science,2002,296:499-502.
14.Luca Bortolussi,Andrea Sgarro.Possibilistic Channels for DNA Computing.Submitted to Journal of Discrete Mathematical Sciences and Cryptography,pp.178-186,2005.
15.Christiaan,V.Thomas,N.Kok.DNA Computing of Solutions to Knapsack Problems.Bio-Systems.88(2007) 156-1.
16.张凤月,殷志祥,许进.基于芯片上的DNA计算.生物化学与生物物理进展[J],2003,30(3):412-415.
17.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[J].4th Int.Meeting on DNA-Based Computing,Baltimore,Penns(June,1998)
18.Yin Z.X.,Zhang F.Y,Xu Jin.A Chinese Postman Problem Based on DNA Computing [J].Journal of Chemical Information and Computer Sciences,2002,42(2):224-224.
19.Yin Zhixiang,Tang Shuangqing,Dong Yafei,Zhang Yumin.Working Operation Problem Based on DNA Computing[J].Proc.SPIE,5253:870-873,FifthInternational Symposium on Instrumentation and Control Technology,Oct.2003,Beijing(ISICT,2003).
20.Kari L.,Gloor G.,Yu S.Using DNA to Solve the Bounded Post Correspondence Problem [J].Theoretical Computer Science,2000,231(2):193-203.
21.Guarnieri F.,Fliss M.,Bancroft Making DNAAdd[J].Science,1996,273:220-223.
22.Boneh D.,Dunworth C.,Lipton R.J.Breaking DES Using a Molecular Computer[J].Princeton CS Tech-Report number CS-TR-489-95(1995).
23.Williams R.,Wood H.Computer Algebra Problems Interconnect with Molecular Reactions and Complexity Theory[J].In Proceeding Soft the 2ndDIMACS workshop on DNA-based computers,1996.
24.陆维明.Petri网与DNA计算[J].计算机科学,25(1)(1998)1-3.
25.Freund R,Paun G.,Rozenberg G.,et al.Watson-Crick Finite Automata[J],3~(rd)DIMACS Meeting on DNA Based Computers,Univ of Penns(June,1997).
26.Head T.Formal Language Theory and DNA:An Analysis of The Generative Capacity of Spastic Recombinant Behaviors[J],Bull.Math.Biology,1987,49:737-759.
27.Head T.Splicing System and Molecular Processes[J].ICEC'97 Special Session on DNA Based Computation,Indiana,April,1997.
28.Paun G..DNA Computing Based on Splicing:Universality Results[J].Theoretical Computer Science,2000,231(2):275-296
29. Mateesu A., Paun G, Rozenberg G, Salomaa A .,SimpIe Splicing Systems[J].Discrete Applied Mathematics,1998,84(1-3):145-163.
30. Benenson Y., Paz-Elizur T., Adar R., et al.. Programmable and Autonomous Computing Machine Made of Biomolecules [J], Nature, 2001, 414(6862):430-434.
31. Roweis S., Winfree E., Burgoyne R., et al.. A Sticker Based Architecture for DNA Computation [J]. 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.
32. Kari L., Paun G, Rozenberg G, et al. DNA Computing, Sticker Systems and Universality [J]. Acta Informatica, 1998,35:401-420.
33. Gheorghe Paun and Grzegorz Rozenberg, Sticker systems [J].Theoretical computer science, 1998 (204):183-203.
34. L.Kari, G. Thierrin. Contextual Insertions-Deletions and Computability [J]. Inf. Comput.,1996,131,47-61.
35. C.Martin-Vide, Gh.Paun, Salomaa. Characterizations of Recursively Enumerable Languages by means of Insertion Grammars[J] .Theoretical Computer Science ,205,1-2(1998),195-205.
36. L.Kari, GPaun, GThierrin, 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.
37. A. Takahara. On the Computational Power of Insertion-Deletion Systems [J].Proc .of 8th International Meeting on DNA Based Computers June, Sapporo,139-150,2002.
38. 朱玉贤,李毅.现代分子生物学[M].北京:高等教育出版社, 2002.7.
39. Zuwairie Ibrahim, Yusei Tsuboi, et al. A Study on Lower Bound of Direct Proportional Length-Based DNA Computing for Shortest Path Problem [J].CIS2004, LNCS3314,pp.71-76,2004
40. Zuwairie Ibrahim, Yusei Tsuboi, et al. Molecular Computation Approach to Compete Dijkstra's Algorithm [C]. 5th Asian Control Conference, 2005:22-28.
41. Garzon M, Deaton R, Nino L F, Stevens S E , Wittner M. Genome Encoding for DNA Computing[A].The Third DIMACS Workshop on DNA 2based Computing[J].U of Pennsylvania,1997.230-237.
42.E B Baum.DNA Sequences Useful for Computation[A].P roc Second Annual Meeting on DNA Based Computers[C].American Mathematical Society,1996.
43.A G Frutos,et al.Demonstration of a Word Design Strategy for DNA Computing on Surface[J].Nucleic Acids Research,1997,25(23):4748-4757.
44.Ravinderjit Braich,Cli-Johnson,Paul W K Rothemund,Leonard M Adleman.Solution of a Satisfiability Problem Based on DNA Computer[J].The 6th International Workshop on DNA Based Computers[J].London Springer Verlag,2001.27-42.
45.Deaton R,et al.A DNA Based Implementation of An Evolutionary Search for Good Encodings for DNA Computation[A].Proceedings IEEE Conference on Evolutionary Computation[C].IEEE Press,1997.267-271.
46.Deaton R,et al.Genetic Search of Reliable Encodings for DNA Based Computation[A].1st Genetic Programming Conference[C].Stanford Bookstore,1996.9-15.
47.John SantaLucia,Jr,Hatim T Allawi,P Ananda Seneviratne.Improved Nearest-neighbor Parameters for Predicting DNA Duplex Stability[J].Biochemistry 1996,35(11),3555-3562.
48.吴哲辉,吴振寰.形式语言与自动机理论[M].北京:机械工业出版社,2007年4月,104-119.