Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Computational Complexity of Atomic Chemical Reaction Networks

  • Conference paper
  • First Online:
SOFSEM 2018: Theory and Practice of Computer Science (SOFSEM 2018)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10706))

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

This work was supported by NSF grant 1619343.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

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

  2. 2.

    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.

References

  1. 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

    Google Scholar 

  2. 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)

    Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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 2004

    Article  MATH  Google Scholar 

  5. 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

    Chapter  Google Scholar 

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

    Google Scholar 

  7. 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

    Google Scholar 

  8. 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 2012

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

    Google Scholar 

  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)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  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

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  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

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  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)

    Article  Google Scholar 

  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

    Chapter  Google Scholar 

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

    Article  MATH  Google Scholar 

  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

    Chapter  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  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

    Article  Google Scholar 

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

    MATH  Google Scholar 

  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

    Article  MathSciNet  MATH  Google Scholar 

  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 2008

    Article  Google Scholar 

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

    Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

Download references

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.

Author information

Authors and Affiliations

  1. Computer Science Department, University of California, Davis, Davis, USA

    David Doty

  2. Computer Science Department, University of Maryland, College Park, USA

    Shaopeng Zhu

Authors
  1. David Doty
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shaopeng Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Doty .

Editor information

Editors and Affiliations

  1. Vienna University of Technology , Vienna, Austria

    A Min Tjoa

  2. ISAE-ENSMA, Chasseneuil-du-Poitou, France

    Ladjel Bellatreche

  3. Vienna University of Technology, Vienna, Austria

    Stefan Biffl

  4. Utrecht University, Utrecht, The Netherlands

    Jan van Leeuwen

  5. Academy of Sciences, Prague, Czech Republic

    Jiří Wiedermann

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Doty, D., Zhu, S. (2018). Computational Complexity of Atomic Chemical Reaction Networks. In: Tjoa, A., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds) SOFSEM 2018: Theory and Practice of Computer Science. SOFSEM 2018. Lecture Notes in Computer Science(), vol 10706. Edizioni della Normale, Cham. https://doi.org/10.1007/978-3-319-73117-9_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-73117-9_15

  • Published:

  • Publisher Name: Edizioni della Normale, Cham

  • Print ISBN: 978-3-319-73116-2

  • Online ISBN: 978-3-319-73117-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation