# Block-sequential update schedules and Boolean automata circuits.

1 IntroductionFrom the point of view of theoretical biology as well as that of theoretical computer science, it seems to be of great interest to address the question of the number of different asymptotic dynamical behaviours of a regulation network. Close to the 16th Hilbert problem concerning the number of limit cycles of dynamical systems [10], this question has already been considered in a certain number of works [3, 2, 13]. In the same lines and with a similar will to understand the dynamical properties of (regulation) networks, we decided to focus on the dynamics of Boolean automata networks.

Two aspects of these networks caught our attention. The first one is that, as Thomas [15] already noticed, the "driving force" of their dynamics lies in their underlying circuits. Indeed, a network whose underlying interaction graph is an acyclic digraph can only eventually end up in a configuration that will never change over time (aka. fixed point). A network with retroactive loops, on the contrary, exhibits more diverse dynamical behaviour patterns. This is why, before attempting to explain theoretically the dynamics of Boolean automata networks whose interaction graphs are arbitrary, we decided to pay special attention to the simple instance of Boolean automata networks that are Boolean automata circuits (i).

The other essential aspect of Boolean networks, or more generaly, of regulation networks, that we concentrated on is their update schedule, that is, the order according to which the different interactions that define the system occur. Robert [14] highlighted the importance of update schedules on the dynamics of a system. In [7], the focus was put on the parallel update schedule that updates all automata of a network synchronously at each time step of a discretised time scale. Now, although biological knowledge about the precise schedules of gene regulations lack, one may argue reasonably that genes involved in a same cellular physiological function are highly unlikely to perform there regulations in perfect synchrony although biologists seem to agree that a certain amount of synchrony is not, on the whole, implausible. In this paper, we consider a looser version of the parallel update schedule, namely, the general block-sequential schedule that updates every automaton of a network exactly once at every step according to a predefined order but which does not impose that all automata be updated at once. In other words, block-sequential schedules define blocks of automata to be updated sequentially while within the blocks, the automata are updated synchronously.

Section 2 introduces some definitions relative to general Boolean automata networks as well as some preliminary results. Section 3 focuses on Boolean automata circuits and on their dynamics under arbitrary block-sequential update schedules (ii).

2 Networks and their dynamics

We define a Boolean automata network of size n as a couple N = (G, F) where G = (V, A) is a digraph of order [absolute value of V] = n called the interaction graph of the network. The nodes of G are assimilated to the automata of N. Vectors of [{0,1}.sup.n] are seen as configurations of N. Their ith components are the states of nodes i [member of] V. F = {[f.sub.i] : [{0,1}.sup.n] [right arrow] {0,1} | i [member of] V} is the set of local transition functions of the network. For each node i [member of] V, and each configuration x [member of] [{0,1}.sup.n], [f.sub.i](x) depends only on the components [x.sub.j] such that (j, i) [member of] A. For the sake of simplicity, we consider abusingly, in some cases, that [f.sub.i] is a function of arity [deg.sup.-](i) = [absolute value of {j [member of] V | (j, i) [member of] A}| instead of n.

To define the dynamics of N, an update schedule s of the states of nodes needs to be specified. In this paper, we consider only block-sequential update schedules, that is, functions s : V [right arrow] {0, ..., n - 1} such that for any node i [member of] V, s(i) gives the date of update of node [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] between any two time steps t and t + 1. Thus, within a time step t, the states of all nodes are updated exactly once. Without loss of generality, we suppose that update schedules s impose no "waiting period" within a time step: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. The parallel update schedule denoted here by [pi] is the update schedule such that [for all]i [member of] V, [pi](i) = 0. It updates all nodes at once. A sequential update schedule is a block-sequential update schedule s that updates only one node at a time: [for all]i [not equal to] j, s(i) [not equal to] s(j). The number of different update schedules of a set of n elements is known to be exponential in n [6].

Example 2.1 Let V = {0, ..., 5}. The function r : V [right arrow] {0, ..., 5} such that r(2) = 0, r(3) = r(4) = 1 and r(0) = r(1) = r(5) = 2 is a block sequential update schedule. The function s : V [right arrow] {0, ..., 5} such that s(5) = 0, s(3) = 1, s(1) = 2, s(0) = 3, s(2) = 4 and s(4) = 5 is a sequential update schedule. A more practical way of denoting r, s and the parallel update schedule is the following:

r [equivalent to] (2)(3,4)(0,1,5) s [equivalent to] (5)(3)(1)(0)(2)(4) [pi] = (0,1,2,3,4,5).

A network N = (G, F), updated according to a block-sequential update schedule s is denoted by N(s). Its dynamics is defined by the following global transition function:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

where [for all]i [member of] V, [f.sup.s.sub.i] is the local transition function of node i relative to s and is defined by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

In particular, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and the global transition function simplifies to: [F.sup.([pi])](x) = ([f.sub.0](x), ..., [f.sub.n-1](x)). When there is no ambiguity as to what network is being considered, for any initial configuration x [member of] [{0,1}.sup.n], we write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (where [F.sub.s] is composed t times) and when there is no ambiguity either on s, we write x = x(0) and x(t) = [F.sup.t.sub.s](x). With this notation, (1) and (2) mean that [for all]i, j [member of] V such that (j, i) [member of] A, [x.sub.i](t + 1) depends on [x.sub.j](t) if s(j) [greater than or equal to] s(i), and on [x.sub.j](t + 1) if s(j) < s(i).

[FIGURE 1 OMITTED]

For a network N updated with a particular update schedule s, we define a new interaction graph [G.sup.s] = (V, [A.sup.s]), the interaction graph relative to s (see figure 1) such that [A.sup.s] = {(j, i)|[x.sup.s.sub.i](t + 1) depends on [x.sup.s.sub.j](t)}. By an easy induction, this set of arcs can be shown to be equal to:

[A.sup.s] = {(j, i) | there exists in G a directed path {[v.sub.0] = j, [v.sub.1] ..., [v.sub.l] = i}

from j to i such that s(j) [greater than or equal to] s([v.sub.1]) and [for all] 1 [less than or equal to] k < l, s([v.sub.k]) < s([v.sub.k+1])}. (3)

An important point is that when s = [pi], [G.sup.[pi]] = G. Further, define [N.sup.s] = ([G.sup.s], [F.sup.s]) to be the network whose interaction graph is [G.sup.s] and whose set of local transition functions is [F.sup.s] = {[f.sup.s.sub.i] | i [member of] V}. Then, as one may check, the dynamics of [N.sup.s]([pi]) is identical to that of N(s): the global transition functions of both networks are equal to [F.sub.s]. As a result, provided a characterisation of the graphs [G.sub.s], we may bring our study of networks updated with arbitrary block-sequential update schedules back to the study of networks updated in parallel.

The dynamics of a network N updated with an update schedule s is described by its iteration graph I(N(s)) (and also, from the previous paragraph by the iteration graph I([N.sup.s]([pi]))) whose nodes are the configurations of N and whose arcs are the transitions (x(t), x(t + 1)) from one configuration to another. Since the set of configurations of any finite sized network is finite, all trajectories necessarily end up looping, i.e., [for all] x(0) [member of] [{0,1}.sup.n], [there exists],p, x(t + p) = x(t). Attractors of N(s) are orbits of such configurations x(t) for which there exists a p [member of] N such that x(t) = x(t + p). The smallest such p is called the period of the attractor. Attractors of period one are called fixed points.

3 Boolean automata circuits

As mentioned in the introduction, we pay special attention here to a particular instance of Boolean automata networks called Boolean automata circuits [7]. A circuit of size n is a digraph denoted by [C.sub.n] = (V, A). Its set of nodes V = {0,..., n - 1} is identified with Z/nZ so that, considering two nodes i and j, i + j designates the node i + j mod n. The set of arcs of [C.sub.n] is A = {(i, i + 1) | i [member of] Z/nZ}. A Boolean automata circuit is a Boolean automata network whose interaction graph is a circuit. Since any node i in this graph has a unique incoming neighbour, i - 1 , its local transition function [f.sub.i] is either equal to the identity function id : a [member of] {0,1} [??] a or to the negation function neg : a [member of] {0,1} [??] [logical not]a = 1 - a. In the first case, the arc (i - 1, i) is said to be positive and in the second case it is said to be negative. When there is an even number of negative arcs in the circuit, then the the sign of the (Boolean automata) circuit is said to be positive. Otherwise it is said to be negative.

Let C = ([C.sub.n], F) be a Boolean automata circuit of size n whose set of local transition functions is F = {[f.sub.i] | i [member of] Z/nZ}). Let s be an arbitrary block-sequential update schedule of C. For any node i [member of] V, let us note:

[i.sup.*] = max{k < i | s(k) [greater than or equal to] s(k + 1)}.

where the maximum is taken cyclically so that the number of arcs on a path rom [i.sup.*] to i is is minimal. From (3), it holds that [A.sup.s] = {([i.sup.*], i) | i [member of] V} and it can be shown that [for all]i [member of] Z/nZ, [f.sup.s.sub.i] = F[i, [i.sup.*] + 1] where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Following the remarks made in the previous section, the dynamics of C(s) is identical to that of [C.sup.s] (n) = ([C.sup.s.sub.n], [F.sup.s]) where [F.sup.s] = {F[i, [i.sup.*] + 1] | i [member of] Z/nZ}. Let us describe the digraph [C.sup.s.sub.n]. To do this, we first define the inversions of C relative to s:

inv(s) = A \ [A.sup.s] = {(i, i +1) | s(i) < s(i + 1)}.

For nodes of an inversion (i, i + 1), [x.sup.s.sub.i+1](t + 1) depends on [x.sup.s.sub.i](t + 1) instead of [x.sup.s.sub.i](t) as is the case when s(i + 1) [less than or equal to] s(i) and when, in particular, s = [pi]. Obviously, the number of inversions is strictly smaller than n. The only block-sequential update schedule that has no inversions is the parallel update schedule [pi]. From the characterisation of [A.sup.s] given in equation 3, we derive that the nodes [i.sup.*] (i.e., the nodes i [member of] Z/nZ, [there exists]j [member of] Z/nZ, i = [j.sup.*]) form a circuit in [C.sup.s.sub.n] of size n - [absolute value of inv(s)]. The [absolute value of inv(s)] other nodes that do not belong to this circuit depend on one and only one node in it (as in Figure 2). And since the composition of all functions [f.sub.i] is necessarily equal to the composition of all functions F[i, [i.sup.*] + 1], the sign of this circuit is equal to the sign of the original circuit [C.sub.n]. From this description of the network [C.sup.s], we may now derive the following result:

[FIGURE 2 OMITTED]

Proposition 3.1 Let C = ([C.sub.n], F) be a Boolean automata circuit of size n and let s and r be two block-sequential update schedules of C. Then:

(i) The dynamics induced by s, that of C(s), and the dynamics induced by r, that of C(r), are identical if and only if inv(s) = inv(r).

(ii) If inv(s) [not equal to] inv(r), then the dynamics induced by s and by r have no attractor of period p > 1 in common.

(iii) If [absolute value of inv(s)] = k, then for any p [member of] N, C(s) has as many attractors of period p than any Boolean automata circuit of size n - k, of same sign as C and updated with the parallel update schedule.

Proof: (i) follows directly from theorem 1 of [5] and (iii) is derived from the description of the structure of [C.sup.s.sub.n] made in the previous paragraph. To prove (ii), suppose that (i, i + 1) [member of] inv(r) \ inv(s) and that there exists x = [x.sup.s](t) = [x.sup.r](t) [member of] [{0,1}.sup.n] such that [x.sup.s](t + 1) = [x.sup.r] (t + 1). Then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [i.sup.*] = max{k < i | s(k) [greater than or equal to] s(k + 1)} (as above). By the injectivity of F[i + 1, [i.sup.*] + 1], this implies that if [x.sup.s](t + 2) = [x.sup.r] (t + 2) then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Now, if x belongs to an attractor that is induced identically by both s and r, then [for all]t [member of] N, [x.sup.s](t) = [x.sup.r] (t). As result, in this case, [for all]t [member of] N, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (t + 1) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (i.e., the state of node [i.sup.*] is fixed in the attractor). As one can check this leads to states of all nodes being fixed in the attractor which therfore is a fixed point. [there does not exist]

In relation with point (ii) of Proposition 3.1 above, recall that if the dynamics of a network has fixed points for a certain update schedule, then it has the same fixed points for every other update schedule. The important consequence of point (iii) of Proposition 3.1 is that from the results in [7] concerning the number of attractors of Boolean automata circuits updated in parallel, we may derive the number of attractors of each period and in total of any Boolean automata circuit updated with any block-sequential update schedule:

Corollary 3.1 Let C = ([C.sub.n], F) be a Boolean automata circuit of size n and s a block-sequential update schedule of C such that [absolute value of inv(s)] = k:

* If C is positive, then the total number of attractors in the dynamics of C(s) is given by [T.sup.+.sub.p] below. For any integer p, the number of attractors of period p is either 0 if p does not divide n - k or it is [A.sup.+.sub.p]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

* If C is negative, then the total number of attractors in the dynamics of C (s) is given by [T.sup.-.sub.p] below. For any integer p, the number of attractors of period p is either 0 if n - k cannot be written n - k = q x p/2 where q [member of] N is odd, or it is [A.sup.-.sub.p]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Above, [mu] is the Mobius (see [9, 1]) function and V> the Euler totient function.

Following Proposition 3.1, we define the equivalence relation between update schedules that relates r and s if and only if inv(s) = inv(r). [s] denotes the equivalence class of s for this relation. Proposition 3.2 below sums up some results concerning this relation:

Proposition 3.2 Let C = ([C.sub.n], F) be a Boolean automata circuit of size n.

(i) The total number of distinct dynamics induced by the different update schedules of C is [[SIGMA].sup.n-1.sub.k=0] (n/k) = [2.sup.n] - 1.

[FIGURE 3 OMITTED]

(ii) In every class [s], s [not equal to] n, there exists a sequential update schedule. Given the set of inversions of the class, a sequential update schedule can be constructed effectively in O(n) steps.

(iii) Given a set of p > 1 configurations of C, A = {x(0),..., x(p - 1)}, we can determine in O(p * n) steps whether there exists a block-sequential update schedule s such that C(s) has A as an attractor of period p. If such an update schedule exists, with Algorithm 1 below, in O(p x n) steps, we can compute its set of inversions as well as a sequential update schedule inducing the same dynamics.

Algorithm 1: Finding a sequential update schedule that induces a particular attractor of a given Boolean automata circuit if it exists Input: C = ([C.sub.n], F) and A = {x(0),..., x(p - 1)}. begin 1 In O(p x n) steps, compute the set [A.sup.[pi]] = {y(t) = [F.sub.[pi]](x(t - 1)) | 0 [greater than or equal to] t < p}; 2 In O(p x n), compute the set inv = {(i - 1,i | [there exists]t [less than or equal to] p, [x.sub.i](t) [not equal to] [y.sub.i](t)}; 3 In O(n) steps, compute a sequential update schedule s using the set inv; 4 In O(p x n) steps, compute the set [A.sub.s] = {[F.sup.t.sub.s](x(0)) = [x.sup.s](t) | 0 [less than or equal to] t < p} and check that [A.sub.s] = A. If not, then no update schedule induces A as an attractor; 5 Otherwise, output s. end

Proof: Point (i) of Proposition 3.2 above is a direct consequence of points (i) and (ii) of Proposition 3.1 and of the fact that the number of distinct equivalence classes of update schedules with k inversions is (n/k) (i.e., the number of different sets of k inversions).

To prove Point (ii), let us show that for every set of k < n inversions, there exists a sequential update schedule s that satisfies exactly these k inversions. Thus, let inv be a set of |inv| = k inversions and let G = (V, A) be the acyclic digraph whose set of nodes is that of [C.sub.n] (i.e., V = {0,..., n - 1}) and whose set of arcs is A = {(i, i + 1) [member of] inv} U {(i + 1, i) | (i, i + 1) [member of] inv} (in other words, G is obtained by inverting all arcs of [C.sub.n] that belong to inv). Then, any sequential update schedule s whose set of inversions is inv satisfies the following:

[for all](i,j) [member of] A, s(i) > s(i)

so that such a sequential update schedule s can be obtained in linear time using a topological ordering algorithm on digraph G.

Finally, to prove Point (iii) and Algorithm , suppose that s is an existing block-sequential update schedule that induces A as an attractor, i.e., [for all]t < p, [x.sup.s](t + 1) = [f.sup.s.sub.i](x(t)) = x(t + 1). Let us show that its set of inversions inv(s) is necessarily equal to inv. Suppose that (i - 1, i) [??] inv(s). Then, [for all]t < p, [x.sub.i](t + 1) = [x.sup.s.sub.i](t + 1) = [f.sup.s.sub.i](x(t)) = [f.sub.i]([x.sub.i-1](t)) = [y.sub.i](t + 1) and consequently, (i - 1, i) [??] inv. Now, [for all]i [member of] Z/nZ, again, let [i.sup.*] = max{j < i, ([i.sup.*], [i.sup.*] + 1) [??] inv(s)}. It is easy to prove that the state of any node j such that [there exists]i, j = [i.sup.*] necessarily changes in all attractors induced by s and in particular in A. Suppose that (i - 1, i) [member of] inv(s). Let T < p be such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Then, the following holds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

so that [x.sub.i](T + 2) [not equal to] [y.sub.i](T + 2) and consequently (i - 1, i) [member of] inv. [there does not exists]

4 Conclusion

Following the work presented in this paper, we believe that most combinatoric problems concerning the dynamics Boolean automata circuits updated with block-sequential update schedules have now been dealt with. We know the exact value of both the total number of attractors and the number of attractors of period p, [for all]p [member of] N, in the dynamics of positive and negative Boolean automata circuits of any size updated with the synchronous, sequential and the block-sequential update schedules. We also know how many different dynamics can be induced by the set of block-sequential update schedules of a Boolean automata circuit.

One important question, however, remains unanswered: "What are the sizes of the equivalence classes of block-sequential update schedules that yield the same dynamics?". For the very particular cases of [n] and of the classes of update schedules with n - 1 inversions (where n is the size of the circuit) we know that the size of the classes is 1. We also obtained a very intricate formula for the size of classes of update schedules having consecutive inversions only. It implies that the sizes of such classes is exponential as may certainly be that of many other classes. One motive (amongst others) for studying this question follows from A. Elena's work. In his PhD thesis [8], Elena computed statistics of the number of attractors of threshold Boolean automata networks as well as of their periods averaging over all networks (of sizes between 3 and 6) and all update schedules. For both, he found particularly small values. Now, as we have already mentioned, it is known that underlying circuits play an important role in the dynamics of a network with an arbitrary structure. Knowing the answer to this question would help us to understand better the averages found by Elena.

Therefore, beyond this question, we believe that there are two obvious extensions needed of our combinatoric analysis of the dynamics of circuits: one towards more general networks, that is, networks with arbitrary underlying interaction graphs. In line, with [4], this would need to relate the dynamics of arbitrary networks with that of there embedded circuits. The second extension needed is in the direction of other update schedules. Although understanding the dynamics of networks under block-sequential update schedules is a first notable step, these update schedules remain rather unadapted to the modelisation of biological networks. One may indeed argue that it is rather unrealistic that a network updates infallibly every one of its nodes exactly once and according to the exact same order at every time step. It seems more likely, that, on the contrary, some nodes may be updated more often than others and that the updating of nodes may depend on some parameters in a way that cannot be translated by giving an order of update as do block-sequential update schedules.

Acknowledgements

We thank the Basal project-CMM and the Fondecyt 1100003.

References

[1] T. M. Apostol. Introduction to analytic number theory. Springer-Verlag, 1976.

[2] J. Aracena, J. Demongeot, and E. Goles. Fixed points and maximal independent sets in and--or networks. Discrete Applied Mathematics, 138:277-288,2004.

[3] J. Aracena, J. Demongeot, and E. Goles. On limit cycles of monotone functions with symmetric connection graph. Theoretical Computer Science, 322:237-244, 2004.

[4] J. Aracena, J. Demongeot, and E. Goles. Positive and negative circuits in discrete neural networks. IEEE Transactions on Neural Networks, 15:77-83, 2004.

[5] J. Aracena, E. Goles, A. Moreira, and L. Salinas. On the robustness of update schedules in boolean networks. Biosystems, 97, 2009.

[6] J. Demongeot, A. Elena, and S. Sene. Robustness in regulatory networks: a multi-disciplinary approach. Acta Biotheoretica, 56(1-2):27-49, 2008.

[7] J. Demongeot, M. Noual, and S. Sene. On the number of attractors of boolean automata circuits. WAINA, Perth, Australia, 2010. IEEE Press. To appear.

[8] A. Elena. Robustesse des reseaux d'automates booleens a seuil aux modes d'iteration. Application a la modelisation des reseaux de regulation genetique. PhD thesis, Universite Joseph Fourier-Grenoble, 2009.

[9] C. F. Gauss and A. A. (tr.) Clarke. Disquisitiones Arithemeticae. Yale University Press, 1965.

[10] D. Hilbert. Mathematical problems. Bulletin of the American Mathematical Society, 8:437-479, 1902.

[11] W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Journal of Mathematical Biology, 5:115-133, 1943.

[12] M. Noual. On the dynamics of two particular classes of boolean automata networks: Boolean automata circuits and or networks. Technical report, TIMC-IMAG (Grenoble) and CMM (Santiago de Chile), 2009.

[13] A. Richard and J.P. Comet. Necessary conditions for multistationarity in discrete dynamical systems. Discrete Applied Mathematics, 155(18):2403-2413, 2007.

[14] F. Robert. Discrete Iterations. Springer-Verlag, 1986.

[15] R. Thomas. On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations. Springer Series in Synergetics, 9:180-193, 1981.

(i) and which also happen to be a simple instance of threshold Boolean automata networks [11].

(ii) Results presented in this paper and their proofs are detailed in [12].

Eric Goles (1,2) and Mathilde Noual (3,4) ([dagger])

(1) University Adolfo Ibanez, Penalolen, Santiago, Chile

(2) Complex Systems Institute of Valparaiso, ISCV, Valparaiso, Chile

(3) University of Lyon, EENS-Lyon,, LIP, CNRS UMR 5668, F-69007, Lyon,, France

(4) Rhoone-Alpes Complex Systems Institute, IXXI, F-69007, Lyon, France

([dagger]) corresponding author

Printer friendly Cite/link Email Feedback | |

Author: | Goles, Eric; Noual, Mathilde |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 3CHIL |

Date: | Jan 1, 2010 |

Words: | 4495 |

Previous Article: | Probabilistic initial value problem for cellular automaton rule 172. |

Next Article: | The fractal structure of cellular automata on abelian groups. |

Topics: |