logo

SCIENTIA SINICA Informationis, Volume 49, Issue 7: 819-837(2019) https://doi.org/10.1360/N112019-00007

DNA computing for combinational logic

More info
  • ReceivedApr 5, 2018
  • AcceptedJul 23, 2018
  • PublishedJul 16, 2019

Abstract

With the progressive scale-down of semiconductor feature size, people are looking forward to More Moore and More than Moore. Thus, people are trying to devise a feasible transfer from silicon to molecular computing to offer a possible alternative implementation process. Such a transfer is based on bio-based module programming with computer-like logic, aimed at realizing the Turing machine. DNA-based combinational logic is inevitably the first step that we have taken to accomplish this. This timely overview paper introduces combinational logic separately synthesized in DNA computing from both analog and digital perspectives. State-of-the-art research progress is summarized herein for interested readers to quickly understand DNA computing, initiate discussion on existing techniques, and inspire innovative solutions. We hope this review paves the way for future DNA computing synthesis.


Funded by

国家自然科学基金(61871115,61501116)

江苏省自然科学优秀青年基金(BK20180059)


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. MoS$_{2}$ transistors with 1-nanometer gate lengths. Science, 2016, 354: 99-102 CrossRef PubMed ADS 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, 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-379 CrossRef PubMed 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. Synthetic biology: new engineering rules for an emerging discipline.. Mol Syst Biol, 2006, 2 CrossRef PubMed 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] Adleman L. Molecular Computation of Solutions to Combinatorial Problems. Science, 1994, 266: 1021-1024 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, 1997. 267--271. Google Scholar

[16] Tagore S, Bhattacharya S, Islam M, et al. DNA computation: application and perspectives. J Proteomics 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 Emerging 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. Am J 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?". In: Proceedings of a DIMACS Workshop on DNA Based Computers, Philadelphia, 1997. 161--172. Google Scholar

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

[27] Gehani A, LaBean T, Reif J. DNA-based cryptography. Lecture Notes Comput Sci, 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), 2013. 721--727. Google Scholar

[30] Zhang C, Ge L, Zhong Z, et al. Karnaugh map-aided combinational logic design approach with bistable molecular reactions. In: Proceedings of IEEE International Conference on Digital Signal Processing (DSP), 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, Ge L, Lu Y, et al. A DNA strand displacement reaction implementation-friendly clock design. In: Proceedings of IEEE International Conference on Communications (ICC), 2017. 1--6. Google Scholar

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

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

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

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

[37] Salehi S A, Riedel M D, Parhi K K. Molecular computation of complex Markov chains with self-loop state transitions. In: Proceedings of IEEE international conference on digital signal processing (DSP), 2015. 689--693. Google Scholar

[38] Salehi S A, Riedel M D, Parhi K K. Molecular computation of complex Markov chains with self-loop state transitions. In: Proceedings of the 51st Asilomar Conference on Signals, Systems, and Computers, 2017. 478--483. Google Scholar

[39] 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

[40] 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

[41] Salehi S A, Liu X, Riedel M D, Parhi K K. Computing mathematical functions using DNA via fractional coding. 2018, 1: 8321. Google Scholar

[42] 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

[43] 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

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

[45] Zhuang Y, Ge L, Shen Z, 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), 2017. 1--6. Google Scholar

[46] 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

[47] 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

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

[49] 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

[50] Senum P, Riedel M D. Rate-independent constructs for chemical computation. PLoS ONE, 2011, 6: e21414. Google Scholar

[51] É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

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

[53] Howard P. Analysis of ODE models. 2009. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.4759&rep=rep1&type=pdf. Google Scholar

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

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

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

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

[58] 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

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

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

[61] Phillips A, Cardelli L. A programming language for composable DNA circuits. J Royal Soc Inter, 2009, 6: S419--S436. Google Scholar

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

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

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

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

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

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

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

[69] 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

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

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

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

[73] 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

[74] 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

[75] 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

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

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

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

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

[80] 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

[81] 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

[82] 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

[83] 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

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

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

[86] Noordewier M O, Towell G G, Shavlik J W. Training knowledge-based neural networks to recognize genes in DNA sequences. In: Proceedings of the 1990 Conference on Advances in Neural Information Processing Systems, 1990. 530--536. Google Scholar

[87] Zuber J, Sun H, Zhang X. 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 Res, 2017, 45: 6168-6176 CrossRef PubMed Google Scholar

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

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

[90] 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 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1