nach oben

Natural Computing

Erschienen in:

08.06.2019

Concurrency in Boolean networks

verfasst von: Thomas Chatain, Stefan Haar, Juraj Kolčák, Loïc Paulevé, Aalok Thakkar

Erschienen in: Natural Computing | Ausgabe 1/2020

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 widely used to model the qualitative dynamics of biological systems. Besides the logical rules determining the evolution of each component with respect to the state of its regulators, the scheduling of component updates can have a dramatic impact on the predicted behaviours. In this paper, we explore the use of Read (contextual) Petri Nets (RPNs) to study dynamics of BNs from a concurrency theory perspective. After showing bi-directional translations between RPNs and BNs and analogies between results on synchronism sensitivity, we illustrate that usual updating modes for BNs can miss plausible behaviours, i.e., incorrectly conclude on the absence/impossibility of reaching specific configurations. We propose an encoding of BNs capitalizing on the RPN semantics enabling more behaviour than the generalized asynchronous updating mode. The proposed encoding ensures a correct abstraction of any multivalued refinement, as one may expect to achieve when modelling biological systems with no assumption on its time features.

Vorheriger Artikel Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations

Nächster Artikel Generation and robustness of Boolean networks to model Clostridium difficile infection

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

for readers familiar with Baldan et al. (2001): we will only need this immediate preemption relation \(\leadsto\) here, not the full asymmetric conflict obtained by adding causal precedence

Aracena J (2008) Maximum number of fixed points in regulatory boolean networks. Bull Math Biol 70(5):1398–1409. https://doi.org/10.1007/s11538-008-9304-7 MathSciNetCrossRefMATH

Aracena J, Demongeot J, Goles E (2004) Positive and negative circuits in discrete neural networks. IEEE Trans Neural Netw 15:77–83. https://doi.org/10.1109/TNN.2003.821555 CrossRefMATH

Aracena J, Goles E, Moreira A, Salinas L (2009) On the robustness of update schedules in Boolean networks. Biosystems 97(1):1–8. https://doi.org/10.1016/j.biosystems.2009.03.006 CrossRef

Aracena J, Richard A, Salinas L (2017) Number of fixed points and disjoint cycles in monotone boolean networks. SIAM J Discrete Math 31(3):1702–1725. https://doi.org/10.1137/16M1060868 MathSciNetCrossRefMATH

Baetens J, der Weeën PV, Baets BD (2012) Effect of asynchronous updating on the stability of cellular automata. Chaos Solitons Fractals 45(4):383–394. https://doi.org/10.1016/j.chaos.2012.01.002 CrossRefMATH

Balaguer S, Chatain T, Haar S (2012) A concurrency-preserving translation from time Petri nets to networks of timed automata. Form Methods Syst Des 40(3):330–355. https://doi.org/10.1007/s10703-012-0146-4 CrossRefMATH

Baldan P, Bruni A, Corradini A, König B, Rodríguez C, Schwoon S (2012) Efficient unfolding of contextual Petri nets. TCS 449:2–22. https://doi.org/10.1016/j.tcs.2012.04.046 MathSciNetCrossRefMATH

Baldan P, Corradini A, Montanari U (2001) Contextual Petri nets, asymmetric event structures, and processes. Inf Comput 171(1):1–49. https://doi.org/10.1006/inco.2001.3060 MathSciNetCrossRefMATH

Busi N, Pinna GM (1996) Non sequential semantics for contextual P/T nets. In: Application and theory of Petri nets, lecture notes in computer science, vol 1091, pp 113–132. Springer. https://doi.org/10.1007/3-540-61363-3_7 CrossRef

Chaouiya C (2007) Petri net modelling of biological networks. Brief Bioinf 8(4):210–219. https://doi.org/10.1093/bib/bbm029 CrossRef

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

Chaouiya C, Remy E, Ruet P, Thieffry D (2004) Qualitative modelling of genetic networks: From logical regulatory graphs to standard Petri nets. In: Cortadella J, Reisig W (eds) Applications and theory of Petri nets 2004, 25th international conference, ICATPN 2004, Bologna, Italy, June 21–25, 2004, Proceedings, lecture notes in computer science, vol 3099, pp 137–156. Springer. https://doi.org/10.1007/978-3-540-27793-4_9

Chatain T, Haar S, Jezequel L, Paulevé L, Schwoon S (2014) Characterization of reachable attractors using Petri net unfoldings. In: Computational methods in systems biology, lecture notes in computer science, vol 8859. Springer, pp 129–142. https://doi.org/10.1007/978-3-319-12982-2_10 CrossRef

Chatain T, Haar S, Koutny M, Schwoon S (2015) Non-atomic transition firing in contextual nets. In: Applications and Theory of Petri Nets, Lecture Notes in Computer Science, vol 9115, pp 117–136. Springer. https://doi.org/10.1007/978-3-319-19488-2_6 CrossRef

Chatain T, Haar S, Paulevé L (2018) Boolean networks: beyond generalized asynchronicity. In: Baetens JM, Kutrib M (eds) Cellular automata and discrete complex systems (AUTOMATA 2018), vol 10875. Lecture Notes in Computer Science. Springer, Ghent, pp 29–42. https://doi.org/10.1007/978-3-319-92675-9_3 CrossRef

Chatain T, Paulevé L (2017) Goal-Driven Unfolding of Petri Nets. In: R. Meyer, U. Nestmann (eds.) 28th International Conference on Concurrency Theory (CONCUR 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol 85, pp 18:1–18:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. https://doi.org/10.4230/LIPIcs.CONCUR.2017.18

Cheng A, Esparza J, Palsberg J (1995) Complexity results for 1-safe nets. Theor Comput Sci 147(1&2):117–136. https://doi.org/10.1016/0304-3975(94)00231-7 MathSciNetCrossRefMATH

Collombet S, van Oevelen C, Sardina Ortega JL, Abou-Jaoudé W, Di Stefano B, Thomas-Chollier M, Graf T, Thieffry D (2017) Logical modeling of lymphoid and myeloid cell specification and transdifferentiation. Proc Natl Acad Sci 114(23):5792–5799. https://doi.org/10.1073/pnas.1610622114 CrossRef

Courtiat J, Saïdouni D (1995) Relating maximality-based semantics to action refinement in process algebras. In: Formal description techniques VII, proceedings of the 7th IFIP WG6.1 international conference on formal description techniques, Berne, Switzerland, 1994, IFIP conference proceedings, vol 6, pp 293–308. Chapman & Hall. https://doi.org/10.1007/978-0-387-34878-0_24 CrossRef

Esparza J, Heljanko K (2008) Unfoldings–a partial-order approach to model checking. Springer, BerlinMATH

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

Goss PJE, Peccoud J (1998) Quantitative modeling of stochastic systems in molecular biology by using stochastic Petri nets. Proc Natl Acad Sci 95(12):6750–6755. https://doi.org/10.1073/pnas.95.12.6750 CrossRef

Janicki R, Koutny M (1993) Structure of concurrency. Theor Comput Sci 112(1):5–52. https://doi.org/10.1016/0304-3975(93)90238-O MathSciNetCrossRefMATH

Janicki R, Koutny M (1997) Fundamentals of modelling concurrency using discrete relational structures. Acta Inf 34:367–388. https://doi.org/10.1007/s002360050090 MathSciNetCrossRefMATH

Janicki R, Lauer PE, Koutny M, Devillers RR (1986) Concurrent and maximally concurrent evolution of nonsequential systems. Theor Comput Sci 43:213–238. https://doi.org/10.1016/0304-3975(86)90177-5 MathSciNetCrossRefMATH

Kauffman SA (1969) Metabolic stability and epigenesis in randomly connected nets. J Theor Biol 22:437–467. https://doi.org/10.1016/0022-5193(69)90015-0 CrossRef

Kolčák J, Šafránek D, Haar S, Paulevé L (2018) Parameter space abstraction and unfolding semantics of discrete regulatory networks. Theor Comput Sci. https://doi.org/10.1016/j.tcs.2018.03.009 CrossRefMATH

Mai Z, Liu H (2009) Boolean network-based analysis of the apoptosis network: irreversible apoptosis and stable surviving. J Theor Biol 259(4):760–769. https://doi.org/10.1016/j.jtbi.2009.04.024 MathSciNetCrossRefMATH

Martínez-Sosa P, Mendoza L (2013) The regulatory network that controls the differentiation of t lymphocytes. Biosystems 113(2):96–103. https://doi.org/10.1016/j.biosystems.2013.05.007 CrossRef

Noual M, Sené S (2017) Synchronism versus asynchronism in monotonic boolean automata networks. Nat Comput. https://doi.org/10.1007/s11047-016-9608-8 CrossRef

Palma E, Salinas L, Aracena J (2016) Enumeration and extension of non-equivalent deterministic update schedules in boolean networks. Bioinformatics 32(5):722–729. https://doi.org/10.1093/bioinformatics/btv628 CrossRef

Paulevé L (2017) Reduction of qualitative models of biological networks for transient dynamics analysis. IEEE/ACM Trans Comput Biol Bioinf. https://doi.org/10.1109/TCBB.2017.2749225 CrossRef

Popova-Zeugmann L, Heiner M, Koch I (2005) Time Petri nets for modelling and analysis of biochemical networks. Fundam Inf 67(1):149–162MathSciNetMATH

Remy E, Ruet P, Thieffry D (2008) Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework. Adv Appl Math 41(3):335–350. https://doi.org/10.1016/j.aam.2007.11.003 MathSciNetCrossRefMATH

Richard A (2010) Negative circuits and sustained oscillations in asynchronous automata networks. Adv Appl Math 44(4):378–392. https://doi.org/10.1016/j.aam.2009.11.011 MathSciNetCrossRefMATH

Rodríguez C, Schwoon S (2013) Cunf: a tool for unfolding and verifying Petri nets with read arcs. In: International symposium on automated technology for verification and analysis, pp 492–495. Springer. https://doi.org/10.1007/978-3-319-02444-8_42 CrossRef

Rougny A, Froidevaux C, Calzone L, Paulevé L (2016) Qualitative dynamics semantics for SBGN process description. BMC Syst Biol 10(1):1–24. https://doi.org/10.1186/s12918-016-0285-0 CrossRef

Schwoon S (2014) Mole. http://www.lsv.ens-cachan.fr/~schwoon/tools/mole/. Accessed 6 June 2019

Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. Biosystems 51(3):123–143. https://doi.org/10.1016/S0303-2647(99)00025-8 CrossRef

Steggles LJ, Banks R, Shaw O, Wipat A (2007) Qualitatively modelling and analysing genetic regulatory networks: a Petri net approach. Bioinformatics 23(3):336–343. https://doi.org/10.1093/bioinformatics/btl596 CrossRef

Thieffry D, Thomas R (1995) Dynamical behaviour of biological regulatory networks-II. Immunity control in bacteriophage lambda. Bull Math Biol 57:277–297. https://doi.org/10.1007/BF02460619 CrossRefMATH

Thomas R (1973) Boolean formalization of genetic control circuits. J Theor Biol 42(3):563–585. https://doi.org/10.1016/0022-5193(73)90247-6 CrossRef

Traynard P, Fauré A, Fages F, Thieffry D (2016) Logical model specification aided by model-checking techniques: application to the mammalian cell cycle regulation. Bioinformatics 32(17):i772–i780. https://doi.org/10.1093/bioinformatics/btw457 CrossRef

Vogler W (1995) Fairness and partial order semantics. Inf Process Lett 55(1):33–39. https://doi.org/10.1016/0020-0190(95)00049-I MathSciNetCrossRefMATH

Vogler W (2002) Partial order semantics and read arcs. Theor Comput Sci 286(1):33–63. https://doi.org/10.1016/s0304-3975(01)00234-1 MathSciNetCrossRefMATH

Winkowski J (1998) Processes of contextual nets and their characteristics. Fundam Inf 36(1):71–101MathSciNetCrossRef

Titel: Concurrency in Boolean networks
verfasst von: Thomas Chatain
Stefan Haar
Juraj Kolčák
Loïc Paulevé
Aalok Thakkar
Publikationsdatum: 08.06.2019
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 1/2020
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09748-4

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"

Weitere Artikel der Ausgabe 1/2020

Bionic vision system and its application in license plate recognition

Spiking neural networks modelled as timed automata: with parameter learning

Reversible causal graph dynamics: invertibility, block representation, vertex-preservation

Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations

From electric circuits to chemical networks

Preface