nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Minimal Trap Spaces of Logical Models are Maximal Siphons of Their Petri Net Encoding

verfasst von : Van-Giang Trinh, Belaid Benhamou, Kunihiko Hiraishi, Sylvain Soliman

Erschienen in: Computational Methods in Systems Biology

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

Boolean modelling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. This is even more true for very large models where such data is frequently missing and led to a constant increase in size of logical models à la Thomas. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model-size, the state-of-the-art computation of minimal trap spaces based on prime-implicants shows its limits as there can be a huge number of implicants.

In this article we present an alternative method to compute minimal trap spaces, and hence complex attractors, of a Boolean model. It replaces the need for prime-implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. After some technical preliminaries, we expose the concrete need for such a method and detail its implementation using Answer Set Programming. We then demonstrate its efficiency and compare it to implicant-based methods on some large Boolean models from the literature.

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 Variable-Depth Simulation of Most Permissive Boolean Networks

Nächstes Kapitel Stability Versus Meta-stability in a Skin Microbiome Model

https://github.com/bnediction/mpbn.

https://www.pnml.org/.

http://www.colomoto.org/biolqm/.

http://colomoto.org/.

https://github.com/hklarner/pyboolnet/tree/master/pyboolnet/repository.

Aghamiri, S.S., et al.: Automated inference of Boolean models from molecular interaction maps using CaSQ. Bioinformatics 36(16), 4473–4482 (2020). https://doi.org/10.1093/bioinformatics/btaa484CrossRefPubMedPubMedCentral

Angeli, D., Leenheer, P.D., Sontag, E.: A Petri net approach to persistence analysis in chemical reaction networks. In: Queinnec, I., Tarbouriech, S., Garcia, G., Niculescu, SI. (eds.) Biology and Control Theory: Current Challenges, pp. 181–216. Springer (2007). https://doi.org/10.1007/978-3-540-71988-5_9

Angeli, D., Leenheer, P.D., Sontag, E.D.: Persistence results for chemical reaction networks with time-dependent kinetics and no global conservation laws. SIAM J. Appl. Math. 71(1), 128–146 (2011). https://doi.org/10.1137/090779401CrossRef

Blätke, M.A., Heiner, M., Marwan, W.: Biomodel engineering with Petri nets. In: Algebraic and Discrete Mathematical Methods for Modern Biology, pp. 141–192. Elsevier (2015). https://doi.org/10.1016/B978-0-12-801213-0.00007-1

Chaouiya, C., Bérenguier, D., Keating, S.M., Naldi, A., et al.: SBML qualitative models: a model representation format and infrastructure to foster interactions between qualitative modelling formalisms and tools. BMC Syst. Biol. 7, 135 (2013). https://doi.org/10.1186/1752-0509-7-135CrossRefPubMedPubMedCentral

Chaouiya, C., Naldi, A., Remy, E., Thieffry, D.: Petri net representation of multi-valued logical regulatory graphs. Nat. Comput. 10(2), 727–750 (2011). https://doi.org/10.1007/s11047-010-9178-0CrossRef

Chaouiya, C., Naldi, A., Thieffry, D.: Logical modelling of gene regulatory networks with GINsim. In: van Helden, J., Toussaint, A., Thieffry, D. (eds.) Bacterial Molecular Networks, pp. 463–479. Springer (2012). https://doi.org/10.1007/978-1-61779-361-5_23

Chaouiya, C., Remy, E., Ruet, P., Thieffry, D.: Qualitative modelling of genetic networks: from logical regulatory graphs to standard petri nets. In: Cortadella, J., Reisig, W. (eds.) ICATPN 2004. LNCS, vol. 3099, pp. 137–156. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27793-4_9CrossRef

Chatain, T., Haar, S., Jezequel, L., Paulevé, L., Schwoon, S.: Characterization of reachable attractors using petri net unfoldings. In: Mendes, P., Dada, J.O., Smallbone, K. (eds.) CMSB 2014. LNCS, vol. 8859, pp. 129–142. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-12982-2_10CrossRef

10.

Chatain, T., Haar, S., Kolčák, J., Paulevé, L., Thakkar, A.: Concurrency in Boolean networks. Nat. Comput. 19(1), 91–109 (2019). https://doi.org/10.1007/s11047-019-09748-4CrossRef

11.

Chevalier, S., Froidevaux, C., Paulevé, L., Zinovyev, A.Y.: Synthesis of Boolean networks from biological dynamical constraints using answer-set programming. In: 31st IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2019, Portland, OR, USA, 4–6 November 2019, pp. 34–41. IEEE (2019). https://doi.org/10.1109/ICTAI.2019.00014

12.

Chevalier, S., Noël, V., Calzone, L., Zinovyev, A., Paulevé, L.: Synthesis and simulation of ensembles of boolean networks for cell fate decision. In: Abate, A., Petrov, T., Wolf, V. (eds.) CMSB 2020. LNCS, vol. 12314, pp. 193–209. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60327-4_11CrossRef

13.

Corral-Jara, K.F., et al.: Interplay between SMAD2 and STAT5A is a critical determinant of IL-17A/IL-17F differential expression. Mol. Biomed. 2(1), 1–16 (2021). https://doi.org/10.1186/s43556-021-00034-3CrossRef

14.

Degrand, É., Fages, F., Soliman, S.: Graphical conditions for rate independence in chemical reaction networks. In: Abate, A., Petrov, T., Wolf, V. (eds.) CMSB 2020. LNCS, vol. 12314, pp. 61–78. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60327-4_4CrossRef

15.

Didier, G., Remy, E., Chaouiya, C.: Mapping multivalued onto Boolean dynamics. J. Theor. Biol. 270(1), 177–184 (2011). https://doi.org/10.1016/j.jtbi.2010.09.017CrossRefPubMed

16.

Cifuentes Fontanals, L., Tonello, E., Siebert, H.: Control strategy identification via trap spaces in Boolean networks. In: Abate, A., Petrov, T., Wolf, V. (eds.) CMSB 2020. LNCS, vol. 12314, pp. 159–175. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60327-4_9CrossRef

17.

Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: the Potsdam answer set solving collection. AI Commun. 24(2), 107–124 (2011). https://doi.org/10.3233/AIC-2011-0491CrossRef

18.

Glass, L., Kauffman, S.A.: The logical analysis of continuous, non-linear biochemical control networks. J. Theor. Biol. 39(1), 103–129 (1973). https://doi.org/10.1016/0022-5193(73)90208-7CrossRefPubMed

19.

Guberman, E., Sherief, H., Regan, E.R.: Boolean model of anchorage dependence and contact inhibition points to coordinated inhibition but semi-independent induction of proliferation and migration. Comput. Struct. Biotechnol. J. 18, 2145–2165 (2020). https://doi.org/10.1016/j.csbj.2020.07.016CrossRefPubMedPubMedCentral

20.

Helikar, T., et al.: A comprehensive, multi-scale dynamical model of ErbB receptor signal transduction in human mammary epithelial cells. PloS One 8(4), e61757 (2013). https://doi.org/10.1371/journal.pone.0061757CrossRefPubMedPubMedCentral

21.

Helikar, T., Konvalina, J., Heidel, J., Rogers, J.A.: Emergent decision-making in biological signal transduction networks. Proc. National Acad. Sci. 105(6), 1913–1918 (2008). https://doi.org/10.1073/pnas.0705088105CrossRef

22.

Helikar, T., Kowal, B.M., McClenathan, S., Bruckner, M., et al.: The Cell Collective: toward an open and collaborative approach to systems biology. BMC Syst. Biol. 6, 96 (2012). https://doi.org/10.1186/1752-0509-6-96CrossRefPubMedPubMedCentral

23.

Hernandez, C., Thomas-Chollier, M., Naldi, A., Thieffry, D.: Computational verification of large logical models-application to the prediction of T cell response to checkpoint inhibitors. Front. Physiol. 1154 (2020). https://doi.org/10.3389/fphys.2020.558606

24.

Keating, S.M., Waltemath, D., König, M., Zhang, F., et al.: SBML Level 3: an extensible format for the exchange and reuse of biological models. Mol. Syst. Biol. 16(8), e9110 (2020). https://doi.org/10.15252/msb.20199110CrossRefPubMedPubMedCentral

25.

Kim, J.R., Kim, J., Kwon, Y.K., Lee, H.Y., Heslop-Harrison, P., Cho, K.H.: Reduction of complex signaling networks to a representative kernel. Sci. Signal. 4(175), ra35 (2011). https://doi.org/10.1126/scisignal.2001390CrossRefPubMed

26.

Kim, J., Yi, G.S.: RMOD: a tool for regulatory motif detection in signaling network. PloS One 8(7), e68407 (2013). https://doi.org/10.1371/journal.pone.0068407CrossRefPubMedPubMedCentral

27.

Klarner, H., Bockmayr, A., Siebert, H.: Computing maximal and minimal trap spaces of Boolean networks. Nat. Comput. 14(4), 535–544 (2015). https://doi.org/10.1007/s11047-015-9520-7CrossRef

28.

Klarner, H., Streck, A., Siebert, H.: PyBoolNet: a python package for the generation, analysis and visualization of Boolean networks. Bioinformatics 33(5), 770–772 (2017). https://doi.org/10.1093/bioinformatics/btw682CrossRefPubMed

29.

Kwon, Y.: Properties of Boolean dynamics by node classification using feedback loops in a network. BMC Syst. Biol. 10, 83 (2016). https://doi.org/10.1186/s12918-016-0322-zCrossRefPubMedPubMedCentral

30.

Lee, D., Cho, K.H.: Signal flow control of complex signaling networks. Sci. Rep. 9(1), 1–18 (2019). https://doi.org/10.1038/s41598-019-50790-0CrossRef

31.

Liu, G., Barkaoui, K.: A survey of siphons in Petri nets. Inf. Sci. 363, 198–220 (2016). https://doi.org/10.1016/j.ins.2015.08.037CrossRef

32.

Montagud, A., et al.: Patient-specific Boolean models of signaling networks guide personalized treatments. BioRxiv (2021). https://doi.org/10.1101/2021.07.28.454126

33.

Murata, T.: Petri nets: properties, analysis and applications. Proc. IEEE 77(4), 541–580 (1989). https://doi.org/10.1109/5.24143CrossRef

34.

Müssel, C., Hopfensitz, M., Kestler, H.A.: BoolNet - an R package for generation, reconstruction and analysis of Boolean networks. Bioinformatics 26(10), 1378–1380 (2010). https://doi.org/10.1093/bioinformatics/btq124CrossRefPubMed

35.

Nabli, F., Martinez, T., Fages, F., Soliman, S.: On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity. Constraints 21(2), 251–276 (2015). https://doi.org/10.1007/s10601-015-9190-1CrossRef

36.

Naldi, A., et al.: Cooperative development of logical modelling standards and tools with CoLoMoTo. Bioinformatics 31(7), 1154–1159 (2015). https://doi.org/10.1093/bioinformatics/btv013CrossRefPubMed

37.

Noual, M., Regnault, D., Sené, S.: About non-monotony in Boolean automata networks. Theor. Comput. Sci. 504, 12–25 (2013). https://doi.org/10.1016/j.tcs.2012.05.034CrossRef

38.

Oanea, O., Wimmel, H., Wolf, K.: New algorithms for deciding the siphon-trap property. In: Lilius, J., Penczek, W. (eds.) PETRI NETS 2010. LNCS, vol. 6128, pp. 267–286. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13675-7_16CrossRef

39.

Ogishima, S., et al.: AlzPathway, an updated map of curated signaling pathways: towards deciphering Alzheimer’s disease pathogenesis. In: Castrillo, J.I., Oliver, S.G. (eds.) Systems Biology of Alzheimer’s Disease. MMB, vol. 1303, pp. 423–432. Springer, New York (2016). https://doi.org/10.1007/978-1-4939-2627-5_25CrossRef

40.

Ostaszewski, M., Niarakis, A., Mazein, A., Kuperstein, I., Phair, R., Orta-Resendiz, A., Singh, V., Aghamiri, S.S., Acencio, M.L., Glaab, E., et al.: COVID19 disease map, a computational knowledge repository of virus-host interaction mechanisms. Mol. Syst. Biol. 17(10), e10387 (2021). https://doi.org/10.15252/msb.202110387CrossRefPubMedPubMedCentral

41.

Paulevé, L., Kolčák, J., Chatain, T., Haar, S.: Reconciling qualitative, abstract, and scalable modeling of biological networks. Nat. Commun. 11(1), 1–7 (2020). https://doi.org/10.1038/s41467-020-18112-5CrossRef

42.

Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice Hall PTR, Hoboken (1981)

43.

Reddy, V.N., Mavrovouniotis, M.L., Liebman, M.N.: Petri net representations in metabolic pathways. In: Hunter, L., Searls, D.B., Shavlik, J.W. (eds.) Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, Bethesda, MD, USA, July 1993, pp. 328–336. AAAI (1993). http://www.aaai.org/Library/ISMB/1993/ismb93-038.php

44.

Rodríguez-Jorge, O., et al.: Cooperation between T cell receptor and Toll-like receptor 5 signaling for CD4+ T cell activation. Sci. Signal. 12(577), eaar3641 (2019). https://doi.org/10.1126/scisignal.aar3641CrossRefPubMed

45.

Singh, V., et al.: Computational systems biology approach for the study of rheumatoid arthritis: from a molecular map to a dynamical model. Genom. Comput. Biol. 4(1), e100050 (2018). https://doi.org/10.18547/gcb.2018.vol4.iss1.e100050CrossRefPubMed

46.

Thomas, R.: Boolean formalisation of genetic control circuits. J. Theor. Biol. 42, 565–583 (1973). https://doi.org/10.1016/0022-5193(73)90247-6CrossRef

47.

Thomas, R.: Regulatory networks seen as asynchronous automata: a logical description. J. Theor. Biol. 153(1), 1–23 (1991). https://doi.org/10.1016/S0022-5193(05)80350-9CrossRef

48.

Thomas, R., d’Ari, R.: Biological Feedback. CRC Press, Boca Raton (1990)

49.

Tsirvouli, E., Touré, V., Niederdorfer, B., Vázquez, M., Flobak, Å., Kuiper, M.: A middle-out modeling strategy to extend a colon cancer logical model improves drug synergy predictions in epithelial-derived cancer cell lines. Front. Mol. Biosci. 7, 502573 (2020). https://doi.org/10.3389/fmolb.2020.502573CrossRefPubMedPubMedCentral

50.

Wang, R.S., Saadatpour, A., Albert, R.: Boolean modeling in systems biology: an overview of methodology and applications. Phys. Biol. 9(5), 055001 (2012). https://doi.org/10.1088/1478-3975/9/5/055001CrossRefPubMed

51.

Zevedei-Oancea, I., Schuster, S.: Topological analysis of metabolic networks based on Petri net theory. Silico Biol. 3(3), 323–345 (2003). http://content.iospress.com/articles/in-silico-biology/isb00100

Titel: Minimal Trap Spaces of Logical Models are Maximal Siphons of Their Petri Net Encoding
verfasst von: Van-Giang Trinh
Belaid Benhamou
Kunihiko Hiraishi
Sylvain Soliman
Verlag: Springer International Publishing
Buch: Computational Methods in Systems Biology
Print ISBN: 978-3-031-15033-3

Electronic ISBN: 978-3-031-15034-0

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-15034-0_8

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"

Premium Partner