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 by proving that the problem of the existence of a pair of update schedules with different dynamics is NP-complete. However, we show that certain structural properties of the interaction digraph are sufficient for guaranteeing distinct dynamics of a network. In [1] 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 this algorithm on the well known Arabidopsis thaliana network to determine the full spectrum of its different dynamics.

Introduction

Deterministic Boolean networks have been introduced in Systems Biology by Kauffman [2], [3] to model the dynamics of genetic networks. In the original scheme all the nodes are updated at each time step, in parallel (this scheme is also called synchronous updating). This kind of updating has given rise to an enormous mathematical literature.

A more general scheme is to consider that the set of network nodes is partitioned into blocks and that the nodes in a block are updated simultaneously, the blocks being considered in a given sequence (block-sequential schedule). This generalizes the previous case because the parallel case corresponds to a single block. It also generalizes the so-called sequential Boolean systems where every node is updated in a defined sequence at every time step.

On different grounds it was realized that the purely synchronous (parallel) updating was not satisfactory for modeling genetic networks and several extensions were proposed in the literature. Gershenson [4] defined the so-called Deterministic Generalized Asynchronous RBNs (DGARBNs), for which a node i is updated if it satisfies an updating condition (depending on two parameters $P_i$ and $Q_i$ associated to the node). When several nodes satisfy their condition simultaneously they are updated synchronously. Gershenson calls this kind of Boolean network semi-synchronous.

Thomas, Thomas et al. and Thomas and Kauffman [5], [6], [7] developed a different approach in which the Boolean model is viewed as an abstraction of a system of piecewise-linear differential equations with diagonal matrix, and is consequently non-deterministic (in the sense that a given state may have several successors). Thomas also introduced time delays and even considered the possibility that these delays may be stochastic, but the occurence of non-determinism is intrinsically linked to the fact that the Boolean model is a discrete abstraction of a dynamical system: the continuous state space is partitioned into rectangular domains, and so is the parameter space. The loss of information induced by the abstraction entails an uncertainty in the successor of a state and the formalism of Thomas is designed to include all the admissible transitions from a state. A transition graph computed with these rules includes all the possible dynamics compatible with a given network architecture (but conversely an arbitrary path from the transition graph does not necessarily represent a valid behavior).

The formalism of Thomas is at first sight quite different from the Boolean networks with deterministic updating rules. It was nevertheless recognized that deterministic synchronous updating can often be recovered as a simplification of the Thomas dynamics [8].

In the present paper we will call Boolean network an entity made of (i) a directed graph (called interaction graph, the nodes of which represent the genes); (ii) an activation function for each node, which specifies the next state of the node given the state of the predecessor nodes; (iii) an update schedule s which specifies the order in which the nodes are updated. In other words the function s defines the ordered partition into blocks of the set of nodes.

In this framework, Aracena et al. [1] proved that two Boolean networks differing only by their update schedules may have exactly the same dynamics. They introduced a new kind of signed digraph, called update digraph, which defines for each arc whether the tail is updated before or after the head of the arc. Equivalence classes of update schedules have been defined on these grounds and the robustness of the dynamics with respect to perturbation of the schedules has been studied. In [9] the combinatorial and algorithmical aspects of update digraphs were studied. In particular bounds on the number of equivalence classes were obtained.

One of the main analytical studies of equivalent update schedules in discrete networks has been made in sequential dynamical systems (SDS) [10], [11]. These systems correspond to networks with sequential schedules and where the connection digraph is symmetric. Reidys [12] characterized the set of equivalent sequential schedules yielding a same dynamical behavior of a given SDS and gave a sharp upper bound for the number of different SDS. In [1] it was proved that these equivalence classes coincide with those defined in this paper in the particular case of SDS. For a more general case of SDS when the update order is a word (the alphabet is the set of nodes) and the interaction graph is a digraph, an upper bound was given in [13]. However, this case does not include the block-sequential update schedule considered in this work.

Our perspective in this paper is the modeling of specific biological phenomena. The problem is thus one of inference: how to infer a Boolean network whose behavior matches the observed behaviors? We will focus here more precisely on the update schedules and their equivalence classes. We showed in [9] that for complete digraphs there is exactly 1 update schedule per class. The architecture of networks encountered in biology is generally rather sparse and in that case a given class may contain many update schedules (thus associated to the same dynamics). This means that the information contained in the dynamics of a system pertains only to the equivalence classes. In other words such observations do not allow to distinguish two update schedules belonging to the same class. Consequently in the context of building models from data it is very important to characterize the classes in order to optimize the inference process. In [14] we give an exact formula for the number of equivalence classes for a large class of digraphs. In the present paper we focus on the enumeration of the equivalence classes of a given digraph.

Section 2 provides the necessary definitions for the sequel. All the schedules belonging to a given class generate the same dynamics, but conversely two different classes are not necessarily associated to different dynamics. Section 3 gives some results related to this issue; first, we point out the difficulty of knowing the different dynamics for a given network, problem that, to our knowledge, has not been studied in depth, yet. More specifically, we prove that the problem of determining whether there exist two different update schedules for a given network such that the associated dynamics are different is, in fact, NP-Complete. We prove a proposition which ensures the existence of different dynamics providing that the corresponding digraph has some structural property. We illustrate this result in the case of a particular family of digraphs where the choice of the activation function of each node can lead to two extreme situations: either all the dynamics are identical or they are all different. We explain how the analysis of update schedules yielding the same dynamics gives us bounds for the number of different dynamics in a given network. At the end of the section it should be clear that large computational savings would be achieved by an efficient algorithm enumerating the equivalence classes compatible with a given network architecture (digraph). In Section 4 we propose such an efficient algorithm.

Finally in Section 5, our theoretical and computational tools are applied to the study of the flower morphogenesis of the plant A. thaliana [15]. More specifically, we work with the reduced model defined by Demongeot et al. [16] which has two non-trivial connected components of 3 and 4 genes. Our results allow us to compute just one update schedule for each equivalence class, instead of enumerating all update schedules, and we show that this entails a significant reduction of the computational work. We are then able to compute the full spectrum of all the different dynamics associated with each component of the A. thaliana network.