Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Cell differentiation is the process whereby stem cells, which can develop into different types, become more and more specialised. A mathematical model of cell differentiation has been recently proposed by Serra et al. [1, 2]. The model is an abstract one (i.e., it does not refer to a specific organism or cell type) and aims at reproducing the most relevant features of cell differentiation, which are the following:

  1. 1.

    there exist different degrees of differentiation that span from totipotent stem cells to fully differentiated cells;

  2. 2.

    there are both deterministic differentiation, where signals trigger the progress of multipotent cells into more differentiated types, in well-defined lineages, and stochastic differentiation, where populations of identical multipotent cells stochastically generate different cell types;

  3. 3.

    limited reversibility: differentiation is almost always irreversible, but there are limited exceptions under the action of appropriate signals;

  4. 4.

    induced pluripotency: fully differentiated cells can come back to a pluripotent state by modifying the expression of some genes;

  5. 5.

    induced change of cell type: modification of the expression of few genes can directly convert one differentiated cell type into another.

The differentiation model is based on a noisy version of a well-known model of gene networks, that is, the Random Boolean Network (RBN) model. In spite of the assumption of discreteness, RBNs have been proven to describe important experimental facts concerning gene expression [3–5]. The dynamics of “classical” RBNs is discrete and synchronous, so fixed points and cycles are the only possible asymptotic states in finite networks; typically, a single RBN owns more than one attractor. Attractors of RBNs are unstable with respect to noise even at low levels, e.g., transient flips of randomly chosen nodes. In fact, even if the flips last for a single time step, one often observes transitions from one attractor to another one. Ribeiro and Kauffman [6] observed that it is possible to identify in the attractors’ landscape subsets of attractors, which they called Ergodic Sets (ESs), which entrap the system in the long time limit, so the system continues to jump between attractors which belong to the set. Unfortunately, it turns out that most noisy RBNs have just one such set: this observation rules out the possibility to associate them with cell types. The model proposed by Serra et al. overcomes this problem by observing that flips are a kind of fairly intense noise, as they amount to silencing an expressed gene or to express a gene which would otherwise be inactive: this event may happen with a very low probability in the cell lifetime. It is possible therefore to introduce a threshold θ, and neglect all the transitions whose occurrence probability is lower than θ. In such a way, the notion of ES has to be modified in that of Threshold Ergodic Set (TES θ ), a set of attractors linked only by jumps having a probability higher than θ, that entrap the system in the long time limit. A TES θ is therefore a subset of attractors which are θ-reachableFootnote 1 from each other, directly or indirectly, and from which no transition can allow escaping. The threshold is related to the level of noise in the cell, and scales with its reciprocal (the frequency of flips) [1]. Hence, cell types are associated with TESs, which represent coherent stable ways of functioning of the same genome even in the presence of noise. According to this framework, RBNs can host more than one TES, avoiding in such a way the problem that hampered the straightforward association of cell types with ES. At high noise level the system can jump among all the attractors, modelling stem cells while, as the threshold is increased (i.e., noise is reduced), the cell becomes entrapped in a smaller TES, that represents a multipotent cell. At very high threshold values all the attractors are also TES, a condition likely to describe final cell types. Indeed, there are experimental indications in favour of the key hypothesis that noise in stem cells is higher than in more differentiated ones. In this model, cell differentiation is an emerging property originating from the interactions of many genes: its main features therefore should be shared by a variety of different organisms.

This single model is able to capture all the phenomena encompassed by cell differentiation and its application to real cell differentiation processes is open to validations.Footnote 2 Nevertheless, the model could be ameliorated in some important aspects. In fact, while for RBNs it is true that the number of TESs increases with the threshold θ, the largest amount of this increase takes place for a very narrow range of values, necessitating in such a way a very sophisticated control to precisely tune the correct threshold for the required differentiation level. This paper presents a way of overcoming this weakness by providing a method for designing Boolean networks (BNs) such that the range of threshold values over which the number of TESs varies is as large as possible.

This contribution is structured as follows. Section 2 details the limitation of the current model and introduces the revision needed to accomplish the proper relation between number of TES and threshold. In Sect. 3, we illustrate the method we used for obtaining such BNs. Section 4 describes the experiments we made and present a statistical analysis of the results. Finally, Sect. 5 summarises the main outcome of this contribution and outlines future work.

2 Improved Model

The mathematical model previously illustrated can capture all the relevant phenomena of cell differentiation. Precise quantitative analyses can be undertaken depending on the availability of experimental data, which unfortunately are scarce and incomplete at the present time. However, the relevance of the model can be assessed in the context of the so-called ensemble approach [7], which aims at finding classes of genetic regulatory network models that match statistical features of living cells. In the case of cell differentiation, the model proposed by Serra et al. succeeds in describing the way in which a lineage tree is hierarchically organised and can also explain the other phenomena involved in the differentiation process from the ensemble approach standpoint. Nevertheless, as already emphasised, it requires a precise control in a very narrow threshold range, resulting in this aspect not completely satisfactory with respect to biological feasibility. In fact, in the ensemble of noisy RBNs considered in the model, the number of TESs varies approximately as a Heaviside step function of θ: one or very few TESs can be found for θ ≤ θ 0 and the maximum number of TESs (equal to the number of attractors) is achieved with θ just above θ 0.Footnote 3 This behaviour is prone to errors in identifying the correct differentiation level within the lineage tree, and therefore biologically not plausible. Therefore, we would like to find an ensemble of BNs such that the main properties characterising RBNs are preserved and the number of TESs scales smoothly with the threshold θ. This goal can be achieved by applying a recently proposed method, which consists in converting the BN design problem into an optimisation one and solve it through stochastic local search (SLS) [8]. This automatic design method has been proven to successfully solve BN design problems [9–11] and will be detailed, for the case at hand, in the following section.

3 Methods

The problem of designing a BN or a set of BNs meeting given dynamical requirements can be stated as an optimisation problem. In particular, one has to define the decision variables and the objective function.Footnote 4 In principle, the optimisation problem can be solved by any search method; however, SLS has been shown to be very effective in tackling these kinds of problems and is thus our preferential choice. For this specific case, we assume that the topology of the network is set initially according to a random model [12] and kept fixed during search. The decision variables of the problem manipulate the Boolean functions of the BN nodes: for BNs with N nodes, each with K inputs, we introduce 2K N Boolean decision variables, which define the transition functions of network nodes. Therefore, the local search can explore the space of all possible assignments of Boolean functions to the nodes, trying to minimise an objective function which estimates the distance between a current BN instance and the requirements posted.

The local search algorithm employed here is an Iterated Local Search (ILS), a well-known SLS framework successfully applied to many hard combinatorial optimisation problems. An outline of the high-level algorithm is given in Algorithm 1. In a nutshell, ILS applies a local search to an initial solution until it finds a local optimum (Line 3); then, it perturbs the solution (Line 5) and it restarts the local search (Line 6). A user-supplied acceptance criterion selects between the current best solution, also called incumbent solution, and the one found by the local search (Line 7). This design makes it possible to combine the efficiency of local search with the capability of escaping from the basins of attraction of local optima. An overview on the theory and applications of ILS can be found in [8, 13].

Algorithm 1 Iterated local search high-level framework

  1:    input: a local search

  2:    s ← generateInitialSolution()

  3:    s ∗ ← localSearch(s)

  4:    while termination conditions not met do

  5:        s′ ← perturbation(s best)

  6:        s′ ls  ← localSearch(s′)

  7:        s ∗ ← acceptanceCriterion(s ∗, s′ ls )

  8:    end while

  9:    return s ∗

Like many metaheuristic frameworks, we must implement problem-specific choices in order to apply ILS to the problem at hand. Following the successful design described in [10], we committed to the following choices to instantiate the ILS framework.

Acceptance criterion::

we accept a new solution if it is better than the incumbent one (extreme intensification).

Perturbation::

for each node function, we perform a single random flip in the truth table. This choice makes ILS not too close to random restart, while keeping the perturbation computationally fast and easy to implement. As a drawback, we will see that local search moves can undo the effects of such a perturbation, albeit unlikely.

A clarification on the perturbation step is needed. In the limit case where the perturbation performed in Line 5 is independent of the incumbent solution s best—for instance, s′ could be randomly generated—ILS would degenerate into a random restart. Our experiments involve networks with input connectivity K = { 2, 3}, therefore the truth tables have either four or eight elements. With such low figures, many more flips in the perturbation step would reduce the correlation between the incumbent solution s best and the perturbed solution s′ too much, thereby making our algorithm a “quasi-random” restart.

The last component to be defined is the embedded local search procedure. We opted for Stochastic Descent (SD), a simple local search in which a neighbour of the current solution is randomly picked and accepted if it is at least as good as the current one. The neighbourhood is implicitly defined by the modifications, or moves, that the current solution may undertake. In our implementation, a move consists in randomly choosing a node, then flipping a bit—chosen at random—in the truth table of its function.

As a final algorithmic remark, we can say that, in a sense, our combination of ILS with SD can be regarded as an iterated version of an adaptive walk in which restart is not random but performed in such a way that diversification is increased gradually.

3.1 Objective Function

The aim of our local search is to find BNs endowed with the two following properties:

  1. 1.

    the number of TESs should grow smoothly with the threshold θ;

  2. 2.

    attractors should be stable, i.e., the probability of transition a → a, where a is an attractor, should be high. This property ensures that we can put into relation the attractors of the BN with the cell types of completely differentiated cells. Some attractors may be sensitive to small perturbations, but the majority should be stable [14].

The objective function closely reflects the requirements mentioned above. In particular, we opted for a linear relation between the number of TESs and the threshold θ, which is the simplest, yet effective choice. The computation of the objective function requires first the calculation of the transition graph, i.e., a directed graph whose vertices V = {v i } are attractors and edges (indicated as e ij ) represent transitions between attractors. Edges are weighted with transition probabilities (weights are denoted as w ij ). The transition graph \(\mathcal{G}(V,E)\) is calculated by the algorithm specified in [2]. The objective function consists of the following two terms:

Attractor stability::

the first contribution to the objective function is given by a term S calculated as the fraction of vertices in \(\mathcal{G}\) with a self-loop with weight greater than or equal to 0. 8. We chose this value in order to aim at stable enough attractors.

$$\displaystyle{ S = \frac{1} {\vert V \vert }\sum \limits _{v_{i}\in V }\left [w_{\mathit{ii}} \geq 0.8\right ]. }$$
(1)

where \(\left [P\right ]\) is the Iverson Bracket and equals to 1 if predicate P is true, 0 otherwise.

Number of TESs as a linear function of θ::

the second term E (E stands for error as we see in Eq. (2)) is calculated as follows: let us select a sequence Θ of n equally spaced values from interval [0, 0. 5[, i.e., \(\varTheta = 0, \frac{1} {2n}, \frac{2} {2n},\ldots, \frac{n-1} {2n}\). Let us also define the sequence s i , 0 ≤ i ≤ n, as the number of \(\mbox{ TES}_{\varTheta _{i}}\) (TESs with threshold Θ i ) in \(\mathcal{G}\). This term is defined as:

$$\displaystyle{ E =\sum \limits _{ i=0}^{n}\left \vert \frac{s_{i}} {s_{n}} - \frac{i} {n}\right \vert. }$$
(2)
Objective function::

the objective function to be minimised is

$$\displaystyle{ (2 - S)E }$$
(3)

Let us motivate our choices. The term S directly reflects the requirement on attractor stability. We should make clear that the resulting networks do not necessarily have transition graphs with self-loops of weight 0. 8, but they are forced to have most of the attractors with this property. Contribute E addresses the first requirement; basically, we ask for a sequence s i that is as smooth as possible, i.e., we want s i to gradually grow to its maximum value s n , the linear growth we are using in this paper being the simplest option among an ampler set of possibilities. In Eq. (2) we divide s i by s n so that E is not dependent on the number of TESs. Finally, the two contributes are composed so that S takes the role of a penalty: the smaller S, the larger the term by which error E is weighted.

The choice of 0. 5 as the maximum threshold value of sequence Θ, although partly arbitrary, is directly related to the first requirement on the stability of network attractors. By definition of transition graph, the sum of the weights of the outgoing edges for each vertex amounts to one. By the first requirement, we seek networks whose transition graphs have self-loops with high weight: this effectively limits the range of weights of the remaining edges.Footnote 5 By this argument, we understand that it is useless to calculate TESs by setting too high a threshold because, ideally, the number of TES θ s should be maximal for θ = 0. 2 and then it should stay constant for threshold values greater than 0. 2. Of course, as remarked above, we cannot guarantee that all transition graphs have self-loops with weight 0. 8 or greater, so we calculate TESs also for threshold values greater than 0. 2.

We conclude this section with some remarks on our design choices. The choice of the specific objective function is being guided by the requirement of obtaining a smooth grow of the number of TESs as threshold θ increases. Since experimental data concerning the functional relation between number of TESs and θ are not available, we opted for a simple linear model. Hence the function used in Eq. (2). However, this function can be changed according to specific hypotheses, so as to have a better fit with given experimental data. Moreover, the choices of some parameters, for example, the values 0.8 (the self-loop desired weight) or 0.5 (the interval length spanned by sequence Θ), are partly arbitrary; evaluating the robustness of our results with respect to variations in these parameters lies beyond the purpose of the present work and will be the aim of further investigations.

Finally, an algorithmic detail. From a graph theoretical point of view, the number of TESs can be calculated as follows: first we remove from \(\mathcal{G}\) all edges with weight less than θ, then we compute the condensation of \(\mathcal{G}\) [15] and count the vertices with null out-degree.

4 Results

Typical RBNs are characterised by constant input connectivity K and Boolean functions chosen at random with on average 2K p true entries in the truth table, where p ∈ [0, 1] is called bias. Depending on the values of K and p the dynamics of RBNs is ordered or disordered (also called chaotic, with a slight abuse of terms). In the first case, the majority of nodes in the attractors is frozen; any moderate-size perturbation is rapidly dampened and the network returns to its original attractor. Conversely, in disordered dynamics, attractor cycles are very long and the system is extremely sensitive to small perturbations: slightly different initial states lead to exponentially diverging trajectories in the state space. RBNs temporal evolution undergoes a second order phase transition between order and chaos, governed by the following relation that defines a curve in the bidimensional space of parameters K and p:

$$\displaystyle{ K_{c} = \frac{1} {2p_{c}(1 - p_{c})} }$$
(4)

where the subscript c denotes the critical values [16]. The curve defined by Eq. (4) separates the ordered from the disordered regime [17]. RBNs whose parameters are chosen along the critical line are the ones that best match living cell features [5, 18].

We tested our algorithm on two test sets, both composed of critical RBNs with N = 100 nodes and constant in-degree. The first test set consists of 30 critical RBNs with in-degree K = 2 (whence p = 0. 5); the second test set contains 30 critical RBNs with in-degree K = 3 (whence p ≈ 0. 788). Networks in these two ensembles constitute the initial solutions of our local search and will be collectively referred to as initial ensemble. Similarly, the set of BNs obtained after running our local search constitutes our optimised ensemble.

In order to compute our objective function we had to compute the transition graph. We initialise the algorithm with attractors found after a sample of 1,000 initial conditions (more attractors may of course be found during algorithm execution and are recursively considered in the algorithm). We considered only trajectories with at most 1,500 steps: if an attractor is not found in this number of steps, the sample is discarded. As for ILS, we set a runtime limit of 3 h per experiment. All experiments were executed on a desktop PC equipped with a Intel Core 2 Quad 2.83 GHz with 8 GB RAM and running Ubuntu Server 10.04; the implementation of the SLS algorithm presented in this paper was written in C++ and was compiled with GCC 4.4.3 with the -O3 optimisation option turned on.

4.1 Analysis of Network Properties

In order to analyse a BN we sampled its state space in 100,000 random initial conditions, since an exhaustive test would be prohibitive. For each network, we recorded the number of attractors, their relative basin sizes and their periods. In addition, we computed the transition graph and the sequence of the number of TESs (actually, the sequence s i as defined in Sect. 3.1).

The first remarkable result is that the number of TESs of the networks designed through our local search smoothly increases with the threshold. A typical case is depicted in Fig. 1, where we can observe that the number of TESs increases within a wide threshold range. The transition graph corresponding to this automatically designed network is drawn in Fig. 2. This property is common to almost all the networks generated by the search procedure and can be considered as an invariant of the ensemble.Footnote 6

Fig. 1
figure 1

Number of TES as a function of the threshold in a random BN (a) and an automatic designed one (b). (a) is the typical plot that characterises RBNs and displays their undesirable features, with respect to the cellular differentiation model, as explained at the end of Sect. 1. (a) A random BN. (b) Automatically designed BN

Full size image
Fig. 2
figure 2

Attractor transition graph for an automatically designed BN

Full size image

Statistics on attractors stability, weights in the transition graph, number of attractors, their relative basin sizes and their periods are summarised by boxplots in Figs. 3, 4 and 5. Boxplots graphically summarise the main statistics of a distribution [19]. The values represented are:

Fig. 3
figure 3

Attractor stability and transitions for initial and optimised BNs in all test sets. (a) and (b) depict the distribution of attractor stability across all networks in either test set; the distribution is constructed by merging all data samples gathered. Data depicted in (c) and (d) characterise the distribution of edge weights in the transition graph as explained in the text. (a) Attractor stability (K = 2). (b) Attractor stability (K = 3). (c) Transitions (K = 2). (d) Transitions (K = 3)

Full size image
Fig. 4
figure 4

Distributions of the number of attractors (a and b) on initial and optimised networks. (a) Number of attractors (K = 2). (b) Number of attractors (K = 3)

Full size image

  • The median (second quartile of the distribution)—line inside the box.

  • The lower quartile (first quartile, Q1)—lowermost side of the box.

  • The upper quartile (third quartile, Q3)—uppermost side of the box.

  • Uppermost and lowermost whiskers are drawn at 1. 5 × (Q3 −Q1), from the first and third quartile, respectively.

  • Outliers (i.e., values lying far from first and third quartile more than 1. 5 × (Q3 −Q1))—open dots.

Each figure depicts the main statistics of a measure on the initial ensemble (left boxplot) and the optimised ensemble (right boxplot) for all test sets.

Fig. 5
figure 5

(a)–(d) summarise the distribution of median attractor period (a and b) and median normalised basin size (c and d), respectively. (a) Attractor periods (K = 2). (b) Attractor periods (K = 3). (c) Attractor basins (K = 2). (d) Attractor basins (K = 3)

Full size image

Figure 3 shows two measures that try to characterise weights of the transition graph and thereby statistically demonstrate the effectiveness of our method in designing BNs with the characteristics stated in Sect. 3.1. The networks’ transition graphs can be represented by a weight matrix \(\boldsymbol{W} = (w_{\mathit{ij}}),0 \leq w_{\mathit{ij}} \leq 1\), where w ij represents the probability of the network to go from attractor i to the basin of attractor j after a random flip; \(w_{\mathit{ij}} = 0 \Leftrightarrow \nexists e_{\mathit{ij}}\). Self-loops weights w ii indicate how insensitive to random flips the attractor i is; in general, we want this probability to be high.

Figure 3a, b describes the distribution of attractor stability in the initial and optimised ensembles. Since we have one stability figure for each attractor for each network, in order to clearly report summaries of our results, we decided to merge together the data for all networks in each ensemble. Figure 3c, d characterises, instead, the distribution of the weights of edges e ij , i ≠ j, i.e., we disregard self-loop. For each BN, we collect in a set P all non-zero elements of \(\boldsymbol{W}\) outside the main diagonal; afterwards, we compute the difference maxP − minP. Figure 3c, d shows the distribution of such differences for the initial and the optimised networks. It can be observed that attractor stability (Fig. 3a, b) is lower but close to the initial ensemble (requirement (1) in Sect. 3.1); at the same time, edge weights w ij , i ≠ j, are more spread out, according to our objective (requirement (2) in Sect. 3.1). We also remark that, for the reasons explained in Sect. 3.1, the quantity minP is rather small, so we actually have maxP − minP ≈ maxP.

Figure 4 depicts the distribution of the number of attractors. As a result of the search process, the number of attractors does not vary in a statistically significant way, although it seems to grow a bit.

Figure 5 shows basin sizes and attractor periods. Since a network can have more than one attractor, a single BN is characterised by a set of attractor periods and basin sizes. To adequately summarise these two statistics, boxplots in Fig. 5 depict the distribution of the median basin size and attractor period calculated on each BN. We observe that attractors’ period does not statistically vary, but the distribution of basin sizes is remarkably different; specifically, the search process tends to shrink basin sizes. Intuitively, we can say that attractors with small basin sizes are likely to be less robust than attractors with larger basin sizes simply because the basins of the latter contain more states. Therefore, one would expect that networks with smaller basins (a feature typical of optimised networks) are also characterised by unstable attractors. However, Fig. 3a, b clearly shows that attractor stability is essentially unchanged. From these data we can conclude that the search process reorganises the basins of the attractors in such a way as to satisfy our stated requirements: the basins are therefore “rebalanced” so as to have generally stable attractors. It appears that, in order to achieve this goal, our local search had to reduce the size of some of the larger basins. This is the motivation why the median stability in Fig. 3a, b slightly decreases (about a 0.2 decrease for networks with K = 2 and a decrement less than 0.1 for networks with K = 3).

5 Conclusion and Future Work

In this paper we have proposed an improvement of a mathematical model for cell differentiation that makes use of RBNs. An ensemble of BNs that match the dynamical requirements deriving from biological plausibility has been designed by means of an optimisation process that uses SLS. The BNs generated are characterised by a more realistic relation between the number of TESs and the threshold, conserving the other relevant properties of the RBN ensemble. In particular, results show that in the ensemble generated by the optimisation process the number of TESs grows smoothly with the threshold and attractors are robust.

Future work will address the extension of the model by introducing in the optimisation process further features of cell differentiation, such as properties concerning deterministic and stochastic differentiation. Furthermore, besides the ensemble approach, we are planning to validate the model against experimental data collected for specific organisms.