Abstract
Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed solution. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced rate-independent continuous CRNs (CCRNs) to study the chemical computation of continuous functions. A fundamental question for any CRN model is reachability, the question whether a given target state is reachable from a given start state via a sequence of reactions (a path) in the network. In this paper, we investigate CCRN-REACH, the reachability problem for rate-independent continuous chemical reaction networks. Our main theorem is that, for CCRNs, deciding reachability—and constructing a path if there is one—is computable in polynomial time. This contrasts sharply with the known exponential space hardness of the reachability problem for discrete CRNs. We also prove that the related problem Sub-CCRN-REACH, which asks about reachability in a CCRN using only a given number of its reactions, is NP-complete.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R (2006) Computation in networks of passively mobile finite-state sensors. Distrib Comput 18(4):235–253
Cardelli L (2011) Strand algebras for DNA computing. Nat Comput 10(1):407–428
Case A, Lutz JH, Stull DM (2016) Reachability problems for continuous chemical reaction networks. In: Proceedings of the 15th international conference unconventional computation and natural computation, pp 1–10
Chen H-L, Doty D, Soloveichik D (2014) Rate-independent computation in continuous chemical reaction networks. In: ITCS 2014: proceedings of the 5th innovations in theoretical computer science conference, pp 313–326
Chen Y-J, Dalchau N, Srinivas N, Phillips A, Cardelli L, Soloveichik D, Seelig G (2013) Programmable chemical controllers made from DNA. Nat Nanotechnol 8(10):755–762
Cook M, Soloveichik D, Winfree E, Bruck J (2009) Programmability of chemical reaction networks, Algorithmic bioprocesses. Springer, Berlin, pp 543–584
Elowitz MB, Levine AJ, Siggia ED, Swain PS (2002) Stochastic gene expression in a single cell. Science 297:1183–1185
Esparza J, Nielsen M (1994) Decidability issues for Petri nets—a survey. J Inform Process Cybern 3:143–160
Gillespie DT (1977) Exact stochastic simulation of coupled chemical reactions. J Phys Chem 81(25):2340–2361
Jiang H, Riedel M, Parhi K (2012) Digital signal processing with molecular reactions. IEEE Design Test Comput 29(3):21–31
Karp RM, Miller RE (1969) Parallel program schemata. J Comput Syst Sci 3(4):147–195
Kleinberg JM, Tardos É (2006) Algorithm design. Addison-Wesley, Boston
Kosaraju SR (1982) Decidability of reachability in vector addition systems (preliminary version). In: STOC 1982. ACM, pp 267–281
Lambert JL (1992) A structure to decide reachability in Petri nets. Theor Comput Sci 99(1):79–104
Leroux J (2012) Vector addition reachability problem (a simpler solution). In: The Alan turing centenary conference, volume 10 of EPiC series. EasyChair, pp 214–228
Lipton RJ (1976) The reachability problem requires exponential space technical report. Yale University, New Haven
Mayr EW(1981) An algorithm for the general Petri net reachability problem. In: STOC 1981. ACM, pp 238–246
McAdams HH, Arkin AP (1997) Stochastic mechanisms in gene expression. Proc Natl Acad Sci 94:814–819
Sacerdote GS, Tenney RL (1977) The decidability of the reachability problem for vector addition systems (preliminary version). In: STOC 1977. ACM, pp 61–76
Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615–633
Soloveichik D, Seelig G, Winfree E (2010) DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci 107(12):53–93
Acknowledgements
We thank Tim McNicholl, Xiang Huang, Titus Klinge, and Jim Lathrop for useful discussions. We also thank three anonymous reviewers for detailed improvements to this paper.
Funding
This research was supported in part by National Science Foundation Grants 1247051 and 1545028. Part of the second author’s work was carried out while participating in the 2015 Focus Semester on Computability and Randomness at Heidelberg University. A preliminary version of part of this work was presented at the Fifteenth International Conference on Unconventional Computation and Natural Computation (UCNC 2016, Manchester, UK, July 11–15, 2016).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Case, A., Lutz, J.H. & Stull, D.M. Reachability problems for continuous chemical reaction networks. Nat Comput 17, 223–230 (2018). https://doi.org/10.1007/s11047-017-9641-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-017-9641-2