A Caltech Library Service

Impossibility of Sufficiently Simple Chemical Reaction Network Implementations in DNA Strand Displacement

Johnson, Robert F. (2019) Impossibility of Sufficiently Simple Chemical Reaction Network Implementations in DNA Strand Displacement. In: Unconventional Computation and Natural Computation. Lecture Notes in Computer Science. No.11493. Springer , Cham, pp. 136-149. ISBN 978-3-030-19310-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


DNA strand displacement (DSD) has recently become a common technology for constructing molecular devices, with a number of useful systems experimentally demonstrated. To help with DSD system design, various researchers are developing formal definitions to model DNA strand displacement systems. With these models a DSD system can be defined, described by a Chemical Reaction Network, simulated, and otherwise analyzed. Meanwhile, the research community is trying to use DSD to do increasingly complex tasks, while also trying to make DSD systems simpler and more robust. I suggest that formal modeling of DSD systems can be used not only to analyze DSD systems, but to guide their design. For instance, one might prove that a DSD system that implements a certain function must use a certain mechanism. As an example, I show that a physically reversible DSD system with no pseudoknots, no effectively trimolecular reactions, and using 4-way but not 3-way branch migration, cannot be a systematic implementation of reactions of the form A⇌B that uses a constant number of toehold domains and does not crosstalk when multiple reactions of that type are combined. This result is a tight lower bound in the sense that, for most of those conditions, removing just that one condition makes the desired DSD system possible. I conjecture that a system with the same restrictions using both 3-way and 4-way branch migration still cannot systematically implement the reaction A+B⇌C.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Johnson, Robert F.0000-0002-5340-8347
Additional Information:© 2019 Springer Nature Switzerland AG. First Online: 26 April 2019. I thank Chris Thachuk, Stefan Badelt, Erik Winfree, and Lulu Qian for helpful discussions on formal verification and on two-stranded DSD systems. I also thank the anonymous reviewers of a rejected previous version of this paper for their suggestions, many of which appear in this version. I thank the NSF Graduate Research Fellowship Program for financial support.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Series Name:Lecture Notes in Computer Science
Issue or Number:11493
Record Number:CaltechAUTHORS:20200903-092531091
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105233
Deposited By: Tony Diaz
Deposited On:08 Sep 2020 23:23
Last Modified:16 Nov 2021 18:41

Repository Staff Only: item control page