Abstract
Chemical reaction networks (CRNs) and DNA strand displacement systems (DSDs) are widely-studied and useful models of molecular programming. However, in order for some DSDs in the literature to behave in an expected manner, the initial number of copies of some reagents is required to be fixed. In this paper we show that, when multiple copies of all initial molecules are present, general types of CRNs and DSDs fail to work correctly if the length of the shortest sequence of reactions needed to produce any given molecule exceeds a threshold that grows polynomially with attributes of the system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Condon, A., Hu, A.J., Maňuch, J., Thachuk, C.: Less haste, less waste: On recycling and its limits in strand displacement systems. J R Soc. Interface (2012)
Cardelli, L.: Two-domain DNA strand displacement. In: Proc. of Developments in Computational Models (DCM 2010). Electronic Proceedings in Theoretical Computer Science, vol. 26, pp. 47–61 (2010)
Qian, L., Soloveichik, D., Winfree, E.: Efficient Turing-Universal Computation with DNA Polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16 2010. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011)
Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 1196–1201 (2011)
Qian, L., Winfree, E., Bruck, J.: Neural network computation with DNA strand displacement cascades. Nature 475, 368–372 (2011)
Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006)
Soloveichik, D.: Robust stochastic chemical reaction networks and bounded tau-leaping. J. Comput. Biol. 16(3), 501–522 (2009)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comp. 7, 615–633 (2008)
Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Nat. Acad. Sci. USA 107(12), 5393–5398 (2010)
Yurke, B., Mills, A.P.: Using DNA to power nanostructures. Genet. Program. Evolvable Mach. 4(2), 111–122 (2003)
Yurke, B., Turberfield, A.J., Mills Jr., A.P., Simmel, F.C., Neumann, J.L.: A DNA-fuelled molecular machine made of DNA. Nature 406, 605–608 (2000)
Zhang, D.Y.: Cooperative hybridization of oligonucleotides. J. Am. Chem. Soc. 133, 1077–1086 (2011)
Zhang, D.Y., Turberfield, A.J., Yurke, B., Winfree, E.: Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318, 1121–1125 (2007)
Zhang, D.Y., Seelig, G.: Dynamic DNA nanotechnology using strand displacement reactions. Nature Chemistry 3, 103–113 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Condon, A., Kirkpatrick, B., Maňuch, J. (2012). Reachability Bounds for Chemical Reaction Networks and Strand Displacement Systems. In: Stefanovic, D., Turberfield, A. (eds) DNA Computing and Molecular Programming. DNA 2012. Lecture Notes in Computer Science, vol 7433. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32208-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-32208-2_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32207-5
Online ISBN: 978-3-642-32208-2
eBook Packages: Computer ScienceComputer Science (R0)