Preprint 2012-12
Julio Aracena, Jacques Demongeot, Eric Fanchon, Marco Montalva:
On the number of different dynamics in Boolean networks with deterministic update schedules
Abstract:
Deterministic Boolean networks are a type of discrete dynamical systems widely used in the modeling of genetic networks. The dynamics of such systems is characterized by the local activation functions and the update schedule, i.e., the order in which the nodes are updated. In this paper, we address the problem of knowing the different dynamics of a Boolean network when the update schedule is changed. We begin proving that problem about the existence of different dynamics is NP-complete. However, we show that certain structural properties of the interaction digraph are sufficient for guarantee distinct dynamics of a network. In a recent paper the authors define equivalence classes which have the property that all the update schedules of a given class yield the same dynamics. In order to determine the dynamics associated to a network, we develop an algorithm to efficiently enumerate the above equivalence classes by selecting a representative update schedule for each class with a minimum number of blocks. Finally, we run it over the well known Arabidopsis Thaliana network to know the full spectrum of its different dynamics.
This preprint gave rise to the following definitive publication(s):
Julio ARACENA, Jacques DEMONGEOT, Eric FANCHON, Marco MONTALVA: On the number of different dynamics in Boolean networks with deterministic update schedules. Mathematical Biosciences, vol. 242, 2, pp. 188-194, (2013).
Julio ARACENA, Jacques DEMONGEOT, Eric FANCHON, Marco MONTALVA: On the number of update digraphs and its relation with the feedback arc sets and tournaments. Discrete Applied Mathematics, vol. 161, 10-11, pp. 1345-1355, (2013).