Abstract
Chemical reaction network has been a model of interest to both theoretical and applied computer scientists, and there has been concern about its physical-realisticity which calls for study on the atomic property of chemical reaction networks. Informally, a chemical reaction network is “atomic” if each reaction may be interpreted as the rearrangement of indivisible units of matter. There are several reasonable definitions formalizing this idea. We investigate the computational complexity of deciding whether a given network is atomic according to each of these definitions. Primitive atomic, which requires each reaction to preserve the total number of atoms, is shown to be equivalent to mass conservation. Since it is known that it can be decided in polynomial time whether a given chemical reaction network is mass-conserving (Mayr and Weihmann, in: International conference on applications and theory of petri nets and concurrency, Springer, New York, 2014), the equivalence we show gives an efficient algorithm to decide primitive atomicity. Subset atomic further requires all atoms be species, so intuitively this type of network is endowed with a “better” property than primitive atomic (i.e. mass conserving) ones in the sense that the atoms are not just abstract indivisible units, but also actual participants of reactions. We show that deciding if a network is subset atomic is in \({\mathsf{NP}}\), and “whether a network is subset atomic with respect to a given atom set” is strongly \({\mathsf{NP}}\)-\({\mathsf {complete}}\). Reachably atomic, studied by Adleman et al. (On the mathematics of the law of mass action, Springer, Dordrecht, 2014. https://doi.org/10.1007/978-94-017-9041-3_1), and Gopalkrishnan (2016), further requires that each species has a sequence of reactions splitting it into its constituent atoms. Using a combinatorial argument, we show that there is a polynomial-time algorithm to decide whether a given network is reachably atomic, improving upon the result of Adleman et al. that the problem is decidable. We show that the reachability problem for reachably atomic networks is \({\mathsf {PSPACE}}\)-\({\mathsf {complete}}\). Finally, we demonstrate equivalence relationships between our definitions and some cases of an existing definition of atomicity due to Gnacadja (J Math Chem 49(10):2137, 2011).
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.Notes
This usage of the term “atomic” is different from its usage in traditional areas like operating system or syntactic analysis, where an “atomic” execution is an uninterruptable unit of operation (Silberschatz et al. 2013).
Note that by the argument above, reversible networks are weakly reversible and hence consistent, which establishes the equivalence between self-replicability and criticality. One may further observe from Deshpande and Gopalkrishnan (2013) that this equivalence translates to the equivalence between the mass conserving property and the reachability property above.
There is typically a positive real-valued rate constant associated to each reaction, but we ignore reaction rates in this paper and consequently simplify the definition.
For example, for \(V = \{v_1,v_2,\ldots , v_5\}\), \(C = (v_1\vee v_3\vee v_4)\wedge (v_3\vee v_2\vee v_5)\), \(v_{11}=v_1, v_{12}=v_3, v_{13}=v_4, \ldots , v_{23} = v_5\). Correspondingly, \(S_{11}=S_1,X_{11}=X_1, \cdots , S_{23}=S_5, X_{23}=X_5\).
To continue the example in the previous footnote, the set of reactions shall be:
$$\begin{aligned} &3P+2F+T\rightarrow {} S_1+ S_3 + S_4\\ & 3P+2F+T\rightarrow {} S_3 + S_2 + S_5\\ & 3Q+2F+T\rightarrow {} X_1 + X_3 + X_4\\ & 3Q+2F+T\rightarrow {} X_3 + X_2 + X_5\\ & S_i + Q\rightarrow {} X_i + P\ (i = 1,2,\ldots , 5). \end{aligned}$$We point out that the set of atoms \(M\ne \{S\in \varLambda \mid \exists ({{\mathbf {r}}},{\mathbf {p}})\in R\, {{\text { s.t. }}}\,(\{1S\}={{\mathbf {r}}})\wedge (\Vert {\mathbf {p}}\Vert \ge 2)\}\), so we have to test the \(\Vert {\mathbf {d}}_S\Vert \ge 2\) condition in later steps. This is because it might be the case that the only reaction \(({{\mathbf {r}}},{\mathbf {p}})\) with \({{\mathbf {r}}}=\{1S\}\) turns out to be an isomerization reaction. A counter example would be:
$$\begin{aligned} A\rightarrow & {} B\\ B\rightarrow & {} 2C \end{aligned}$$By our definition \(M = \{S\in \varLambda \mid \exists ({{\mathbf {r}}},{\mathbf {p}})\in R\ {{\text { s.t. }}}\,\{1S\}={{\mathbf {r}}}\}\), we shall correctly identify \(M=\{A,B\}\), yet the added condition \(\Vert {\mathbf {p}}\Vert \ge 2\) would make \(M=\{B\}\), a mis-identification.
That is, if (\(\forall S\in M'\))(\(\forall ({{\mathbf {r}}},{\mathbf {p}})\in R\)) (\({{\mathbf {r}}}=\{1S\}\Rightarrow [{\mathbf {p}}]\cap M'\ne \emptyset\)), then for each species S in \(M'\) there will be \(S'\in M'\) s.t. \(\Vert S\Vert _1>\Vert S'\Vert _1\), contradicting the finiteness of \(M'\).
We organize the construction procedure as an algorithm to make the description more concise.
References
Adleman L, Gopalkrishnan M, Huang M-D, Moisset P, Reishus D (2014) On the mathematics of the law of mass action. Springer, Dordrecht, pp 3–46. https://doi.org/10.1007/978-94-017-9041-3_1
Alistarh D, Aspnes J, Eisenstat D, Gelashvili R, Rivest R (2017) Time-space trade-offs in molecular computation. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms. pp 2560–2579
Angeli D, De Leenheer P, Sontag ED (2007) A Petri net approach to the study of persistence in chemical reaction networks. Math Biosci 210:598–618
Angluin D, Aspnes J, Diamadi Z, Fischer M, Peralta R (2006) Computation in networks of passively mobile finite-state sensors. Distrib Comput 18:235–253. https://doi.org/10.1007/s00446-005-0138-3 (Preliminary version appeared in PODC 2004)
Brijder R, Doty D, Soloveichik D (2016) Robustness of expressivity in chemical reaction networks. In: DNA 2016: proceedings of the 22th international meeting on DNA computing and molecular programming
Cardelli L, Csikász-Nagy A (2012) The cell cycle switch computes approximate majority. Scientific Reports, 2
Chen H-L, Cummings R, Doty D, Soloveichik D(2014) Speed faults in computation by chemical reaction networks. Distrib Comput (2015, to appear, special issue of invited papers from DISC)
Chen H-L, Doty D, Soloveichik D (2013) Deterministic function computation with chemical reaction networks. Nat Comput 13(4):517–534 (Special issue of invited papers from DNA 2012)
Chen H-L, Doty D, Soloveichik D (2014) Rate-independent computation in continuous chemical reaction networks. In ITCS 2014: proceedings of the 5th conference on innovations in theoretical computer science. 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
Chubanov S (2015) A polynomial projection algorithm for linear feasibility problems. Math Program 153(2):687–713
Craciun G, Dickenstein A, Shiu A, Sturmfels B (2009) Toric dynamical systems. J Symb Comput 44(11):1551–1565
Cummings R, Doty D, Soloveichik D (2015) Probability 1 computation with chemical reaction networks. Nat Comput 1–17. https://doi.org/10.1007/s11047-015-9501-x (Special issue of invited papers from. DNA 2014)
Deshpande A, Gopalkrishnan M (2013) Autocatalysis in reaction networks. arXiv preprint arXiv:1309.3957
Doty David (January 2014) Timing in chemical reaction networks. In: SODA 2014: proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, pp 772–784
Doty D, Hajiaghayi M (2015) Leaderless deterministic chemical reaction networks. Nat Comput 14(2):213–223 (Preliminary version appeared in DNA 2013)
Doty D, Zhu S (2017) Computational complexity of atomic chemical reaction networks. arXiv preprint arXiv:1702.05704
Doty D, Zhu S (2018) Computational complexity of atomic chemical reaction networks. In: International conference on current trends in theory and practice of informatics. pp 212–226. Springer, New York
Esparza J, Ganty P, Leroux J, Majumdar R (2017) Verification of population protocols. Acta Inform 54(2):191–215
Garey MR, Johnson DS (1978) “strong” NP-completeness results: motivation, examples, and implications. JACM 25(3):499–508
Garey MR, Johnson DS (1979) Computers and intractability. W. H. Freeman, New York
Ginsburg S, Spanier EH (1966) Semigroups, Presburger formulas, and languages. Pac J Math 16(2):285–296. http://projecteuclid.org/euclid.pjm/1102994974
Gnacadja G (2011) Reachability, persistence, and constructive chemical reaction networks (part II): a formalism for species composition in chemical reaction network theory and application to persistence. J Math Chem 49(10):2137
Gopalkrishnan M (2016) Private communication. Email
Guldberg CM, Waage P (1864) Studies concerning affinity. Forhandlinger: Videnskabs-Selskabet i Christinia. In: Norwegian Academy of Science and Letters, 35
Horn FJM (1974) The dynamics of open reaction systems. In SIAM-AMS proceedings VIII, pp 125–137
Hua J, Ahmad SS, Riedel Marc D, Parhi Keshab K (2013) Discrete-time signal processing with DNA. ACS Synth Bafiol 2(5):245–254
Leroux J (2011) Vector addition system reachability problem: a short self-contained proof. In: ACM SIGPLAN notices. ACM, vol 46, pp 307–316
Lien YE (1976) A note on transition systems. Inform Sci 10(2):347–362
Mayr EW, Weihmann J (2014) A framework for classical Petri net problems: conservative petri nets as an application. In: International conference on applications and theory of petri nets and concurrency. Springer, New York, pp 314–333
Montagne K, Plasson R, Sakai Y, Fujii T, Rondelez Y (2011) Programming an in vitro DNA oscillator using a molecular networking strategy. Mol Syst Biol 7(1):466
Napp NE, Adams RP (2013) Message passing inference with chemical reaction networks. In: Advances in neural information processing systems. pp 2247–2255
Oishi K, Klavins E (2011) Biomolecular implementation of linear I/O systems. IET Syst Biol 5(4):252–260
Padirac A, Fujii T, Rondelez Y (2013) Nucleic acids for the rational design of reaction circuits. Curr Opin Biotechnol 24(4):575–580
Papadimitriou Christos H (1981) On the complexity of integer programming. JACM 28(4):765–768
Papadimitriou CH (2003) Computational complexity. Wiley, New York
Qian L, Winfree E, Bruck J (2011) Neural network computation with dna strand displacement cascades. Nature 475(7356):368–372
Qian L, Winfree E (2011) Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034):1196
Roos K (2015) An improved version of Chubanov’s method for solving a homogeneous feasibility problem. Optim Method Softw 33(1):26–44
Salehi SA, Parhi KK, Riedel MD (2016) Chemical reaction networks for computing polynomials. ACS Synth Biol 6(1):76–83
Salehi SA, Riedel MD, Parhi KK (2014) Asynchronous discrete-time signal processing with molecular reactions. In: 2014 48th Asilomar conference on signals, systems and computers, pp 1767–1772
Salehi SA, Riedel MD, Parhi KK (2015) Markov chain computations using molecular reactions. In: 2015 IEEE international conference on digital signal processing (DSP), pp 689–693
Savitch WJ (1970) Relationships between nondeterministic and deterministic tape complexities. J Comput Syst Sci 4(2):177–192
Seelig G, Soloveichik D, Zhang DY, Winfree E (2006) Enzyme-free nucleic acid logic circuits. Science 314(5805):1585–1588. https://doi.org/10.1126/science.1132493
Silberschatz A, Galvin PB, Gagne G, Silberschatz A (2013) Operating system concepts, vol 4. Addison-Wesley, Reading
Soloveichik D, Cook M, Winfree E, Bruck J (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615–633. https://doi.org/10.1007/s11047-008-9067-y
Soloveichik D, Seelig G, Winfree E (2010) DNA as a universal substrate for chemical kinetics. Proc Natl Acad Sci 107(12):5393 (Preliminary version appeared in DNA 2008)
Srinivas N (2015) Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement. PhD thesis, California Institute of Technology
Thachuk C, Condon A (2012) Space and energy efficient computation with DNA strand displacement systems. In: DNA 2012: proceedings of the 18th international meeting on DNA computing and molecular programming, pp 135–149
Yurke B, Turberfield AJ, Mills AP Jr, Simmel FC, Neumann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406(6796):605–608
Acknowledgements
The authors are thankful to Manoj Gopalkrishnan, Gilles Gnacadja, Javier Esparza, Sergei Chubanov, Matthew Cook, and anonymous reviewers for their insights and useful discussion.
Funding
Funding was provided by NSF (Grant No. 1619343).
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is based on Doty and Zhu (2018), which omitted many detailed proofs to various theorems and lemmas, such as the poly-time decidability of Reachably-Atomic. These proofs have been included in the current version of the paper. We have also corrected some errors and typos that appeared in the conference version.
Rights and permissions
About this article
Cite this article
Doty, D., Zhu, S. Computational complexity of atomic chemical reaction networks. Nat Comput 17, 677–691 (2018). https://doi.org/10.1007/s11047-018-9687-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-018-9687-9