Document Open Access Logo

Non-Deterministic Updates of Boolean Networks

Authors Loïc Paulevé , Sylvain Sené

PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.10.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

Loïc Paulevé
  • Université Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Sylvain Sené
  • Université Publique, Marseille, France

Funding

  • Paulevé, Loïc: French Agence Nationale pour la Recherche (ANR): ANR-FNR project "AlgoReCell" ANR-16-CE12-0034 and ANR project "BNeDiction" ANR-20-CE45-0001.
  • Sené, Sylvain: his salary as a French state agent affiliated to Université Aix-Marseille, Université Toulon, CNRS, LIS, UMR 7020, Marseille, France, and the ANR project "FANs" ANR-18-CE40-0002.

Cite As Get BibTex

Loïc Paulevé and Sylvain Sené. Non-Deterministic Updates of Boolean Networks. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.AUTOMATA.2021.10

Abstract

Boolean networks are discrete dynamical systems where each automaton has its own Boolean function for computing its state according to the configuration of the network. The updating mode then determines how the configuration of the network evolves over time. Many of updating modes from the literature, including synchronous and asynchronous modes, can be defined as the composition of elementary deterministic configuration updates, i.e., by functions mapping configurations of the network. Nevertheless, alternative dynamics have been introduced using ad-hoc auxiliary objects, such as that resulting from binary projections of Memory Boolean networks, or that resulting from additional pseudo-states for Most Permissive Boolean networks. One may wonder whether these latter dynamics can still be classified as updating modes of finite Boolean networks, or belong to a different class of dynamical systems. In this paper, we study the extension of updating modes to the composition of non-deterministic updates, i.e., mapping sets of finite configurations. We show that the above dynamics can be expressed in this framework, enabling a better understanding of them as updating modes of Boolean networks. More generally, we argue that non-deterministic updates pave the way to a unifying framework for expressing complex updating modes, some of them enabling transitions that cannot be computed with elementary and non-elementary deterministic updates.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Program semantics
  • Applied computing → Systems biology
Keywords
  • Natural computing
  • discrete dynamical systems
  • semantics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Julio Aracena. Maximum number of fixed points in regulatory Boolean networks. Bulletin of Mathematical Biology, 70:1398-1409, 2008. URL: https://doi.org/10.1007/s11538-008-9304-7.
  2. Julio Aracena, Eric Fanchon, Marco Montalva, and Mathilde Noual. Combinatorics on update digraphs in Boolean networks. Discrete Applied Mathematics, 159:401-409, 2011. URL: https://doi.org/10.1016/j.dam.2010.10.010.
  3. Julio Aracena, Eric Goles, Andres Moreira, and Lilian Salinas. On the robustness of update schedules in Boolean networks. Biosystems, 97:1-8, 2009. URL: https://doi.org/10.1016/j.biosystems.2009.03.006.
  4. Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené. Complexity of limit-cycle problems in Boolean networks. In Proceedings of the International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'21), volume 12607 of Lecture Notes in Computer Science, pages 135-146. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-67731-2_10.
  5. Thomas Chatain, Stefan Haar, Juraj Kolčák, Loïc Paulevé, and Aalok Thakkar. Concurrency in Boolean networks. Natural Computing, 19(1):91-109, 2020. URL: https://doi.org/10.1007/s11047-019-09748-4.
  6. Thomas Chatain, Stefan Haar, Maciej Koutny, and Stefan Schwoon. Non-atomic transition firing in contextual nets. In Applications and Theory of Petri Nets, volume 9115 of Lecture Notes in Computer Science, pages 117-136. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19488-2_6.
  7. Thomas Chatain, Stefan Haar, and Loïc Paulevé. Boolean Networks: Beyond Generalized Asynchronicity. In Cellular Automata and Discrete Complex Systems (AUTOMATA 2018), volume 10875 of Lecture Notes in Computer Science, pages 29-42, Ghent, Belgium, 2018. Springer. URL: https://doi.org/10.1007/978-3-319-92675-9_3.
  8. Michel Cosnard and Jacques Demongeot. On the definitions of attractors. In Proceedings of the International Symposium on Iteration Theory and its Functional Equations, volume 1163 of Lecture Notes in Mathematics, pages 23-31. Springer, 1985. URL: https://doi.org/10.1007/BFb0076414.
  9. Jacques Demongeot, Eric Goles, Michel Morvan, Mathilde Noual, and Sylvain Sené. Attraction basins as gauges of the robustness against boundary conditions in biological complex systems. PLoS One, 5:e11793, 2010. URL: https://doi.org/10.1371/journal.pone.0011793.
  10. Jacques Demongeot, Mathilde Noual, and Sylvain Sené. Combinatorics of Boolean automata circuits dynamics. Discrete Applied Mathematics, 160:398-415, 2012. URL: https://doi.org/10.1016/j.dam.2011.11.005.
  11. Jacques Demongeot and Sylvain Sené. About block-parallel Boolean networks: a position paper. Natural Computing, 19:5-13, 2020. URL: https://doi.org/10.1007/s11047-019-09779-x.
  12. A. Elena. Robustesse des réseaux d'automates booléens à seuil aux modes d'itération. Application à la modélisation des réseaux de régulation génétique. PhD thesis, Université Grenoble 1 - Joseph Fourier, 2009. URL: https://tel.archives-ouvertes.fr/tel-00447564/document.
  13. Françoise Fogelman, Eric Goles, and Gérard Weisbuch. Transient length in sequential iteration of threshold functions. Discrete Applied Mathematics, 6:95-98, 1983. URL: https://doi.org/10.1016/0166-218X(83)90105-1.
  14. Eric Goles, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. Attractor landscapes in Boolean networks with firing memory: a theoretical study applied to genetic networks. Natural Computing, 19:295-319, 2020. URL: https://doi.org/10.1007/s11047-020-09789-0.
  15. Eric Goles, Pedro Montealegre, and Martín Ríos-Wilson. On the effects of firing memory in the dynamics of conjunctive networks. In Proceedings of the International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA'19), volume 11525 of Lecture Notes in Computer Science, pages 1-19. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-20981-0_1.
  16. Eric Goles and Mathilde Noual. Block-sequential update schedules and Boolean automata circuits. In Proceedings of the International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA'10), pages 41-50. Discrete Mathematics and Theoretical Computer Science, 2010. URL: https://hal.inria.fr/hal-01185498/document.
  17. Eric Goles and Lilian Salinas. Comparison between parallel and serial dynamics of Boolean networks. Theoretical Computer Science, 396:247-253, 2008. URL: https://doi.org/10.1016/j.tcs.2007.09.008.
  18. Alex Graudenzi and Roberto Serra. A new model of genetic networks: the gene protein Boolean network. In Proceedings of the Workshop italiano su vita artificiale e calcolo evolutivo (WIVACE'09), pages 283-291. World Scientific, 2009. URL: https://doi.org/10.1142/9789814287456_0025.
  19. Shuji Ishihara, Koichi Fujimoto, and Tatsuo Shibata. Cross talking of network motifs in gene regulation that generates temporal pulses and spatial stripes. Genes to Cells, 10(11):1025-1038, 2005. URL: https://doi.org/10.1111/j.1365-2443.2005.00897.x.
  20. S. Mangan and U. Alon. Structure and function of the feed-forward loop network motif. Proceedings of the National Academy of Sciences, 100(21):11980-11985, 2003. URL: https://doi.org/10.1073/pnas.2133841100.
  21. John Milnor. On the concept of attractor. Communications in Mathematical Physics, 99:177-185, 1985. URL: https://doi.org/10.1007/978-0-387-21830-4_15.
  22. Mathilde Noual. Updating automata networks. PhD thesis, École normale supérieure de Lyon, 2012. URL: https://tel.archives-ouvertes.fr/tel-00726560/document.
  23. Mathilde Noual and Sylvain Sené. Synchronism versus asynchronism in monotonic Boolean automata networks. Natural Computing, 17:393-402, 2018. URL: https://doi.org/10.1007/s11047-016-9608-8.
  24. Loïc Paulevé, Juraj Kolčák, Thomas Chatain, and Stefan Haar. Reconciling qualitative, abstract, and scalable modeling of biological networks. Nature Communications, 11(1), 2020. URL: https://doi.org/10.1038/s41467-020-18112-5.
  25. François Robert. Discrete iterations: a metric study, volume 6 of Springer Series in Computational Mathematics. Springer, 1986. URL: https://doi.org/10.1007/978-3-642-61607-5.
  26. Guillermo Rodrigo and Santiago F. Elena. Structural discrimination of robustness in transcriptional feedforward loops for pattern formation. PLoS One, 6(2):e16904, 2011. URL: https://doi.org/10.1371/journal.pone.0016904.
  27. Yolanda Schaerli, Andreea Munteanu, Magüi Gili, James Cotterell, James Sharpe, and Mark Isalan. A unified design space of synthetic stripe-forming networks. Nature Communications, 5(1), 2014. URL: https://doi.org/10.1038/ncomms5905.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact