logo

SCIENCE CHINA Information Sciences, Volume 62 , Issue 6 : 061301(2019) https://doi.org/10.1007/s11432-018-9530-x

DNA computing for combinational logic

More info
  • ReceivedApr 5, 2018
  • AcceptedJul 23, 2018
  • PublishedOct 22, 2018

Abstract

With the progressive scale-down of semiconductor's feature size, people are looking forward to More Moore and More than Moore. In order to offer a possible alternative implementation process, researchers are trying to figure out a feasible transfer from silicon to molecular computing. Such transfer lies on bio-based modules programming with computer-like logic, aiming at realizing the Turing machine. To accomplish this, the DNA-based combinational logic is inevitably the first step we have taken care of. This timely overview study introduces combinational logic synthesized in DNA computing from both analog and digital perspectives separately. State-of-the-art research progress is summarized for interested readers to quick understand DNA computing, initiate discussion on existing techniques and inspire innovation solutions. We hope this study can pave the way for the future DNA computing synthesis.


Acknowledgment

This work was supported in part by National Natural Science Foundation of China (Grant Nos. 61871115, 61501116), Jiangsu Provincial Natural Science Foundation for Excellent Young Scholars, Huawei HIRP Flagship under (Grant No. YB201504), the Fundamental Research Funds for the Central Universities, the SRTP of Southeast University, State Key Laboratory of ASIC System (Grant No. 2016KF007), ICRI for MNC, and the Project Sponsored by the SRF for the Returned Overseas Chinese Scholars of MoE.


References

[1] Kish L B. End of Moore's law: thermal (noise) death of integration in micro and nano electronics. Phys Lett A, 2002, 305: 144-149 CrossRef ADS Google Scholar

[2] Desai S B, Madhvapathy S R, Sachid A B, et al. MoS2 transistors with 1-nanometer gate lengths. Science, 2016, 354: 99--102. Google Scholar

[3] Yahiro W, Hagiya M, Implementation of Turing machine using DNA strand displacement. In: Proceedings of International Conference on Theory and Practice of Natural Computing. Berlin: Springer, 2016. 161--172. Google Scholar

[4] Wikipedia. Combinational logic. 2018. https://en.wikipedia.org/wiki/Combinational_logic. Google Scholar

[5] Khalil A S, Collins J J. Synthetic biology: applications come of age. Nat Rev Genet, 2010, 11: 367. Google Scholar

[6] Siuti P, Yazbek J, Lu T K. Synthetic circuits integrating logic and memory in living cells.. Nat Biotechnol, 2013, 31: 448-452 CrossRef PubMed Google Scholar

[7] Andrianantoandro E, Basu S, Karig D K, et al. Synthetic biology: new engineering rules for an emerging discipline. Molecular Syst Biology, 2006, 2. Google Scholar

[8] Green A A, Kim J, Ma D. Complex cellular logic computation using ribocomputing devices. Nature, 2017, 548: 117-121 CrossRef PubMed ADS Google Scholar

[9] Feynman R P. There's plenty of room at the bottom. Eng Sci, 1960, 23: 22--36. Google Scholar

[10] Trautman J K, Macklin J J, Brus L E. Near-field spectroscopy of single molecules at room temperature. Nature, 1994, 369: 40-42 CrossRef ADS Google Scholar

[11] Paun G, Rozenberg G, Salomaa A. DNA Computing: New Computing Paradigms. Berlin: Springer, 2005. Google Scholar

[12] Amos M. Theoretical and experimental DNA computation. Bull European Assoc Theor Comput Sci, 1999, 67: 125--138. Google Scholar

[13] von Neumann J. First draft of a report on the EDVAC. IEEE Ann Hist Comput, 1993, 15: 27-75 CrossRef Google Scholar

[14] Backus J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs. Commun ACM, 1978, 21: 613-641 CrossRef Google Scholar

[15] Deaton R, Murphy R C, Rose J A, et al. A DNA based implementation of an evolutionary search for good encodings for DNA computation. In: Proceedings of IEEE International Conference on Evolutionary Computation, Indianapolis, 1997. 267--271. Google Scholar

[16] Tagore S, Bhattacharya S, Islam M, et al. DNA computation: application and perspectives. J Proteom Bioinform, 2010, 3: 234--343. Google Scholar

[17] Extance A. How DNA could store all the world's data.. Nature, 2016, 537: 22-24 CrossRef PubMed ADS Google Scholar

[18] Hameed K. DNA computation based approach for enhanced computing power. Int J Emerg Sci, 2011, 1: 23--30. Google Scholar

[19] Saxena S. Introduction to DNA computing. Int Acadmey Eng Medical Res, 2016, 1: 1--3. Google Scholar

[20] Kumar S N. A proper approach on DNA based computer. American Nanomater, 2015, 3: 1--14. Google Scholar

[21] Ma S, Tang N, Tian J. DNA synthesis, assembly and applications in synthetic biology.. Curr Opin Chem Biol, 2012, 16: 260-267 CrossRef PubMed Google Scholar

[22] Bornholt J, Lopez R, Carmean D M. A DNA-Based Archival Storage System. SIGOPS Oper Syst Rev, 2016, 50: 637-649 CrossRef Google Scholar

[23] Hughes R A, Ellington A D. Synthetic DNA Synthesis and Assembly: Putting the Synthetic in Synthetic Biology.. Cold Spring Harb Perspect Biol, 2017, 9: a023812 CrossRef PubMed Google Scholar

[24] Benenson Y, Gil B, Ben-Dor U. An autonomous molecular computer for logical control of gene expression. Nature, 2004, 429: 423-429 CrossRef PubMed ADS Google Scholar

[25] Landweber L F, Lipton R J, Rabin M O. DNA(^mbox2)DNA computations: a potential “killer app"? DNA Based Computers, Proceedings of a DIMACS Workshop, Philadelphia, 1997. 161--172. Google Scholar

[26] Watada J, binti abu Bakar R. DNA computing and its applications. In: Proceedings of the 8th International Conference on Intelligent Systems Design and Applications, Kaohsiung, 2008. 288--294. Google Scholar

[27] Gehani A, LaBean T, Reif J. DNA-based cryptography. Asp Mol Comput, 2003, 2950: 167--188. Google Scholar

[28] Miyamoto T, Razavi S, DeRose R, et al. Synthesizing biomolecule-based Boolean logic gates. ACS Synth Biol, 2012, 2: 72--82. Google Scholar

[29] Jiang H, Riedel M D, Parhi K K. Digital logic with molecular reactions. In: Proceedings of International Conference on Computer-Aided Design (ICCAD), San Jose, 2013. 721--727. Google Scholar

[30] Zhang C, Ge L L, Zhong Z W, et al. Karnaugh map-aided combinational logic design approach with bistable molecular reactions. In: Proceedings of IEEE International Conference on Digital Signal Processing (DSP), Singapore, 2015. 1288--1292. Google Scholar

[31] Ge L, Zhong Z, Wen D. A Formal Combinational Logic Synthesis With Chemical Reaction Networks. IEEE Trans Mol Biol Multi-Scale Commun, 2017, 3: 33-47 CrossRef Google Scholar

[32] Wen D L, Ge L L, Lu Y X, et al. A DNA strand displacement reaction implementation-friendly clock design. In: Proceedings of IEEE International Conference on Communications (ICC), Paris, 2017. 1--6. Google Scholar

[33] Zhang X C, Ge L L, You X H, et al. Synthesizing LDPC belief propagation decoding with molecular reactions. In: Proceedings of IEEE International Conference on Communications (ICC), Kansas City, 2018. 1--6. Google Scholar

[34] Zhong Z W, Li Z, Ge L L, et al. Implementation of Mealy machine with molecular reactions. In: Proceedings of IEEE International Conference on Communications (ICC), Kansas City, 2018. 1--6. Google Scholar

[35] Lu Y X, Ge L L, You X H, et al. Implementation of sinusoids and pulse width modulation with chemical reactions. In: Proceedings of IEEE International Conference on Communications (ICC), Kansas City, 2018. 1--6. Google Scholar

[36] Li M H, Ge L L, You X H, et al. Basic arithmetics based on analog signal with molecular reactions. In: Proceedings of IEEE International Conference on Communications (ICC), Kansas City, 2018. 1--6. Google Scholar

[37] Shen Z, Ge L, Wei W. Molecular Synthesis for Probability Theory and Stochastic Process. J Sign Process Syst, 2018, 90: 1479-1494 CrossRef Google Scholar

[38] Fang C, Shen Z, Zhang Z, et al. Synthesizing a neuron using chemical reactions. In: Proceedings of IEEE International Workshop on Signal Processing Systems (SiPS), 2018. 1--6. Google Scholar

[39] Zhuang Y, Zhang Z, You X, et al. Arithmetic computations based on chemical reaction networks. In: Proceedings of IEEE International Workshop on Signal Processing Systems (SiPS), 2018. 1--6. Google Scholar

[40] Zhong Z, Ge L, Shen Z, et al. CRN-based design methodology for synchronous sequential logic. In: Proceedings of IEEE International Workshop on Signal Processing Systems (SiPS), 2017. 1--6. Google Scholar

[41] Shen Z Y, Ge L L, Wei W, et al. Synthesizing Markov chain with reversible unimolecular reactions. In: Proceedings of International Conference on Wireless Communications and Signal Processing (WCSP), Nanjing, 2017. 1--6. Google Scholar

[42] Zhuang Y C, Ge L L, Wei W, et al. A synthesis flow for fast convolution unit based on molecular reactions. In: Proceedings of International Conference on Wireless Communications and Signal Processing (WCSP), Nanjing, 2017. 1--6. Google Scholar

[43] Shen Z, Zhang C, Ge L, et al. Synthesis of probability theory based on molecular computation. In: Proceedings of IEEE International Workshop on Signal Processing Systems (SiPS), 2016. 1--6. Google Scholar

[44] Ge L, Zhang C, Zhong Z, et al. A formal design methodology for synthesizing a clock signal with an arbitrary duty cycle of M/N. In: Proceedings of IEEE International Workshop on Signal Processing Systems (SiPS), 2015. 1--6. Google Scholar

[45] Jiang H, Riedel M D, Parhi K K. Synchronous sequential computation with molecular reactions. In: Proceedings of the 48th Design Automation Conference (DAC), San Diego, 2011. 836--841. Google Scholar

[46] Salehi S A, Riedel M D, Parhi K K. Asynchronous discrete-time signal processing with molecular reactions. In: Proceedings of the 48th Asilomar Conference on Signals, Systems and Computers, 2014. Google Scholar

[47] Rate-Independent Constructs for Chemical Computation. PLoS ONE, 2011, 6: e21414 CrossRef PubMed ADS Google Scholar

[48] Howard P. Analysis of ode models. 2009. Google Scholar

[49] Strogatz S H. Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering. Boulder: Westview Press, 2014. Google Scholar

[50] Zauderer E. Partial Differential Equations of Applied Mathematics. Hoboken: John Wiley & Sons, 2011. Google Scholar

[51] Hale J K, Lunel S M V. Introduction to Functional Differential Equations. Berlin: Springer, 2013. Google Scholar

[52] Érdi P, Tóth J. Mathematical models of chemical reactions: theory and applications of deterministic and stochastic models. Manchester: Manchester University Press, 1989. Google Scholar

[53] Horn F, Jackson R. General mass action kinetics. Arch Rational Mech Anal, 1972, 47: 81-116 CrossRef ADS Google Scholar

[54] Crick F. Central Dogma of Molecular Biology. Nature, 1970, 227: 561-563 CrossRef ADS Google Scholar

[55] Soloveichik D, Seelig G, Winfree E. DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci USA, 2010, 107: 5393-5398 CrossRef PubMed ADS Google Scholar

[56] Zhang D Y, Seelig G. Dynamic DNA nanotechnology using strand-displacement reactions. Nat Chem, 2011, 3: 103-113 CrossRef PubMed ADS Google Scholar

[57] Zhang D Y, Winfree E. Control of DNA strand displacement kinetics using toehold exchange. J Am Chem Soc, 2009, 131: 303--314. Google Scholar

[58] Phillips A, Cardelli L. A programming language for composable DNA circuits.. J R Soc Interface, 2009, 6: S419-S436 CrossRef PubMed Google Scholar

[59] SantaLucia Jr. J, Hicks D. The Thermodynamics of DNA Structural Motifs. Annu Rev Biophys Biomol Struct, 2004, 33: 415-440 CrossRef Google Scholar

[60] Shapiro E, Ran T. DNA computing: Molecules reach consensus. Nat Nanotech, 2013, 8: 703-705 CrossRef PubMed ADS Google Scholar

[61] Zhang D Y. Dynamic DNA strand displacement circuits. Dissertation for Ph.D. Degree. Pasadena: California Institute of Technology, 2010. Google Scholar

[62] Leavitt S. Deciphering the genetic code: Marshall Nirenberg. Office of NIH History, 2004. Google Scholar

[63] Sarpeshkar R. Analog Versus Digital: Extrapolating from Electronics to Neurobiology. Neural Computation, 1998, 10: 1601-1638 CrossRef Google Scholar

[64] Sauro H M, Kim K. Synthetic biology: It's an analog world. Nature, 2013, 497: 572-573 CrossRef PubMed ADS Google Scholar

[65] Song T, Garg S, Mokhtar R. Analog Computation by DNA Strand Displacement Circuits.. ACS Synth Biol, 2016, 5: 898-912 CrossRef PubMed Google Scholar

[66] Yordanov B, Kim J, Petersen R L. Computational design of nucleic acid feedback control circuits.. ACS Synth Biol, 2014, 3: 600-616 CrossRef PubMed Google Scholar

[67] Chen Y J, Dalchau N, Srinivas N. Programmable chemical controllers made from DNA. Nat Nanotech, 2013, 8: 755-762 CrossRef PubMed ADS Google Scholar

[68] Daniel R, Rubens J R, Sarpeshkar R. Synthetic analog computation in living cells. Nature, 2013, 497: 619-623 CrossRef PubMed ADS Google Scholar

[69] Sarpeshkar R. Analog synthetic biology. Philos Trans R Soc A-Math Phys Eng Sci, 2014, 372: 20130110-20130110 CrossRef PubMed ADS Google Scholar

[70] Salehi S A, Jiang H, Riedel M D. Molecular Sensing and Computing Systems. IEEE Trans Mol Biol Multi-Scale Commun, 2015, 1: 249-264 CrossRef Google Scholar

[71] Frezza B M, Cockroft S L, Ghadiri M R. Modular multi-level circuits from immobilized DNA-based logic gates. J Am Chem Soc, 2007, 129: 875--879. Google Scholar

[72] Chiniforooshan E, Doty D, Kari L, et al. Scalable, time-responsive, digital, energy-efficient molecular circuits using DNA strand displacement. DNA, 2010, 16: 25--36. Google Scholar

[73] Qian L, Winfree E. Scaling Up Digital Circuit Computation with DNA Strand Displacement Cascades. Science, 2011, 332: 1196-1201 CrossRef PubMed ADS Google Scholar

[74] Nielsen A A K, Der B S, Shin J. Genetic circuit design automation.. Science, 2016, 352: aac7341-aac7341 CrossRef PubMed Google Scholar

[75] Roquet N, Lu T K. Digital and analog gene circuits for biotechnology.. Biotech J, 2014, 9: 597-608 CrossRef PubMed Google Scholar

[76] Weiss R. Genetic circuit building blocks for cellular computation, communications, and signal processing. Nat Computing, 2003, 2: 47-84 CrossRef Google Scholar

[77] Zadegan R M, Jepsen M D E, Hildebrandt L L. Construction of a fuzzy and Boolean logic gates based on DNA.. Small, 2015, 11: 1811-1817 CrossRef PubMed Google Scholar

[78] Zhang Y, Wirkert S J, Iszatt J. Tissue classification for laparoscopic image understanding based on multispectral texture analysis.. J Med Imag, 2017, 4: 015001 CrossRef PubMed Google Scholar

[79] Lu C H, Willner B, Willner I. DNA nanotechnology: from sensing and DNA machines to drug-delivery systems.. ACS Nano, 2013, 7: 8320-8332 CrossRef PubMed Google Scholar

[80] Li J, Pei H, Zhu B. Self-assembled multivalent DNA nanostructures for noninvasive intracellular delivery of immunostimulatory CpG oligonucleotides.. ACS Nano, 2011, 5: 8783-8789 CrossRef PubMed Google Scholar

[81] Qian L, Winfree E, Bruck J. Neural network computation with DNA strand displacement cascades.. Nature, 2011, 475: 368-372 CrossRef PubMed Google Scholar

[82] Schneider G, Wrede P. Artificial neural networks for computer-based molecular design. Prog Biophys Mol Biol, 1998, 70: 175-222 CrossRef Google Scholar

[83] Noordewier M O, Towell G G, Shavlik J W. Training knowledge-based neural networks to recognize genes in DNA sequences. Advances in neural information processing systems 1991. 530--536. Google Scholar

[84] Zuber J, Sun H, Zhang X, et al. A sensitivity analysis of RNA folding nearest neighbor parameters identifies a subset of free energy parameters with the greatest impact on RNA secondary structure prediction. Nucleic acids research, 2017 45: 6168--6176. Google Scholar

[85] Brady M. Artificial intelligence and robotics. Artificial Intelligence, 1985, 26: 79-121 CrossRef Google Scholar

[86] Ray K S, Mondal M. Similarity-based fuzzy reasoning by DNA computing. IJBIC, 2011, 3: 112-122 CrossRef Google Scholar

[87] Jeng D J, Watada J, Wu B, et al. Fuzzy forecasting with DNA computing. In: Proceedings of International Workshop on DNA-Based Computers. Berlin: Springer, 2006. 324--336. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号