Document Open Access Logo

A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems

Authors Hope Amber Johnson , Anne Condon

PDF
Thumbnail PDF

File

LIPIcs.DNA.28.3.pdf
  • Filesize: 0.79 MB
  • 19 pages

Document Identifiers

Author Details

Hope Amber Johnson
  • The University of British Columbia, Vancouver, Canada
Anne Condon
  • The University of British Columbia, Vancouver, Canada

Funding

  • Johnson, Hope Amber: Supported by an NSERC Discovery Grant.
  • Condon, Anne: Supported by an NSERC Discovery Grant.

Cite AsGet BibTex

Hope Amber Johnson and Anne Condon. A Coupled Reconfiguration Mechanism for Single-Stranded DNA Strand Displacement Systems. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DNA.28.3

Abstract

DNA Strand Displacement (DSD) systems model basic reaction rules, such as toehold-mediated strand displacement and 4-way branch migration, that modify complexes of bound DNA strands. DSD systems have been widely used to design and reason about the correctness of molecular programs, including implementations of logic circuits, neural networks, and Chemical Reaction Networks. Such implementations employ a valuable toolkit of mechanisms - sequences of basic reaction rules - that achieve catalysis, reduce errors (e.g., due to leak), or simulate simple computational units such as logic gates, both in solution and on surfaces. Expanding the DSD toolkit of DSD mechanisms can lead to new and better ways of programming with DNA. Here we introduce a new mechanism, which we call controlled reconfiguration. We describe one example where two single-stranded DSD complexes interact, changing the bonds in both complexes in a way that would not be possible for each independently on its own via the basic reaction rules allowed by the model. We use coupled reconfiguration to refer to instances of controlled reconfiguration in which two reactants change each other in this way. We note that our DSD model disallows pseudoknots and that properties of our coupled reconfiguration construction rely on this restriction of the model. A key feature of our coupled reconfiguration example, which distinguishes it from mechanisms (such as 3-way strand displacement or 4-way branch migration) that are typically used to implement molecular programs, is that the reactants are single-stranded. Leveraging this feature, we show how to use coupled reconfiguration to implement Chemical Reaction Networks (CRNs), with a DSD system that has both single-stranded signals (which represent the species of the CRN) and single-stranded fuels (which drive the CRN reactions). Our implementation also has other desirable properties; for example it is capable of implementing reversible CRNs and uses just two distinct toeholds. We discuss drawbacks of our implementation, particularly the reliance on pseudoknot-freeness for correctness, and suggest directions for future research that can provide further insight on the capabilities and limitations of controlled reconfiguration.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Applied computing → Chemistry
Keywords
  • Molecular programming
  • DNA Strand Displacement
  • Chemical Reaction Networks

Metrics

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

References

  1. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, pages 235-253, March 2006. URL: https://doi.org/10.1007/s00446-005-0138-3.
  2. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292-299. ACM, 2006. URL: https://doi.org/10.1145/1146381.1146425.
  3. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21:87-102, 2008. URL: https://doi.org/10.1007/s00446-008-0059-z.
  4. Stefan Badelt, Casey Grun, Karthik V Sarma, Brian Wolfe, Seung Woo Shin, and Erik Winfree. A domain-level DNA strand displacement reaction enumerator allowing arbitrary non-pseudoknotted secondary structures. Journal of the Royal Society Interface, 17(167):20190866, 2020. URL: https://doi.org/10.1098/rsif.2019.0866.
  5. Stefan Badelt, Seung Woo Shin, Robert F Johnson, Qing Dong, Chris Thachuk, and Erik Winfree. A general-purpose CRN-to-DSD compiler with formal verification, optimization, and simulation capabilities. In Damien Woods and Yannick Rondelez, editors, DNA Computing and Molecular Programming, volume 9818 of Lecture Notes in Computer Science, pages 232-248. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-66799-7_15.
  6. Daniele Cappelletti, Andrés Ortiz-Muñoz, David F. Anderson, and Erik Winfree. Stochastic chemical reaction networks for robustly approximating arbitrary probability distributions. Theoretical Computer Science, 801:64-95, 2020. URL: https://doi.org/10.1016/j.tcs.2019.08.013.
  7. Luca Cardelli. Two-domain DNA strand displacement. Mathematical Structures in Computer Science, 23(02):247-271, 2013. URL: https://doi.org/10.1017/S0960129512000102.
  8. Luca Cardelli and Gianluigi Zavattaro. On the computational power of biochemistry. In International Conference on Algebraic Biology, pages 65-80. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85101-1_6.
  9. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517-534, 2014. URL: https://doi.org/10.1007/s11047-013-9393-6.
  10. 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. URL: https://doi.org/10.1038/nnano.2013.189.
  11. Kevin M Cherry and Lulu Qian. Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks. Nature, 559(7714):370, 2018. URL: https://doi.org/10.1038/s41586-018-0289-6.
  12. Samuel Clamons, Lulu Qian, and Erik Winfree. Programming and simulating chemical reaction networks on a surface. Journal of the Royal Society Interface, 17(166):20190790, 2020. URL: https://doi.org/10.1098/rsif.2019.0790.
  13. Swarup Dey, Chunhai Fan, Kurt V Gothelf, Jiang Li, Chenxiang Lin, Longfei Liu, Na Liu, Minke AD Nijenhuis, Barbara Saccà, Friedrich C Simmel, Hao Yan, and Pengfei Zhan. DNA origami. Nature Reviews Methods Primers, 1(1):1-24, 2021. URL: https://doi.org/10.1038/s43586-020-00009-8.
  14. Robert M Dirks, Justin S Bois, Joseph M Schaeffer, Erik Winfree, and Niles A Pierce. Thermodynamic analysis of interacting nucleic acid strands. SIAM review, 49(1):65-88, 2007. URL: https://doi.org/10.1137/060651100.
  15. Robert M Dirks and Niles A Pierce. A partition function algorithm for nucleic acid secondary structure including pseudoknots. Journal of computational chemistry, 24(13):1664-1677, 2003. URL: https://doi.org/10.1002/jcc.10296.
  16. 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. URL: https://doi.org/10.1073/pnas.0407024101.
  17. David Doty and Monir Hajiaghayi. Leaderless deterministic chemical reaction networks. In David Soloveichik and Bernard Yurke, editors, DNA 2013: Proceedings of The 19th International Meeting on DNA Computing and Molecular Programming, volume 8141 of Lecture Notes in Computer Science, pages 46-60. Springer International Publishing, 2013. URL: https://doi.org/10.1007/978-3-319-01928-4_4.
  18. Constantine G Evans, Rizal F Hariadi, and Erik Winfree. Direct atomic force microscopy observation of DNA tile crystal growth at the single-molecule level. Journal of the American Chemical Society, 134(25):10485-10492, 2012. URL: https://doi.org/10.1021/ja301026z.
  19. Cody Geary, Guido Grossi, Ewan KS McRae, Paul WK Rothemund, and Ebbe S Andersen. RNA origami design tools enable cotranscriptional folding of kilobase-sized nanoscaffolds. Nature chemistry, 13(6):549-558, 2021. URL: https://doi.org/10.1038/s41557-021-00679-1.
  20. 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. URL: https://doi.org/10.1021/ja1073239.
  21. 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.
  22. 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.
  23. Robert F. Johnson and Lulu Qian. Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks. In Cody Geary and Matthew J. Patitz, editors, 26th International Conference on DNA Computing and Molecular Programming (DNA 26), volume 174 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DNA.2020.2.
  24. Robert F Johnson and Erik Winfree. Verifying polymer reaction networks using bisimulation. Theoretical Computer Science, 843:84-114, 2020. URL: https://doi.org/10.1016/j.tcs.2020.08.007.
  25. Matthew R. Lakin and Andrew Phillips. Modelling, simulating and verifying Turing-powerful strand displacement systems. In Luca Cardelli and William Shih, editors, DNA Computing and Molecular Programming, pages 130-144, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-23638-9_12.
  26. Matthew R. Lakin, Simon Youssef, Filippo Polo, Stephen Emmott, and Andrew Phillips. Visual DSD: a design and analysis tool for DNA strand displacement systems. Bioinformatics, 27(22):3211-3213, 2011. URL: https://doi.org/10.1093/bioinformatics/btr543.
  27. Jérôme Leroux. Vector addition systems reachability problem (a simpler solution). In EPiC, volume 10, pages 214-228. Andrei Voronkov, 2012. Google Scholar
  28. Marcelo O Magnasco. Chemical kinetics is Turing universal. Physical Review Letters, 78(6):1190-1193, 1997. URL: https://doi.org/10.1103/PhysRevLett.78.1190.
  29. Rasmus L Petersen, Matthew R Lakin, and Andrew Phillips. A strand graph semantics for DNA-based computation. Theoretical computer science, 632:43-73, 2016. URL: https://doi.org/10.1016/j.tcs.2015.07.041.
  30. 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. URL: https://doi.org/10.1007/978-3-642-18305-8_12.
  31. Lulu Qian and Erik Winfree. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 332(6034):1196-1201, 2011. URL: https://doi.org/10.1126/science.1200520.
  32. Lulu Qian and Erik Winfree. Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface. In Satoshi Murata and Satoshi Kobayashi, editors, DNA Computing and Molecular Programming, volume 8727 of Lecture Notes in Computer Science, pages 114-131. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-11295-4_8.
  33. Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6(2):223-231, 1978. URL: https://doi.org/10.1016/0304-3975(78)90036-1.
  34. Seung Woo Shin, Chris Thachuk, and Erik Winfree. Verifying chemical reaction network implementations: A pathway decomposition approach. Theoretical Computer Science, 2017. URL: https://doi.org/doi:10.1016/j.tcs.2017.10.011.
  35. Friedrich C. Simmel, Bernard Yurke, and Hari R. Singh. Principles and applications of nucleic acid strand displacement reactions. Chemical Reviews, 119(10):6326-6369, 2019. PMID: 30714375. URL: https://doi.org/10.1021/acs.chemrev.8b00580.
  36. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615-633, 2008. URL: https://doi.org/10.1007/s11047-008-9067-y.
  37. 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. URL: https://doi.org/10.1073/pnas.0909380107.
  38. Carlo Spaccasassi, Matthew R Lakin, and Andrew Phillips. A logic programming language for computational nucleic acid devices. ACS Synth. Biol., 8(7):1530-1547, July 2019. URL: https://doi.org/10.1021/acssynbio.8b00229.
  39. Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, and David Soloveichik. Enzyme-free nucleic acid dynamical systems. Science, 358, 2017. URL: https://doi.org/10.1126/science.aal2052.
  40. Allison Tai and Anne Condon. Error-free stable computation with polymer-supplemented chemical reaction networks. In Chris Thachuk and Yan Liu, editors, DNA Computing and Molecular Programming, pages 197-218, Cham, 2019. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-26807-7_11.
  41. Chris Thachuk and Anne Condon. Space and energy efficient computation with DNA strand displacement systems. In Darko Stefanovic and Andrew Turberfield, editors, DNA Computing and Molecular Programming, volume 7433 of Lecture Notes in Computer Science, pages 135-149. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32208-2_11.
  42. 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. URL: https://doi.org/10.1007/978-3-319-21999-8_9.
  43. Anupama J. Thubagere, Wei Li, Robert F. Johnson, Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, and Lulu Qian. A cargo-sorting DNA robot. Science, 357(6356), 2017. URL: https://doi.org/10.1126/science.aan6558.
  44. 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. URL: https://doi.org/10.1038/ncomms14373.
  45. Toma E Tomov, Roman Tsukanov, Yair Glick, Yaron Berger, Miran Liber, Dorit Avrahami, Doron Gerber, and Eyal Nir. DNA bipedal motor achieves a large number of steps due to operation using microfluidics-based interface. Acs Nano, 11(4):4002-4008, 2017. URL: https://doi.org/10.1021/acsnano.7b00547.
  46. F. H. van Batenburg, A. P. Gultyaev, C. W. Pleij, J. Ng, and J. Oliehoek. Pseudobase: a database with RNA pseudoknots. Nucleic acids research, 28(1):201-204, January 2000. URL: https://doi.org/10.1093/nar/28.1.201.
  47. Marko Vasic, Cameron Chalk, Austin Luchsinger, Sarfraz Khurshid, and David Soloveichik. Programming and training rate-independent chemical reaction networks, 2021. URL: http://arxiv.org/abs/2109.11422.
  48. 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. URL: https://doi.org/10.1073/pnas.1806859115.
  49. Tianbing Xia, John SantaLucia, Mark E. Burkard, Ryszard Kierzek, Susan J. Schroeder, Xiaoqi Jiao, Christopher Cox, and Douglas H. Turner. Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs. Biochemistry, 37(42):14719-14735, 1998. PMID: 9778347. URL: https://doi.org/10.1021/bi9809425.
  50. Peng Yin, Harry MT Choi, Colby R Calvert, and Niles A Pierce. Programming biomolecular self-assembly pathways. Nature, 451(7176):318-322, 2008. URL: https://doi.org/10.1038/nature06451.
  51. David Yu Zhang. Cooperative hybridization of oligonucleotides. Journal of the American Chemical Society, 133(4):1077-1086, 2010. URL: https://doi.org/10.1021/ja109089q.
  52. David Yu Zhang and Erik Winfree. Dynamic allosteric control of noncovalent DNA catalysis reactions. Journal of the American Chemical Society, 130(42):13921-13926, 2008. URL: https://doi.org/10.1021/ja803318t.
  53. 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. URL: https://doi.org/10.1021/ja906987s.
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