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


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