Skip to main content

2019 | OriginalPaper | Buchkapitel

Fast Enumeration of Non-isomorphic Chemical Reaction Networks

verfasst von : Carlo Spaccasassi, Boyan Yordanov, Andrew Phillips, Neil Dalchau

Erschienen in: Computational Methods in Systems Biology

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Chemical reaction networks (CRNs) have been applied successfully to model a wide range of phenomena and are commonly used for designing molecular computation circuits. Often, CRNs with specific properties (oscillations, Turing patterns, multistability) are sought, which entails searching an exponentially large space of CRNs for those that satisfy a property. As the size of the CRNs being considered grows, so does the frequency of isomorphisms, by up to a factor \(N!\), where \(N\) is the number of species. Accordingly, being able to generate sets of non-isomorphic CRNs within a class can lead to large computational savings when carrying out global searches. Here, we present a bijective encoding of bimolecular CRNs into novel vertex-coloured digraphs called https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-31304-3_12/MediaObjects/478297_1_En_12_Figa_HTML.gif . The problem of enumerating non-isomorphic CRNs can then be tackled by leveraging well-established computational methods from graph theory [20]. In particular, we extend Nauty, the graph isomorphism tool suite by McKay [22]. Our method is highly parallelisable and more efficient than competing approaches, and a software package (genCRN) is freely available for reuse. Non-isomorphs are generated directly by genCRN, alleviating the need to store intermediate results. We provide the first complete count of all 2-species bimolecular CRNs and extend previous known counts for classes of CRNs of special interest, such as mass-conserving and reversible CRNs.

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!

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
2.
Zurück zum Zitat Angeli, D., De Leenheer, P., Sontag, E.: A Petri Net approach to persistence analysis in chemical reaction networks. In: Queinnec, I., Tarbouriech, S., Garcia, G., Niculescu, S.I. (eds.) Biology and Control Theory: Current Challenges, pp. 181–216. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71988-5_9CrossRef Angeli, D., De Leenheer, P., Sontag, E.: A Petri Net approach to persistence analysis in chemical reaction networks. In: Queinnec, I., Tarbouriech, S., Garcia, G., Niculescu, S.I. (eds.) Biology and Control Theory: Current Challenges, pp. 181–216. Springer, Heidelberg (2007). https://​doi.​org/​10.​1007/​978-3-540-71988-5_​9CrossRef
4.
Zurück zum Zitat Bayramov, S.K.: New theoretical schemes of the simplest chemical oscillators. Biochem. (Mosc.) 70(12), 1377–1384 (2005)CrossRef Bayramov, S.K.: New theoretical schemes of the simplest chemical oscillators. Biochem. (Mosc.) 70(12), 1377–1384 (2005)CrossRef
5.
Zurück zum Zitat Brendan, D., McKay, A.P.: Nauty and Traces User’s Guide (2013) Brendan, D., McKay, A.P.: Nauty and Traces User’s Guide (2013)
6.
Zurück zum Zitat Brinkmann, G.: Isomorphism rejection in structure generation programs. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 51(3), 25–38 (2000)MathSciNetMATHCrossRef Brinkmann, G.: Isomorphism rejection in structure generation programs. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 51(3), 25–38 (2000)MathSciNetMATHCrossRef
7.
Zurück zum Zitat Cardelli, L., Tribastone, M., Vandin, A., Tschaikowski, M.: Forward and backward bisimulations for chemical reaction networks. In: CONCUR 2015 (2015) Cardelli, L., Tribastone, M., Vandin, A., Tschaikowski, M.: Forward and backward bisimulations for chemical reaction networks. In: CONCUR 2015 (2015)
9.
Zurück zum Zitat Chen, Y.J., et al.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755 (2013)CrossRef Chen, Y.J., et al.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8(10), 755 (2013)CrossRef
11.
Zurück zum Zitat Craciun, G., Feinberg, M.: Multiple equilibria in complex chemical reaction networks: I. The injectivity property. SIAM J. Appl. Math. 65(5), 1526–1546 (2005)MathSciNetMATHCrossRef Craciun, G., Feinberg, M.: Multiple equilibria in complex chemical reaction networks: I. The injectivity property. SIAM J. Appl. Math. 65(5), 1526–1546 (2005)MathSciNetMATHCrossRef
12.
Zurück zum Zitat Craciun, G., Feinberg, M.: Multiple equilibria in complex chemical reaction networks: II. The species-reaction graph. SIAM J. Appl. Math. 66(4), 1321–1338 (2006)MathSciNetMATHCrossRef Craciun, G., Feinberg, M.: Multiple equilibria in complex chemical reaction networks: II. The species-reaction graph. SIAM J. Appl. Math. 66(4), 1321–1338 (2006)MathSciNetMATHCrossRef
13.
Zurück zum Zitat Deckard, A.C., Bergmann, F.T., Sauro, H.M.: Enumeration and Online Library of Mass-Action Reaction Networks. arXiv e-prints arXiv:0901.3067, January 2009 Deckard, A.C., Bergmann, F.T., Sauro, H.M.: Enumeration and Online Library of Mass-Action Reaction Networks. arXiv e-prints arXiv:​0901.​3067, January 2009
14.
Zurück zum Zitat Farkas, J.: Uber die theorie der einfachen ungeichungen. J. Reine Angew. Math. 124, 1–24 (1902)MathSciNet Farkas, J.: Uber die theorie der einfachen ungeichungen. J. Reine Angew. Math. 124, 1–24 (1902)MathSciNet
15.
Zurück zum Zitat Feinberg, M.: Chemical reaction network structure and the stability of complex isothermal reactors-I. The deficiency zero and deficiency one theorems. Chem. Eng. Sci. 42(10), 2229–2268 (1987)CrossRef Feinberg, M.: Chemical reaction network structure and the stability of complex isothermal reactors-I. The deficiency zero and deficiency one theorems. Chem. Eng. Sci. 42(10), 2229–2268 (1987)CrossRef
16.
Zurück zum Zitat Feinberg, M.: Chemical reaction network structure and the stability of complex isothermal reactors-II. multiple steady states for networks of deficiency one. Chem. Eng. Sci. 43(1), 1–25 (1988)CrossRef Feinberg, M.: Chemical reaction network structure and the stability of complex isothermal reactors-II. multiple steady states for networks of deficiency one. Chem. Eng. Sci. 43(1), 1–25 (1988)CrossRef
17.
Zurück zum Zitat Hucka, M., et al.: The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models. Bioinformatics 19(4), 524–531 (2003)CrossRef Hucka, M., et al.: The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models. Bioinformatics 19(4), 524–531 (2003)CrossRef
18.
Zurück zum Zitat Karlebach, G., Shamir, R.: Modelling and analysis of gene regulatory networks. Nat. Rev. Mol. Cell Biol. 9(10), 770 (2008)CrossRef Karlebach, G., Shamir, R.: Modelling and analysis of gene regulatory networks. Nat. Rev. Mol. Cell Biol. 9(10), 770 (2008)CrossRef
19.
Zurück zum Zitat Kondo, S., Miura, T.: Reaction-diffusion model as a framework for understanding biological pattern formation. Science 329(5999), 1616–1620 (2010)MathSciNetMATHCrossRef Kondo, S., Miura, T.: Reaction-diffusion model as a framework for understanding biological pattern formation. Science 329(5999), 1616–1620 (2010)MathSciNetMATHCrossRef
22.
Zurück zum Zitat McKay, B.D., Piperno, A.: Practical graph isomorphism, II. CoRR abs/1301.1493 (2013) McKay, B.D., Piperno, A.: Practical graph isomorphism, II. CoRR abs/1301.1493 (2013)
23.
Zurück zum Zitat Mincheva, M., Roussel, M.R.: A graph-theoretic method for detecting potential turing bifurcations. J. Chem. Phys. 125(20), 204102 (2006)CrossRef Mincheva, M., Roussel, M.R.: A graph-theoretic method for detecting potential turing bifurcations. J. Chem. Phys. 125(20), 204102 (2006)CrossRef
24.
Zurück zum Zitat Mincheva, M., Roussel, M.R.: Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models. J. Math. Biol. 55(1), 61–86 (2007)MathSciNetMATHCrossRef Mincheva, M., Roussel, M.R.: Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models. J. Math. Biol. 55(1), 61–86 (2007)MathSciNetMATHCrossRef
25.
Zurück zum Zitat Miyazaki, T.: The complixity of McKay’s canonical labeling algorithm. In: Groups and Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, 7–10 June 1995, pp. 239–256 (1995) Miyazaki, T.: The complixity of McKay’s canonical labeling algorithm. In: Groups and Computation, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, 7–10 June 1995, pp. 239–256 (1995)
26.
Zurück zum Zitat Murphy, N., Petersen, R., Phillips, A., Yordanov, B., Dalchau, N.: Synthesizing and tuning stochastic chemical reaction networks with specified behaviours. J. R. Soc. Interface 15(145), 20180283 (2018)MATHCrossRef Murphy, N., Petersen, R., Phillips, A., Yordanov, B., Dalchau, N.: Synthesizing and tuning stochastic chemical reaction networks with specified behaviours. J. R. Soc. Interface 15(145), 20180283 (2018)MATHCrossRef
27.
Zurück zum Zitat Oishi, K., Klavins, E.: Biomolecular implementation of linear I/O systems. IET Syst. Biol. 5(4), 252–260 (2011)CrossRef Oishi, K., Klavins, E.: Biomolecular implementation of linear I/O systems. IET Syst. Biol. 5(4), 252–260 (2011)CrossRef
28.
Zurück zum Zitat Pedersen, M., Phillips, A.: Towards programming languages for genetic engineering of living cells. J. R. Soc. Interface 6(suppl–4), S437–S450 (2009) Pedersen, M., Phillips, A.: Towards programming languages for genetic engineering of living cells. J. R. Soc. Interface 6(suppl–4), S437–S450 (2009)
31.
Zurück zum Zitat Rosen, K.H.: Handbook of Discrete and Combinatorial Mathematics, 2nd edn. Chapman & Hall/CRC, Boca Raton (2010) Rosen, K.H.: Handbook of Discrete and Combinatorial Mathematics, 2nd edn. Chapman & Hall/CRC, Boca Raton (2010)
32.
Zurück zum Zitat Shinar, G., Feinberg, M.: Structural sources of robustness in biochemical reaction networks. Science 327(5971), 1389–1391 (2010)CrossRef Shinar, G., Feinberg, M.: Structural sources of robustness in biochemical reaction networks. Science 327(5971), 1389–1391 (2010)CrossRef
33.
Zurück zum Zitat Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Natl. Acad. Sci. 107(12), 5393–5398 (2010)CrossRef Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Natl. Acad. Sci. 107(12), 5393–5398 (2010)CrossRef
34.
Zurück zum Zitat Srinivas, N., Parkin, J., Seelig, G., Winfree, E., Soloveichik, D.: Enzyme-free nucleic acid dynamical systems. Science 358(eaal2052), 2052 (2017)CrossRef Srinivas, N., Parkin, J., Seelig, G., Winfree, E., Soloveichik, D.: Enzyme-free nucleic acid dynamical systems. Science 358(eaal2052), 2052 (2017)CrossRef
35.
Zurück zum Zitat Wilhelm, T.: The smallest chemical reaction system with bistability. BMC Syst. Biol. 3(1), 90 (2009)CrossRef Wilhelm, T.: The smallest chemical reaction system with bistability. BMC Syst. Biol. 3(1), 90 (2009)CrossRef
Metadaten
Titel
Fast Enumeration of Non-isomorphic Chemical Reaction Networks
verfasst von
Carlo Spaccasassi
Boyan Yordanov
Andrew Phillips
Neil Dalchau
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-31304-3_12