电子计算机的发展给人类社会进步带来了极大的推动作用，但是随着电子计算机制造工艺趋于极限，人们迫切需要找到一种新的计算体系来满足日益增长的计算需求。DNA计算因其超强的信息存储、大规模的并行计算能力和超低的能耗而受到了广泛的关注。自1994年Adlian博士在实验室利用DNA完成了一个6顶点哈密尔顿路求解问题开始，各种计算模型纷纷涌现。本文首先对DNA计算的基本原理和实验操作手段进行了简单的介绍，然后对DNA相关的理论进行了阐述，包括DNA计算中序列编码设计的理论、DNA计算模型复杂度分析与通用计算能力的证明；在此基础上，对突破性的DNA计算模型进行了概括，进而根据实验操作的具体手段将所有已知模型进行了分类，按照类别进行了综述，并随后挑选了该类别中经典的模型进行更为直观的分析。更进一步，在文章的最后，结合笔者的工作对DNA计算领域的前景进行了展望。
The development in computer science has brought a great impetus to the advance of human society. However, as the manufacturing process goes to the limit, there is an urgent need to find a new computing system to meet the growing demand for computing. DNA computing has attracted great attention due to its advantages in huge information storage, large scale parallelism and very low energy consumption. Many different models have been established ever since the experimental implementation of solving a 6 vertices Hamilton pathway problem by Adleman in 1994. In this paper, a brief introduction to the basic principles and experimental operations in DNA computing is first given, and the theories in this field are illustrated, including the DNA sequence design, complexity of different models and the proof of universal computing power. Moreover, the models regarded as breakthroughs in the field are summarized. All the models are classified based on the specific means in conducting the experiment, and reviewed according to different classes. More detailed descriptions are further set forth for a classical model in each class. At last, a prospect is made based on our work in this area.
Contents
1 Introduction
2 Principles and experimental operations of DNA computing
2.1 Principles of DNA computing
2.2 Experimental operations of DNA computing
3 Advances in DNA computing related theories
3.1 Principles of DNA sequence design
3.2 Universal computing power of DNA
4 Five kinds of DNA computing models
4.1 Parallel overlap assembly model
4.2 Sticker model
4.3 Splicing model
4.4 DNA Tile self-assembly model
4.5 Biochemistry signal based logic circuits model
5 Conclusion and outlook
[1] 许进(Xu J), 张雷(Zhang L). 计算机学报(Chinese Journal of Computers), 2003, 26(1):1.
[2] 许进(Xu J), 黄布毅(Huang B Y). 计算机学报(Chinese Journal of Computers), 2005, 28(10):1583.
[3] Adleman L M. Science, 1994, 266(5187):1021.
[4] Feynman R P. Caltech Engineering and Science, 1959, 23:22.
[5] Seeman N C. Journal of Theoretical Biology, 1982, 99(2):237.
[6] Lipton R J. Science, 1995, 268(5210):542.
[7] Seeman N C. Annual Review of Biophysics & Biomolecular Structure, 1998, 27(1):225.
[8] Mao C D, Sun W Q, Seeman N C. Journal of the American Chemical Society, 1999, 121(23):5437.
[9] Cooper D C, Wang H. Journal of Symbolic Logic, 1967, 32(1):119.
[10] Winfree E. Proceedings of the DNA Based Computers. DIMACS, American Mathematical Society, 1995(27).
[11] Mao C D, LaBean T H, Reif J H, Seeman N C. Nature, 2000, 407(6803):493.
[12] Ouyang Q, Kaplan P D, Liu S M, Libchaber A. Science, 1997, 278(5337):446.
[13] Eng T L. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1999, 48:101.
[14] Hagiya M, Arita M, Kiga D, Sakamoto K, Yokoyama S. Proc. of DNA DIMACS, 1997, 48:57.
[15] Head T, Rozenberg G, Bladergroen R S, Breek C K, Lommerse P H, Spaink H P. Biosystems, 2000, 57(2):87.
[16] Sakamoto K, Gouzu H, Komiya K, Kiga D, Yokoyama S, Yokomori T, Hagiya M. Science, 2000, 288(5469):1223.
[17] Braich R S, Chelyapov N, Johnson C, Adleman L. Science, 2002, 296(5567):499.
[18] Baum E B. American Mathematical Society, 1996, 44:235.
[19] Garzon G M, Neathery P, Deaton R, Murphy R C, Ranceschetti D R F, Stevens S E. Stanford Stanford University, 2010, 32(1):636.
[20] Frutos A G, Smith L M, Corn R M. Journal of the American Chemical Society, 1998, 120:10277.
[21] Marathe A, Condon A E, Corn R M. Journal of Computational Biology, 2001, 8(3):201.
[22] Arita M, Nishikawa A, Hagiya M, Komiya K, Gouzu H, Sakamoto K. Proceedings of Genetic and Evolutionary Computation Conference. San Francisco:Morgan Kaufmann, 2000. 875.
[23] Deaton R, Murphy R C, Garzon M, Franceschetti D R, Stevens S E. Proceedings of the 2nd Annual DIMACS Workshop(Princeton University), New Jersey:American Mathematical Society, 2010. 247.
[24] 黄布毅(Huang B Y). 华中科技大学博士论文(Doctoral Dissertation of Huazhong University of Science and Technology),2005.
[25] 李鲁华(Li L H). 新疆大学硕士论文(Master Dissertation of Xinjiang University), 2006.
[26] 马芳芳(Ma F F). 山东科技大学硕士论文(Master Dissertation of Shandong University of Science and Technology), 2008.
[27] 鲍士军(Bao S J). 安徽理工大学硕士论文(Master Dissertation of Anhui University of Science and Technology), 2009.
[28] 吴海龙(Wu H L). 山东师范大学硕士论文(Master Dissertation of Shandong Normal University), 2012.
[29] Lipton R J. Proceedings of the International Conference on Intelligent Networking & Collaborative Systems. IEEE Computer Society, 2007. 222.
[30] Winfree E. DNA Based Computers, 1996:187.
[31] Boneh D, Dunworth C, Lipton R J, Sgall J. Discrete Applied Mathematics, 1996, 71(1/3):79.
[32] Winfree E, Yang X P, Seeman N C. DNA Based Computers Ⅱ, 1999, 44:191.
[33] Reif J H. Algorithmica, 1999, 25(2):142.
[34] Adleman L, Cheng Q, Goel A, Huang M D. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. Hersonissos Greece:ACM Press, 2001. 740.
[35] Rothemund P W K, Winfree E. Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Hersonissos Greece:ACM Press, 2000. 459.
[36] Brun Y. Theoretical Computer Science, 2007, 378(1):17.
[37] Fukagawa H, Fujiwara A. Proceedings of the International Conference on Foundations of Computer Science. Las Vegas:CSREA Press, 2006. 95.
[38] 黄育潜(Huang Y Q). 计算机学报(Chinese Journal of Computers), 2008, 31(3):353.
[39] 黄育潜(Huang Y Q). 中国计算机学会(China Computer Federation), 2011.
[40] Bach E, Condon A, Glaser E, Tanguay C. IEEE Conference on Computational Complexity. Academic Press, 1996. 172.
[41] Chang W L, Ho M S, Guo M Y. Biosystems, 2004, 73(2):117.
[42] Guo M Y, Ho M S, Chang W L. Parallel Computing, 2004, 30(9/10):1109.
[43] 刘文斌(Liu W B),许进(Xu J).系统工程与电子技术(Journal of Systems of Engineering and Electronics), 2002, 24(6):99.
[44] 周康(Zhou K), 刘文斌(Liu W B), 许进(Xu J).系统工程与电子技术(Journal of Systems of Engineering and Electronics), 2007, 29(2):316.
[45] 周康(Zhou K), 强小利(Qiang X L), 同小军(Tong X J), 许进(Xu J).计算机工程与应用(Computer Engineering and Applications), 2007, 43(29):43.
[46] Liu X M, Yin J W, Jwo J S, Feng Z L, Dong J X. International Conference on Intelligent Computing, Hefei. 2005. 99.
[47] Muhammad M S, Ueda S, Ono O, Watada J, Khalid M. Soft Computing as Transdisciplinary Science and Technology. Heidelberg:Springer, 2005.
[48] 李宏(Li H). 北京工业大学硕士论文(Master Dissertation of Beijing University of Technology), 2003.
[49] 郭帅(Guo S). 北京工业大学硕士论文(Master Dissertation of Beijing University of Technology), 2006.
[50] Liu X C, Yang X F, Tang Y Y. Journal of Mathematical Chemistry, 2008, 44(1):172.
[51] Li K L, Zou S T, Jin X. Journal of Biomedicine & Biotechnology, 2008(1):749.
[52] 薛圣伟(Xue S W). 山东科技大学硕士论文(Master Dissertation of Shandong University of Science and Technology), 2008.
[53] 鲍士军(Bao S J), 殷志祥(Yin Z X), 王伟(Wang W).科技广场(Science Mosaic), 2008,(7):6.
[54] 周旭(Zhou X).湖南大学硕士论文(Master Dissertation of Hunan University), 2009.
[55] Zhou X, Yue G X, Yang Z B, Li K L. Journal of Software, 2010, 5(6):662.
[56] Zhao H C, Liu X Y. Proceedings of the 2012 International Conference on Pervasive Computing and the Network World. Istanbul:Springer, 2012. 869.
[57] Roweis S, Winfree E, Burgoyne R, Chelyapov N V, Goodman M F, Rothemund P W K, Adleman L M. Journal of Computational Biology a Journal of Computational Molecular Cell Biology, 1998, 5(4):615.
[58] Yurke B, Mills A P, Cheng S L.Biosystems, 1999, 52(1/3):165.
[59] 殷志祥(Yin Z X), 张风月(Zhang F Y),许进(Xu J).生物数学学报(Journal of Biomathematics), 2003, 18(4):497.
[60] 殷志祥(Yin Z X), 张风月(Zhang F Y),许进(Xu J). 电子与信息学报(Journal of Electronics and Information Technology), 2003, 25(1):62.
[61] 王淑栋(Wang S D).华中科技大学博士论文(Doctoral Dissertation of Huazhong University of Science and Technology),2004.
[62] 董亚非(Dong Y F).华中科技大学博士论文(Doctoral Dissertation of Huazhong University of Science and Technology),2004.
[63] 高美娟(Gao M J).北京工业大学硕士论文(Master Dissertation of Beijing University of Technology), 2005.
[64] 许进(Xu J), 董亚非(Dong Y F), 魏小鹏(Wei X P). 科学通报(Chinese Science Bulletin), 2004, 49(3):205.
[65] 许进(Xu J), 李三平(Li S P), 董亚非(Dong Y F), 魏小鹏(Wei X P).科学通报(Chinese Science Bulletin), 2004, 49(4):299.
[66] Wang L, Chen Z P, Jiang X H, Liu S L. Computational Science and its Applications. Heidelberg:Springer, 2005.
[67] 王雷(Wang L),林亚平(Lin Y P). 电子与信息学报(Journal of Electronics and Information Technology), 2005, 27(5):814.
[68] Yang Y X, Wang A M, Ma J L. Proceedings of the Fourth International Conference on Natural Computation. IEEE Computer Society, 2008. 547.
[69] 刘高峰(Liu G F), 牟廉明(Mou L M), 代锡彬(Dai X B).内江师范学院学报(Journal of Neijiang Normal University), 2009, 24(6):14.
[70] Zhang M J, Cheng M X, Tarn T J. Combinatorial Optimization, 2006, 18:639.
[71] 涂旭东(Tu X D). 重庆大学硕士论文(Master Dissertation of Chongqing University), 2009.
[72] Shapiro E, Benenson Y, Adar R, Paz E T. Europe PMC Funders, 2011, 414(6862).
[73] 李慧(Li H). 北京工业大学硕士论文(Master Dissertation of Beijing University of Technology), 2003.
[74] 马润年(Ma R N), 张强(Zhang Q), 高琳(Gao L), 许进(Xu J). 电子学报(Chinese Journal of Electronics), 2004, 32(1):13.
[75] 张连珍(Zhang L Z), 刘光武(Liu G W), 许进(Xu J). 计算机工程与应用(Computer Engineering and Applications), 2004, 40(4):51.
[76] 吴雪(Wu X),赵艺(Zhao Y).电子与信息学报(Journal of Electronics and Information Technology), 2007, 29(11):2693.
[77] 郭佳(Guo J). 北京工业大学硕士论文(Master Dissertation of Beijing University of Technology), 2007.
[78] 张社民(Zhang S M). 华中科技大学博士论文(Doctoral Disesrtation of Huazhong University of Science and Technology),2007.
[79] 任祖云(Ren Z Y). 安徽理工大学硕士论文(Master Dissertation of Anhui University of Science and Technology), 2009
[80] 刘伟(Liu W), 郭迎(Guo Y), 孟大志(Meng D Z).计算机工程与应用(Computer Engineering and Applications), 2010, 46(20):157.
[81] 刘伟(Liu W), 郭迎(Guo Y), 孟大志(Meng D Z).计算机工程与应用(Computer Engineering and Applications), 2010, 46(20):161.
[82] 孙守霞(Sun S X), 刘伟(Liu W), 郭迎(Guo Y), 孟大志(Meng D Z). 计算机工程与应用(Computer Engineering and Applications), 2012, 48(32):39.
[83] 郭洪敏(Guo H M). 安徽理工大学硕士论文(Master Dissertation of Anhui University of Science and Technology), 2016.
[84] Winfree E, Liu F R, Wenzler L A, Seeman N C. Nature, 1998, 394(6693):539.
[85] Lagoudakis M G, Labean T H. Proceedings of the 5th International Meeting on DNA Based Computers, MIT. 1999. 141.
[86] LaBean T H, Yan H, Kopatsch J, Liu F R, Winfree E, Reif J H, Seeman N C. Journal of the American Chemical Society, 2000, 122(9):1848.
[87] Yan H, LaBean T H, Feng L P, Reif J H. Proc. Natl. Acad. Sci., 2003, 100(14):8103.
[88] Yan H, Park S H, Finkelstein G, Reif J H, LaBean T H. Science, 2003, 301(5641):1882.
[89] Rothemund P W K, Papadakis N, Winfree E. PLoS Biology, 2004, 2(12):424.
[90] Cook M, Rothemund P W K,Winfree E. Lecture Notes in Computer Science, 2004, 2943:91.
[91] Barish R D, Rothemund P W K, Winfree E. Nano Letters, 2005, 5(12):2586.
[92] Fujibayashi K, Murata S. Proceedings of the International Conference on DNA Computering. Milan:Springer, 2004. 113.
[93] Rothemund P W K. Nature, 2006, 440(7082):297.
[94] Fujibayashi K, Hariadi R, Park S H, Winfree E, Murata S. Nano Letters, 2008, 8(7):1791.
[95] Limura N, Yamamoto M, Tanaka F, Proceedings of the International Conference on DNA Computering. Memphis:Springer, 2007. 140.
[96] Zhang X C, Wang Y F, Chen Z H, Xu J, Cui G Z. Progress in Natural Science:Materials International, 2009, 19(3):377.
[97] Fujibayashi K, Zhang D Y, Winfree E, Murata S. Natural Computing, 2009, 8(3):589.
[98] 程珍(Cheng Z). 华中科技大学博士论文(Doctoral Dissertation of Huazhong University of Science and Technology), 2010.
[99] Cheng Z, Huang Y F, Xu J. Proceedings of the International Conference of Bio-Inspired Computing:Theory and Applications. Adelaide:IEEE, 2010, 7(5):31.
[100] Cheng Z. Journal of Computational & Theoretical Nanoscience, 2012, 9(3):336.
[101] Cheng Z, Xu J, Huang Y F, Zhang X C, Zhou K. Journal of Computational & Theoretical Nanoscience, 2009, 6(5):1161.
[102] Cheng Z, Huang Y F, Chen Z, Zhang X C. Proceedings of the International Conference of Bio-inspired Computing. Beijing:IEEE, 2009. 1.
[103] Cheng Z, Chen Z H, Huang Y H, Xu J. Journal of Computational & Theoretical Nanoscience, 2010, V(4):490.
[104] 程珍(Cheng Z), 黄玉芳(Huang Y F), 周康(Zhou K). 计算机学报(Chinese Journal of Computers), 2009, 32(12):2338.
[105] Cheng Z, Cheng Z. International Journal of Computers Communications & Control, 2014, 7(4):616.
[106] 程珍(Cheng Z), 许进(Xu J), 周康(Zhou K).华中科技大学学报:自然科学版(Journal of Huangzhong University of Science and Technology:Nature Science), 2011, 39(2):15.
[107] Bozdemir O A, Guliyev R, Buyukcakir O, Selcuk S, Kolemen S, Gulseren G, Nalbantoglu T, Boyaci H, Akkaya E U. Journal of the American Chemical Society, 2010, 132:8029.
[108] Macdonald J, Yang L, Sutovic M, Lederman H, Pendri K, Lu W H, Andrews B L, Stefanovic D, Stojanovic M N. Nano Letters, 2006, 6:2598.
[109] Ogihara M, Ray A. Nature, 2000, 403:143.
[110] Benenson Y, Gil B, Bendor U, Adar R, Shapiro E. Nature, 2004, 429:423.
[111] Liu W B, Shi X H, Zhang S M, Liu X R, Xu J. Biosystems, 2004, 77(1/3):87.
[112] 朱翔鸥(Zhu X O), 刘文斌(Liu W B), 陈丽春(Chen L C), 吴桂初(Wu G C).计算机科学(Computer Science), 2008, 35:178.
[113] Li T, Zhang L B, Ai J, Dong S J, Wang E K. ACS Nano, 2011, 5(8):6334.
[114] Kang D, White R J, Xia F, Zuo X L, Vallée-Bélisle A, Plaxco KW. NPG Asia Materials, 2012, 4(1):e1.
[115] Li T, Ackermann D, Hall A M, Famulok M. Journal of the American Chemical Society, 2012, 134:3508.
[116] Pei H, Liang L, Yao G B, Li J, Huang Q, Fan C H. Angewandte Chemie International Edition, 2012,51(36):9020.
[117] Li W, Yang Y, Yan H, Liu Y. Nano Letters, 2013, 13:2980.
[118] Xu S L, Li H L, Miao Y Q, Liu Y Q, Wang E K. NPG Asia Materials, 2013, 5:e76.
[119] Zhu J B, Zhang L B, Li T, Dong S J, Wang E K. Advanced Materials, 2013, 25:2440.
[120] Jiang Q, Wang Z G, Ding B Q. Small, 2013, 9(7):1016.
[121] Zhu J B, Zhang L B, Zhou Z X, Dong S J, Wang E K. Chemical Communications, 2014, 50(25):3321.
[122] Gaber R, Lebar T, Majerle A, Šter B, Dobnikar A, Ben? ina M, Jerala R. Nature Chemical Biology, 2014, 10:203.
[123] Guo Y H, Zhou L, Xu L J, Zhou X D, Hu J M, Pei R J. Scientific Reports, 2014, 4:7315.
[124] Mailloux S, Gerasimova Y V, Guz N, Kolpashchikov D M, Katz E. Angewandte Chemie International Edition, 2015,54(22):6562.
[125] Li H L, Liu Y Q, Dong S J, Wang E K. NPG Asia Materials, 2015, 7:e166.
[126] Wei H, Hu B, Tang S M, Zhao G J, Guan Y F. Scientific Reports, 2016, 6:37477.
[127] Zhai Q F, Fan D Q, Zhang X W, Li J, Wang E K. NPG Asia Mater, 2017, 9:e421.
[128] Chatterjee G, Dalchau N, Muscat R A, Phillips A, Seelig G. Nature Nanotechnology, 2017, 12(9):920.
[129] Xu J. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(7):1405.
PDF
(8813KB)
