CI²MA - Publications | Preprints

Preprint 2015-08

Julio Aracena, Eduardo Palma, Lilian Salinas:

Enumeration and extension of non-equivalent deterministic update schedules in Boolean networks


Boolean networks (BNs) were introduced by Stuart Kauffman in 1969 to model gene regulatory networks (GRNs). In the original model, the updating scheme was considered to be synchronous due to the difficulty of really knowing the order (if any) in which the nodes of a network update their state values. Since the dynamical behavior is very sensitive, in particular the attractors of the network, against to changes in the updating scheme, it is increasingly common to use different updating rules in the modeling of GRNs to better capture an observed biological phenomenon and thus to obtain more realistic models. In [Aracena, J. et al., "On the robustness of update schedules in Boolean networks", Biosystems, vol. 97, pp. 1-8, (2009)] equivalence classes of deterministic update schedules in Boolean networks that yield exactly the same dynamical behavior of the network were defined according to the interaction digraph associated to the network. In this way, an upper bound of the number of different dynamical behaviors is the number of non-equivalent update schedules, which is usually much less than the total number of deterministic update schedules. We present an efficient algorithm that allows to enumerate all non-equivalent deterministic update schedules for a given interaction digraph. Also, this algorithm works in the case where there is a partial knowledge about the relative order of the updating of the node states. An executable file of the Label algorithm made in Java is available at: url{

Download in PDF format PDF

This preprint gave rise to the following definitive publication(s):

Julio ARACENA, Eduardo PALMA, Lilian SALINAS: Enumeration and extension of non-equivalent deterministic update schedules in Boolean networks. Bioinformatics, vol. 32, 5, pp. 722-729, (2016).