nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Reducing Boolean Networks with Backward Boolean Equivalence

verfasst von : Georgios Argyris, Alberto Lluch Lafuente, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

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 Networks (BNs) are established models to qualitatively describe biological systems. The analysis of BNs might be infeasible for medium to large BNs due to the state-space explosion problem. We propose a novel reduction technique called Backward Boolean Equivalence (BBE), which preserves some properties of interest of BNs. In particular, reduced BNs provide a compact representation by grouping variables that, if initialized equally, are always updated equally. The resulting reduced state space is a subset of the original one, restricted to identical initialization of grouped variables. The corresponding trajectories of the original BN can be exactly restored. We show the effectiveness of BBE by performing a large-scale validation on the whole GINsim BN repository. In selected cases, we show how our method enables analyses that would be otherwise intractable. Our method complements, and can be combined with, other reduction methods found in 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

Nächstes Kapitel Abstraction of Markov Population Dynamics via Generative Adversarial Nets

All proofs are given in the extended version of this paper [1].

Argyris, G., Lafuente, A.L., Tribastone, M., Tschaikowski, M., Vandin, A.: Reducing boolean networks with backward boolean equivalence - extended version (2021). https://arxiv.org/abs/2106.15476

Bérenguier, D., Chaouiya, C., Monteiro, P.T., Naldi, A., Remy, E., Thieffry, D., Tichit, L.: Dynamical modeling and analysis of large cellular regulatory networks. Chaos. Interdisc. J. Nonlinear Sci. 23(2), 025114 (2013)CrossRef

Biere, A., Biere, A., Heule, M., van Maaren, H., Walsh, T.: Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications. IOS Press, NLD (2009)

Bilke, S., Sjunnesson, F.: Stability of the Kauffman model. Phys. Rev. E 65(1), 016129 (2001)CrossRef

Cardelli, L., Perez-Verona, I.C., Tribastone, M., Tschaikowski, M., Vandin, A., Waizmann, T.: Exact maximal reduction of stochastic reaction networks by species lumping. Bioinformatics (2021). https://doi.org/10.1093/bioinformatics/btab081

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Forward and backward bisimulations for chemical reaction networks. In: 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, 1–4 September 2015, pp. 226–239 (2015). https://doi.org/10.4230/LIPIcs.CONCUR.2015.226

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Comparing chemical reaction networks: a categorical and algorithmic perspective. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, New York, NY, USA, 5–8 July 2016, pp. 485–494 (2016). https://doi.org/10.1145/2933575.2935318

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Efficient syntax-driven lumping of differential equations. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 93–111. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49674-9_6CrossRef

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Symbolic computation of differential equivalences. In: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, St. Petersburg, FL, USA, 20–22 January 2016, pp. 137–150 (2016). https://doi.org/10.1145/2837614.2837649

10.

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: ERODE: a tool for the evaluation and reduction of ordinary differential equations. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10206, pp. 310–328. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54580-5_19CrossRef

11.

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Maximal aggregation of polynomial dynamical systems. Proc. Nat. Acad. Sci. 114(38), 10029–10034 (2017)CrossRef

12.

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Comparing chemical reaction networks: a categorical and algorithmic perspective. Theor. Comput. Sci. 765, 47–66 (2019). https://doi.org/10.1016/j.tcs.2017.12.018

13.

Cardelli, L., Tribastone, M., Tschaikowski, M., Vandin, A.: Symbolic computation of differential equivalences. Theor. Comput. Sci. 777, 132–154 (2019). https://doi.org/10.1016/j.tcs.2019.03.018

14.

Chaouiya, C., et al.: SBML qualitative models: a model representation format and infrastructure to foster interactions between qualitative modelling formalisms and tools. BMC Syst. Biol. 7(1), 1–15 (2013)CrossRef

15.

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, New York (2012). https://doi.org/10.1007/978-1-61779-361-5_23

16.

Chaouiya, C., Remy, E., Thieffry, D.: Petri net modelling of biological regulatory networks. J. Discrete Algorithms 6(2), 165–177 (2008)CrossRef

17.

de Moura, L., Bjørner, N.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337–340. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78800-3_24CrossRef

18.

Delaplace, F., Ivanov, S.: Bisimilar booleanization of multivalued networks. BioSystems 197, 104205 (2020)CrossRef

19.

Di Cara, A., Garg, A., De Micheli, G., Xenarios, I., Mendoza, L.: Dynamic simulation of regulatory networks using squad. BMC Bioinformatics 8(1), 462 (2007)CrossRef

20.

Drossel, B.: Random boolean networks. Rev. Nonlinear Dyn. Complex. 1, 69–110 (2008)CrossRef

21.

Dubrova, E., Teslenko, M.: A sat-based algorithm for finding attractors in synchronous boolean networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 8(5), 1393–1399 (2011)CrossRef

22.

Fauré, A., Naldi, A., Lopez, F., Chaouiya, C., Ciliberto, A., Thieffry, D.: Modular logical modelling of the budding yeast cell cycle. Mol. BioSyst. 5, 1787–96 (2009)CrossRef

23.

Figueiredo, D.: Relating bisimulations with attractors in boolean network models. In: Botón-Fernández, M., Martín-Vide, C., Santander-Jiménez, S., Vega-Rodríguez, M.A. (eds.) AlCoB 2016. LNCS, vol. 9702, pp. 17–25. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-38827-4_2CrossRef

24.

Garg, A., Di Cara, A., Xenarios, I., Mendoza, L., De Micheli, G.: Synchronous versus asynchronous modeling of gene regulatory networks. Bioinformatics 24(17), 1917–1925 (2008). https://doi.org/10.1093/bioinformatics/btn336

25.

Giacomantonio, C.E., Goodhill, G.J.: A boolean model of the gene regulatory network underlying mammalian cortical area development. PLOS Comput. Biol. 6(9), 1–13 (2010). https://doi.org/10.1371/journal.pcbi.1000936

26.

Grieco, L., Calzone, L., Bernard-Pierrot, I., Radvanyi, F., Kahn-Perles, B., Thieffry, D.: Integrative modelling of the influence of MAPK network on cancer cell fate decision. PLoS Comput. Biol. 9(10), e1003286 (2013)CrossRef

27.

Hopfensitz, M., Müssel, C., Maucher, M., Kestler, H.A.: Attractors in boolean networks: a tutorial. Comput. Stat. 28(1), 19–36 (2013)CrossRef

28.

Kauffman, S.: Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol. 22(3), 437–467 (1969)CrossRef

29.

Klamt, S., Haus, U.U., Theis, F.: Hypergraphs and cellular networks. PLoS Comput. Biol. 5(5), e1000385 (2009)CrossRef

30.

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)PubMed

31.

Naldi, A., Berenguier, D., Fauré, A., Lopez, F., Thieffry, D., Chaouiya, C.: Logical modelling of regulatory networks with GINsim 2.3. Biosystems 97(2), 134–139 (2009)CrossRef

32.

Naldi, A., Monteiro, P.T., Chaouiya, C.: Efficient handling of large signalling-regulatory networks by focusing on their core control. In: Gilbert, D., Heiner, M. (eds.) CMSB 2012. LNCS, pp. 288–306. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33636-2_17CrossRef

33.

Naldi, A., et al.: Cooperative development of logical modelling standards and tools with colomoto. Bioinformatics 31(7), 1154–1159 (2015)CrossRef

34.

Naldi, A., Remy, E., Thieffry, D., Chaouiya, C.: Dynamically consistent reduction of logical regulatory graphs. Theor. Comput. Sci. 412(21), 2207–2218 (2011)CrossRef

35.

Naldi, A., et al.: The colomoto interactive notebook: accessible and reproducible computational analyses for qualitative biological networks. Front. Physiol. 9, 680 (2018) https://doi.org/10.3389/fphys.2018.00680

36.

Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973–989 (1987)CrossRef

37.

Pérez-Verona, I.C., Tribastone, M., Vandin, A.: A large-scale assessment of exact model reduction in the biomodels repository. In: Computational Methods in Systems Biology - 17th International Conference, CMSB 2019, Trieste, Italy, 18–20 September 2019, Proceedings, pp. 248–265 (2019). https://doi.org/10.1007/978-3-030-31304-3_13

38.

Perez-Verona, I.C., Tribastone, M., Vandin, A.: A large-scale assessment of exact lumping of quantitative models in the biomodels repository. Theor. Comput. Sci. (2021). https://doi.org/10.1016/j.tcs.2021.06.026. https://www.sciencedirect.com/science/article/pii/S0304397521003716

39.

Richardson, K.A.: Simplifying boolean networks. Adv. Complex Syst. 8(04), 365–381 (2005)CrossRef

40.

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)

41.

Saadatpour, A., Albert, R., Reluga, T.C.: A reduction method for boolean network models proven to conserve attractors. SIAM J. Appl. Dyna. Syst. 12(4), 1997–2011 (2013)CrossRef

42.

Schwab, J.D., Kühlwein, S.D., Ikonomi, N., Kühl, M., Kestler, H.A.: Concepts in boolean network modeling: what do they all mean? Comput. Struct. Biotechnol. J. 18, 571–582 (2020). https://doi.org/10.1016/j.csbj.2020.03.001. http://www.sciencedirect.com/science/article/pii/S200103701930460X

43.

Shmulevich, I., Dougherty, E.R., Kim, S., Zhang, W.: Probabilistic boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics 18(2), 261–274 (2002)CrossRef

44.

Steggles, L.J., Banks, R., Shaw, O., Wipat, A.: Qualitatively modelling and analysing genetic regulatory networks: a petri net approach. Bioinformatics 23(3), 336–343 (2007)CrossRef

45.

Su, C., Pang, J.: Sequential control of boolean networks with temporary and permanent perturbations. arXiv preprint arXiv:2004.07184 (2020)

46.

Thomas, R.: Regulatory networks seen as asynchronous automata: a logical description. J. Theor. Biol. 153(1), 1–23 (1991)CrossRef

47.

Thomas, R.: Kinetic logic: a Boolean approach to the analysis of complex regulatory systems. In: Proceedings of the EMBO Course “Formal Analysis of Genetic Regulation”, held in Brussels, 6–16 September 1977, vol. 29. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-49321-8

48.

Veliz-Cuba, A.: Reduction of boolean network models. J. Theor. Biol. 289, 167–172 (2011)CrossRef

49.

Wittmann, D.M., Krumsiek, J., Saez-Rodriguez, J., Lauffenburger, D.A., Klamt, S., Theis, F.J.: Transforming boolean models to continuous models: methodology and application to T-cell receptor signaling. BMC Syst. Biol. 3(1), 98 (2009). https://doi.org/10.1186/1752-0509-3-98 CrossRefPubMedPubMedCentral

50.

Zañudo, J.G.T., Albert, R.: An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks. Chaos Interdiscip. J. Nonlinear Sci. 23(2), 025111 (2013). https://doi.org/10.1063/1.4809777

51.

Zhang, R., et al.: Network model of survival signaling in large granular lymphocyte leukemia. Proc. Nat. Acad. Sci. 105(42), 16308–16313 (2008)CrossRef

Titel: Reducing Boolean Networks with Backward Boolean Equivalence
verfasst von: Georgios Argyris
Alberto Lluch Lafuente
Mirco Tribastone
Max Tschaikowski
Andrea Vandin
Verlag: Springer International Publishing
Buch: Computational Methods in Systems Biology
Print ISBN: 978-3-030-85632-8

Electronic ISBN: 978-3-030-85633-5

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-85633-5_1

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"