nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Computational Complexity of Atomic Chemical Reaction Networks

verfasst von : David Doty, Shaopeng Zhu

Erschienen in: SOFSEM 2018: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 [28], the equivalence we show gives an efficient algorithm to decide primitive atomicity.

Subset atomic further requires all atoms be species. 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, Gopalkrishnan et al. [1, 22], 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 [21].

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

Nächstes Kapitel Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable

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 [41].

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.

Adleman, L., Gopalkrishnan, M., Huang, M.-D., Moisset, P., Reishus, D.: On the mathematics of the law of mass action. In: Kulkarni, V.V., Stan, G.-B., Raman, K. (eds.) A Systems Theoretic Approach to Systems and Synthetic Biology I: Models and System Characterizations, pp. 3–46. Springer, Dordrecht (2014). https://doi.org/10.1007/978-94-017-9041-3_1

Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.: Time-space trade-offs in molecular computation. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2560–2579 (2017)

Angeli, D., De Leenheer, P., Sontag, E.D.: A Petri net approach to the study of persistence in chemical reaction networks. Math. Biosci. 210, 598–618 (2007)MathSciNetCrossRefMATH

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235–253 (2006). https://doi.org/10.1007/s00446-005-0138-3. Preliminary version appeared in PODC 2004CrossRefMATH

Brijder, R., Doty, D., Soloveichik, D.: Robustness of expressivity in chemical reaction networks. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 52–66. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43994-5_4 CrossRef

Cardelli, L., Csikász-Nagy, A.: The cell cycle switch computes approximate majority. Sci. Rep. 2 (2012)

Chen, H., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. Distributed Computing (2015, to appear). Special issue of invited papers from DISC 2014

Chen, H.L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 13(4), 517–534 (2013). Special issue of invited papers from DNA 2012MathSciNetCrossRefMATH

Chen, H.L., Doty, D., Soloveichik, D.: 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 (2014)

10.

Chen, Y.J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755–762 (2013)CrossRef

11.

Chubanov, S.: A polynomial projection algorithm for linear feasibility problems. Math. Program. 153(2), 687–713 (2015)MathSciNetCrossRefMATH

12.

Craciun, G., Dickenstein, A., Shiu, A., Sturmfels, B.: Toric dynamical systems. J. Symb. Computat. 44(11), 1551–1565 (2009)MathSciNetCrossRefMATH

13.

Cummings, R., Doty, D., Soloveichik, D.: Probability 1 computation with chemical reaction networks. Nat. Comput. 1–17 (2015). https://dx.doi.org/10.1007/s11047-015-9501-x. Special issue of invited papers from DNA 2014

14.

Deshpande, A., Gopalkrishnan, M.: Autocatalysis in reaction networks. arXiv preprint arXiv:1309.3957 (2013)

15.

Doty, D.: Timing in chemical reaction networks. In: SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 772–784, January 2014

16.

Doty, D., Hajiaghayi, M.: Leaderless deterministic chemical reaction networks. Nat. Comput. 14(2), 213–223 (2015). Preliminary version appeared in DNAMathSciNetCrossRefMATH

17.

Doty, D., Zhu, S.: Computational complexity of atomic chemical reaction networks. arXiv preprint arXiv:1702.05704 (2017)

18.

Esparza, J., Ganty, P., Leroux, J., Majumdar, R.: Verification of population protocols. Acta Inform. 54, 1–25 (2016)MathSciNetMATH

19.

Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman, New York (1979)MATH

20.

Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16(2), 285–296 (1966). http://projecteuclid.org/euclid.pjm/1102994974 MathSciNetCrossRefMATH

21.

Gnacadja, G.: 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 (2011)MathSciNetCrossRefMATH

22.

Gopalkrishnan, M.: Private communication. Email (2016)

23.

Guldberg, C.M., Waage, P.: Studies concerning affinity. In: Forhandlinger: Videnskabs-Selskabet i Christinia, p. 35. Norwegian Academy of Science and Letters (1864)

24.

Horn, F.J.M.: The dynamics of open reaction systems. In: SIAM-AMS Proceedings VIII, pp. 125–137 (1974)

25.

Jiang, H., Salehi, S.A., Riedel, M.D., Parhi, K.K.: Discrete-time signal processing with DNA. ACS Synth. Bafiology 2(5), 245–254 (2013)CrossRef

26.

Leroux, J.: Vector addition system reachability problem: a short self-contained proof. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 41–64. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21254-3_3 CrossRef

27.

Lien, Y.E.: A note on transition systems. Inf. Sci. 10(2), 347–362 (1976)CrossRefMATH

28.

Mayr, E.W., Weihmann, J.: A framework for classical Petri net problems: conservative Petri nets as an application. In: Ciardo, G., Kindler, E. (eds.) PETRI NETS 2014. LNCS, vol. 8489, pp. 314–333. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07734-5_17 CrossRef

29.

Montagne, K., Plasson, R., Sakai, Y., Fujii, T., Rondelez, Y.: Programming an in vitro DNA oscillator using a molecular networking strategy. Mol. Syst. Biol. 7(1) (2011)

30.

Napp, N.E., Adams, R.P.: Message passing inference with chemical reaction networks. In: Advances in Neural Information Processing Systems, pp. 2247–2255 (2013)

31.

Oishi, K., Klavins, E.: Biomolecular implementation of linear I/O systems. IET Syst. Biol. 5(4), 252–260 (2011)CrossRef

32.

Padirac, A., Fujii, T., Rondelez, Y.: Nucleic acids for the rational design of reaction circuits. Curr. Opin. Biotechnol. 24(4), 575–580 (2013)CrossRef

33.

Papadimitriou, C.H.: On the complexity of integer programming. J. ACM (JACM) 28(4), 765–768 (1981)MathSciNetCrossRefMATH

34.

Qian, L., Winfree, E., Bruck, J.: Neural network computation with dna strand displacement cascades. Nature 475(7356), 368–372 (2011)CrossRef

35.

Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034), 1196 (2011)CrossRef

36.

Salehi, S.A., Parhi, K.K., Riedel, M.D.: Chemical reaction networks for computing polynomials. ACS Synth. Biol. 6, 76–83 (2016)CrossRef

37.

Salehi, S.A., Riedel, M.D., Parhi, K.K.: Asynchronous discrete-time signal processing with molecular reactions. In: 2014 48th Asilomar Conference on Signals, Systems and Computers, pp. 1767–1772. IEEE (2014)

38.

Salehi, S.A., Riedel, M.D., Parhi, K.K.: Markov chain computations using molecular reactions. In: 2015 IEEE International Conference on Digital Signal Processing (DSP), pp. 689–693. IEEE (2015)

39.

Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970)MathSciNetCrossRefMATH

40.

Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314(5805), 1585–1588 (2006). http://www.sciencemag.org/cgi/doi/10.1126/science.1132493 CrossRef

41.

Silberschatz, A., Galvin, P.B., Gagne, G., Silberschatz, A.: Operating System Concepts. Addison-Wesley, Reading (2013)MATH

42.

Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7(4), 615–633 (2008). https://doi.org/10.1007/s11047-008-9067-y MathSciNetCrossRefMATH

43.

Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Nat. Acad. Sci. 107(12), 5393 (2010). Preliminary version appeared in DNA 2008CrossRef

44.

Srinivas, N.: Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement. Ph.D. thesis, California Institute of Technology (2015)

45.

Thachuk, C., Condon, A.: 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 (2012)

46.

Yurke, B., Turberfield, A., Mills Jr., A., Simmel, F., Neumann, J.: A DNA-fuelled molecular machine made of DNA. Nature 406(6796), 605–608 (2000)CrossRef

Titel: Computational Complexity of Atomic Chemical Reaction Networks
verfasst von: David Doty
Shaopeng Zhu
Verlag: Springer International Publishing
Buch: SOFSEM 2018: Theory and Practice of Computer Science
Print ISBN: 978-3-319-73116-2

Electronic ISBN: 978-3-319-73117-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-73117-9_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"