Document Open Access Logo

Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks

Authors Robert F. Johnson , Lulu Qian

PDF
Thumbnail PDF

File

LIPIcs.DNA.2020.2.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Robert F. Johnson
  • California Institute of Technology, Pasadena, CA, USA
Lulu Qian
  • California Institute of Technology, Pasadena, CA, USA

Funding

  • Johnson, Robert F.: NSF Graduate Research Fellowship.
  • Qian, Lulu: NSF grant CCF-1908643.

Acknowledgements

We would like to thank Chris Thachuk and Erik Winfree for helpful discussions on new DNA strand displacement motifs and optimization thereof.

Cite AsGet BibTex

Robert F. Johnson and Lulu Qian. Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DNA.2020.2

Abstract

In molecular programming, the Chemical Reaction Network model is often used to describe real or hypothetical systems. Often, an interesting computational task can be done with a known hypothetical Chemical Reaction Network, but often such networks have no known physical implementation. One of the important breakthroughs in the field was that any Chemical Reaction Network can be physically implemented, approximately, using DNA strand displacement mechanisms. This allows us to treat the Chemical Reaction Network model as a programming language and the implementation schemes as its compiler. This also suggests that it would be useful to optimize the result of such a compilation, and in general to find effective ways to design better DNA strand displacement systems. We discuss DNA strand displacement systems in terms of "motifs", short sequences of elementary DNA strand displacement reactions. We argue that describing such motifs in terms of their inputs and outputs, then building larger systems out of the abstracted motifs, can be an efficient way of designing DNA strand displacement systems. We discuss four previously studied motifs in this abstracted way, and present a new motif based on cooperative 4-way strand exchange. We then show how Chemical Reaction Network implementations can be built out of abstracted motifs, discussing existing implementations as well as presenting two new implementations based on 4-way strand exchange, one of which uses the new cooperative motif. The new implementations both have two desirable properties not found in existing implementations, namely both use only at most 2-stranded DNA complexes for signal and fuel complexes and both are physically reversible. There are reasons to believe that those properties may make them more robust and energy-efficient, but at the expense of using more fuel complexes than existing implementation schemes.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Molecular computing
Keywords
  • Molecular programming
  • DNA computing
  • Chemical Reaction Networks
  • DNA strand displacement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nathanaël Aubert, Clément Mosca, Teruo Fujii, Masami Hagiya, and Yannick Rondelez. Computer-assisted design for scaling up systems based on DNA reaction networks. Journal of The Royal Society Interface, 11(93):20131167, 2014. Google Scholar
  2. Charles H Bennett. Logical reversibility of computation. IBM journal of Research and Development, 17(6):525-532, 1973. Google Scholar
  3. Charles H Bennett. The thermodynamics of computation—a review. International Journal of Theoretical Physics, 21(12):905-940, 1982. Google Scholar
  4. Luca Cardelli. Two-domain DNA strand displacement. Mathematical Structures in Computer Science, 23(02):247-271, 2013. Google Scholar
  5. Sherry Xi Chen, David Yu Zhang, and Georg Seelig. Conditionally fluorescent molecular probes for detecting single base changes in double-stranded DNA. Nature Chemistry, 5(9):782, 2013. Google Scholar
  6. Xi Chen. Expanding the rule set of DNA circuitry with associative toehold activation. Journal of the American Chemical Society, 134(1):263-271, 2012. Google Scholar
  7. Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from DNA. Nature Nanotechnology, 8(10):755-762, 2013. Google Scholar
  8. Kevin M Cherry and Lulu Qian. Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks. Nature, 559(7714):370, 2018. Google Scholar
  9. Anne Condon, Alan J Hu, Ján Maňuch, and Chris Thachuk. Less haste, less waste: on recycling and its limits in strand displacement systems. Interface Focus, 2(4):512-521, 2012. Google Scholar
  10. Nadine L Dabby. Synthetic molecular machines for active self-assembly: prototype algorithms, designs, and experimental study. PhD thesis, California Institute of Technology, February 2013. Google Scholar
  11. Robert M Dirks and Niles A Pierce. Triggered amplification by hybridization chain reaction. Proceedings of the National Academy of Sciences, 101(43):15275-15278, 2004. Google Scholar
  12. Abeer Eshra, Shalin Shah, Tianqi Song, and John Reif. Renewable DNA hairpin-based logic circuits. IEEE Transactions on Nanotechnology, 18:252-259, 2019. Google Scholar
  13. Sudhanshu Garg, Shalin Shah, Hieu Bui, Tianqi Song, Reem Mokhtar, and John Reif. Renewable time-responsive DNA circuits. Small, 14(33):1801470, 2018. Google Scholar
  14. Anthony J Genot, Jonathan Bath, and Andrew J Turberfield. Reversible logic circuits made of DNA. Journal of the American Chemical Society, 133(50):20080-20083, 2011. Google Scholar
  15. Anthony J Genot, David Yu Zhang, Jonathan Bath, and Andrew J Turberfield. Remote toehold: a mechanism for flexible control of DNA hybridization kinetics. Journal of the American Chemical Society, 133(7):2177-2182, 2011. Google Scholar
  16. Benjamin Groves, Yuan-Jyue Chen, Chiara Zurla, Sergii Pochekailov, Jonathan L Kirschman, Philip J Santangelo, and Georg Seelig. Computing in mammalian cells with nucleic acid strand exchange. Nature Nanotechnology, 11(3):287, 2016. Google Scholar
  17. Casey Grun, Karthik Sarma, Brian Wolfe, Seung Woo Shin, and Erik Winfree. A domain-level DNA strand displacement reaction enumerator allowing arbitrary non-pseudoknotted secondary structures. CoRR, 2015. URL: http://arxiv.org/abs/1505.03738,
  18. Robert F. Johnson. Impossibility of sufficiently simple chemical reaction network implementations in DNA strand displacement. In Ian McQuillan and Shinnosuke Seki, editors, Unconventional Computation and Natural Computation, pages 136-149. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-19311-9_12.
  19. Robert F Johnson, Qing Dong, and Erik Winfree. Verifying chemical reaction network implementations: A bisimulation approach. Theoretical Computer Science, 2018. URL: https://doi.org/10.1016/j.tcs.2018.01.002.
  20. Jongmin Kim, John Hopfield, and Erik Winfree. Neural network computation by in vitro transcriptional circuits. In Advances in Neural Information Processing systems, pages 681-688, 2005. Google Scholar
  21. Jongmin Kim and Erik Winfree. Synthetic in vitro transcriptional oscillators. Molecular Systems Biology, 7(1):465, 2011. Google Scholar
  22. Jocelyn Y Kishi, Thomas E Schaus, Nikhil Gopalkrishnan, Feng Xuan, and Peng Yin. Programmable autonomous synthesis of single-stranded DNA. Nature Chemistry, 10(2):155, 2018. Google Scholar
  23. Kevin Montagne, Raphael Plasson, Yasuyuki Sakai, Teruo Fujii, and Yannick Rondelez. Programming an in vitro DNA oscillator using a molecular networking strategy. Molecular Systems Biology, 7(1):466, 2011. Google Scholar
  24. Richard A Muscat, Jonathan Bath, and Andrew J Turberfield. A programmable molecular robot. Nano letters, 11(3):982-987, 2011. Google Scholar
  25. Igor G Panyutin and Peggy Hsieh. The kinetics of spontaneous DNA branch migration. Proceedings of the National Academy of Sciences, 91(6):2021-2025, 1994. Google Scholar
  26. Tomislav Plesa. Stochastic approximation of high-molecular by bi-molecular reactions. arXiv preprint arXiv:1811.02766, 2018. Google Scholar
  27. Lulu Qian, David Soloveichik, and Erik Winfree. Efficient Turing-universal computation with DNA polymers. In Yasubumi Sakakibara and Yongli Mi, editors, DNA Computing and Molecular Programming, volume 6518 of Lecture Notes in Computer Science, pages 123-140. Springer, 2011. Google Scholar
  28. Lulu Qian and Erik Winfree. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 332(6034):1196-1201, 2011. Google Scholar
  29. Dominic Scalise, Nisita Dutta, and Rebecca Schulman. DNA strand buffers. Journal of the American Chemical Society, 140(38):12069-12076, 2018. Google Scholar
  30. Dominic Scalise and Rebecca Schulman. Designing modular reaction-diffusion programs for complex pattern formation. Technology, 2(01):55-66, 2014. Google Scholar
  31. Dominic Scalise and Rebecca Schulman. Emulating cellular automata in chemical reaction-diffusion networks. Natural Computing, 15(2):197-214, 2016. Google Scholar
  32. Shalin Shah, Tianqi Song, Xin Song, Ming Yang, and John Reif. Implementing arbitrary CRNs using strand displacing polymerase. In International Conference on DNA Computing and Molecular Programming, pages 21-36. Springer, 2019. Google Scholar
  33. Shalin Shah, Jasmine Wee, Tianqi Song, Luis Ceze, Karin Strauss, Yuan-Jyue Chen, and John Reif. Using strand displacing polymerase to program chemical reaction networks. Journal of the American Chemical Society, 2020. Google Scholar
  34. David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences, 107(12):5393-5398, 2010. Google Scholar
  35. Tianqi Song, Abeer Eshra, Shalin Shah, Hieu Bui, Daniel Fu, Ming Yang, Reem Mokhtar, and John Reif. Fast and compact DNA logic circuits based on single-stranded gates using strand-displacing polymerase. Nature Nanotechnology, 14(11):1075-1081, 2019. Google Scholar
  36. Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, and David Soloveichik. Enzyme-free nucleic acid dynamical systems. Science, 358:doi:10.1126/science.aal2052, 2017. Google Scholar
  37. Chris Thachuk and Anne Condon. Space and energy efficient computation with DNA strand displacement systems. In International Workshop on DNA-Based Computers, pages 135-149. Springer, 2012. Google Scholar
  38. Chris Thachuk and Erik Winfree. A fast, robust, and reconfigurable molecular circuit breadboard. 15th Annual Conference on Foundations of Nanoscience, invited talk, 2018. URL: https://thachuk.com/talk/2018-fnano-invited/2018-FNANO-invited.pdf.
  39. Chris Thachuk, Erik Winfree, and David Soloveichik. Leakless DNA strand displacement systems. In Andrew Phillips and Peng Yin, editors, DNA Computing and Molecular Programming, volume 9211 of Lecture Notes in Computer Science, pages 133-153. Springer, 2015. Google Scholar
  40. Anupama J Thubagere, Chris Thachuk, Joseph Berleant, Robert F Johnson, Diana A Ardelean, Kevin M Cherry, and Lulu Qian. Compiler-aided systematic construction of large-scale DNA strand displacement circuits using unpurified components. Nature Communications, 8:14373, 2017. Google Scholar
  41. Suvir Venkataraman, Robert M Dirks, Paul WK Rothemund, Erik Winfree, and Niles A Pierce. An autonomous polymerization motor powered by DNA hybridization. Nature Nanotechnology, 2(8):490, 2007. Google Scholar
  42. Boya Wang, Chris Thachuk, Andrew D Ellington, Erik Winfree, and David Soloveichik. Effective design principles for leakless strand displacement systems. Proceedings of the National Academy of Sciences, 115(52):E12182-E12191, 2018. Google Scholar
  43. Xiaolong Yang, Yanan Tang, Sarah M Traynor, and Feng Li. Regulation of DNA strand displacement using an allosteric DNA toehold. Journal of the American Chemical Society, 138(42):14076-14082, 2016. Google Scholar
  44. Peng Yin, Harry MT Choi, Colby R Calvert, and Niles A Pierce. Programming biomolecular self-assembly pathways. Nature, 451(7176):318-322, 2008. Google Scholar
  45. Bernard Yurke and Allen P Mills. Using DNA to power nanostructures. Genetic Programming and Evolvable Machines, 4(2):111-122, 2003. Google Scholar
  46. David Yu Zhang. Cooperative hybridization of oligonucleotides. Journal of the American Chemical Society, 133(4):1077-1086, 2010. Google Scholar
  47. David Yu Zhang and Georg Seelig. Dynamic DNA nanotechnology using strand-displacement reactions. Nature Chemistry, 3(2):103-113, 2011. Google Scholar
  48. David Yu Zhang and Erik Winfree. Control of DNA strand displacement kinetics using toehold exchange. Journal of the American Chemical Society, 131(47):17303-17314, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact