中文
Earlier issues
Announcement
More
Progress in Chemistry 2017, Vol. 29 Issue (11): 1297-1315 DOI: 10.7536/PC170701 Previous Articles   Next Articles

Special Issue: 计算化学

• Review •

Computation in Chemistry:A Summary of the Development and Models of DNA Computing

Xiaoyao Yin1, Fei Li2, Xiaochen Bo2*, Zhigang Luo1*, Xiaolei Zuo3*   

  1. 1. Science and Technology on Parallel and Distributed Processing Laboratory, College of Computer, National University of Defense Technology, Changsha 410073, China;
    2. Beijing Institute of Radiation Medicine, Academy of Military Medical Sciences, Beijing 100850, China;
    3. Division of Physical Biology & Bioimaging Center, Shanghai Institute of Applied Physics, Chinese Academy of Sciences, Shanghai 201800, China
  • Received: Revised: Online: Published:
  • Supported by:
    The work was supported by the National Natural Science Foundation of China (No. 21422508).
PDF ( 908 ) Cited
Export

EndNote

Ris

BibTeX

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
Key words: DNA computing, NP hard problem, parallel overlap assemble model, sticker model, splicing model, DNA Tile self-assembly, biochemical signal logic gate

CLC Number: 

[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.
[1] Shao Xueguang**,Jiang Haiyan,Cai Wensheng. Advances in Biomolecular Computing [J]. Progress in Chemistry, 2002, 14(01): 37-.