# Exploring attractor bifurcations in Boolean networks – BMC Bioinformatics

#### ByNikola Beneš, Luboš Brim, Jakub Kadlecaj, Samuel Pastva and David Šafránek

May 11, 2022

We start by formally introducing the modelling framework of parametrised Boolean networks and the notion of attractor bifurcation in such models. More technical details about this topic are discussed in [12] and [46].

### Boolean networks

We consider the standard (non-parametrised) Boolean network (BN) to be given as a regulatory graph of Boolean variables, where each variable has an associated Boolean update function. Formally, we have a finite set of Boolean variables ({mathcal {V}}) (denoted (mathtt {A}, mathtt {B}, ldots)), regulations (R subseteq {mathcal {V}}times {mathcal {V}}), and a family of Boolean update functions ({mathcal {F}} = { F_{mathtt {A}} mid mathtt {A} in {mathcal {V}}}). The signature of each (F_{mathtt {A}}) is determined by the regulatory context ({mathcal {C}}(mathtt {A}) = { mathtt {B} mid (mathtt {B}, mathtt {A}) in R }). Specifically, (F_{mathtt {A}} : { 0, 1 }^{{mathcal {C}}(mathtt {A})} rightarrow { 0, 1 }). Here, the members of ({mathcal {C}}(mathtt {A})) are called regulators of (mathtt {A}), and (mathtt {A}) is then referred to as the regulation target.

The network’s behaviour is represented by its asynchronous state-transition graph. State s of a BN assigns each variable a Boolean value, i.e. (s: {mathcal {V}}rightarrow {0, 1}). Graph’s vertices are then the (2^{|{mathcal {V}}|}) possible states of the BN. The edges of the graph correspond to the asynchronous application of the update functions to the current state. Formally, for every (s rightarrow t) in the graph, there exists a variable (mathtt {A} in {mathcal {V}}) such that (t(mathtt {A}) = F_{mathtt {A}}(s)) and the remaining (mathtt {B} in {mathcal {V}}) are unchanged (i.e. (s(mathtt {B}) = t(mathtt {B}))).

### Example 1

Consider a simple BN with ({mathcal {V}}= { mathtt {A}, mathtt {B}, mathtt {C} }) such that ({mathcal {C}}(mathtt {A}) = { mathtt {A}, mathtt {B}, mathtt {C} }), ({mathcal {C}}(mathtt {B}) = { mathtt {C} }), and ({mathcal {C}}(mathtt {C}) = { mathtt {A} }). Additionally, let (F_{mathtt {A}} = mathtt {A} vee lnot mathtt {B} vee lnot mathtt {C}), (F_{mathtt {B}} = lnot mathtt {C}), and (F_{mathtt {C}} = mathtt {B}). The state-transition graph of this network is shown in Fig. 1 (a).

Notice that the dependence between variables is typically monotonous. For example, an increase in (mathtt {B}) cannot decrease (mathtt {C}); hence we might say that (mathtt {B}) regulates (mathtt {C}) positively. We often graphically represent a BN using its regulatory graph in which we include these observations. For the network in Example 1, such a graph is shown in Fig 1b, with positive regulations (activations) using green and sharp arrow tips, while negative regulations (inhibitions) use flat red arrows.

Furthermore, for every ((mathtt {B}, mathtt {A}) in R), in terms of [52], every regulator (mathtt {B}) is essential (also observable) in (F_{mathtt {A}}). The essentiality of regulators mandates that whenever (mathtt {B}) regulates (mathtt {A}), (mathtt {B}) needs to have a measurable impact on the value of (F_{mathtt {A}}). Formally, there is a state s such that flipping the value of (mathtt {B}) in s also flips the value of (F_{mathtt {A}}(s)).

However, we can further generalise this notion of essentiality. Consider the update function (F_{mathtt {A}} = mathtt {A} vee lnot mathtt {B} vee lnot mathtt {C}). When (mathtt {A} = 1), the value of (F_{mathtt {A}}) does not depend on either (mathtt {B}) or (mathtt {C}). Hence (mathtt {B}) and (mathtt {C}) are not essential in (F_{mathtt {A}}) for (mathtt {A} = 1) (however, they are both essential for (mathtt {A} = 0)). In this fashion, we can list an arbitrary partial state of the BN to further specify the dependence between two variables. For example, we can say that (mathtt {C}) is essential in (F_{mathtt {A}}) for (mathtt {A} = 0) and (mathtt {B} = 1). That is because there is a state s which satisfies this partial assignment (i.e. (s(mathtt {A}) = 0) and (s(mathtt {B}) = 1)), and flipping the value of (mathtt {C}) in s flips the value of (F_{mathtt {A}}(s)). This notion of generalised essentiality will come into play later for parametrised Boolean networks when we discuss how AEON visualises the space of possible update functions.

### Network attractors

In practice, a crucial question of BN modelling is what eventually happens to the network state in the long term. This information can be obtained by studying the network’s attractors. These correspond to the bottom (also terminal) strongly connected components (BSCC) of the state-transition graph. Assuming no transition is delayed indefinitely, these are the regions of the state space where the network eventually stays forever.

Formally, a BSCC is a maximal set of states S such that for all (s in S), the states reachable from s are exactly the set S. Consider the network from Example 1 and its state-transition graph in Fig. 1a. It has one attractor, namely, the set ({ 100, 110, 111, 101 }). Once this set is reached, the network oscillates between these four states forever. In practice, attractors can exhibit different types of behaviour:

• Stability ((odot)) An attractor is stable if it consists of a single state. The network then stays in this state forever. Sometimes, this type of attractor is also called equilibrium or sink.

• Oscillation ((circlearrowleft)) A single cycle of states, such as in our example, is called an oscillating attractor. The length of such a cycle is its period. These attractors are also sometimes called limit cycles or periodic attractors.

• Disorder ((rightleftarrows)) Finally, an attractor is disordered (also aperiodic) if it is neither stable nor oscillating. Even though the network will stay in the attractor forever, it will behave somewhat unpredictably due to the non-determinism of the asynchronous state-transition graph.

Since the network will often have multiple attractors, its long-term behaviour is characterised by a multi-set over these three attractor types ({ odot , circlearrowleft , rightleftarrows }). We call such multi-set a behaviour class, and we denote the set of all possible behaviour classes ({mathfrak {C}}). In Example 1, the network’s behaviour class is only one (circlearrowleft) attractor.

Observe that this notion of behaviour classes follows intuitively from the established bifurcation analysis methodology in continuous dynamical systems  [53]. In the continuous case, attractors are differentiated based on their topological properties in the continuous state space. This distinction naturally leads to the recognition of stable equilibria (single-state attractors), limit cycles (oscillating attractors), and chaos (attractors consisting of disordered trajectories). However, note that the workflow is (to some extent) modular in this regard. If a different classification is desired, assuming a symbolic algorithm to perform this classification based on attractor states exists, it can be used to supplement or completely replace our proposed classification.

### Parametrised Boolean networks

Inferring the exact update functions from experimental data is a complex and error-prone task, which often cannot be performed exactly. This uncertainty can be expressed using logical parameters, leading us to the introduction of parametrised Boolean networks.

A parametrised Boolean network has an associated finite set of parameter names ({mathcal {P}}) (disjoint with ({mathcal {V}})), which parametrise each update function. We use the ({widehat{F}}_{mathtt {A}}) notation for such update functions to differentiate them from their non-parametrised counterparts. The type of each such function is then ({widehat{F}}_{mathtt {A}} : {0, 1}^{{mathcal {C}}(mathtt {A}) cup {mathcal {P}}} rightarrow { 0, 1 }). Hence to obtain the final result, values of both regulators and parameters are considered.

We call each assignment (p: {mathcal {P}}rightarrow {0,1}) a parametrisation. With each parametrised Boolean network, we also associate a set of valid parametrisations P. This set allows us to arbitrarily restrict which parametrisations are considered admissible for the given network. By fixing one such parametrisation (p in P), we obtain a standard non-parametrised Boolean network called a pinstantiation.

In the worst case, the number of unique instantiations can be doubly exponential in the size of ({mathcal {V}}) [54]. It is, therefore, necessary to restrict the set P as much as possible. To do this, we often utilise the monotonicity and essentiality properties that we discussed in relation to the non-parametrised BNs.

Specifically, when we say a regulation is monotonous in a parametrised BN, we mean that for every (p in P), the p-instantiation has this property. Consequently, we can use the visual elements we introduced for non-parametrised regulatory graphs in a parametrised setting as well.

In a non-parametrised BN, we assumed each regulation was essential. In a parametrised BN, we pose no such requirement, as an unknown update function need not always depend on all regulators. Instead, we assume each regulation marked as essential (solid arrow) must be essential in each instantiation, and regulations not denoted as such (dashed arrows) may or may not be employed by valid instantiations.

### Example 2

Let us now consider Example 1, but extended to a parametrised Boolean network in the following way: We add a new regulation ((mathtt {C}, mathtt {C})) without any assumptions about monotonicity or essentiality (drawn in black, with a combined sharp and flat arrow tip). Then, let ({mathcal {P}}= { mathtt {K} }) and ({widehat{F}}_{mathtt {C}} = mathtt {B} wedge (mathtt {K} Rightarrow mathtt {C})). As valid parametrisations P, we naturally consider both (mathtt {K} = 0) and (mathtt {K} = 1). Consequently, (mathtt {K}) effectively switches ({widehat{F}}_{mathtt {C}}) between (mathtt {B}) (as used in Example 1) and (mathtt {B} wedge mathtt {C}). Fig. 2 shows how this influences the state-transition graph and the regulation graph.

As we see in Fig. 2a, even a small change in an update function can drastically alter the attractors of a Boolean network. Knowing when such change occurs and which parametrisations produce similar behaviour is the motivation behind the attractor bifurcation problem.

### Attractor bifurcation in Boolean networks

Given a parametrised Boolean network with a set of valid parametrisations P, the goal of attractor bifurcation analysis is to compute the bifurcation function ({mathcal {A}}: P rightarrow {mathfrak {C}}). For a valid parametrisation (p in P), the function ({mathcal {A}}) provides the behaviour class (i.e. multiplicity of different attractor types) of the corresponding p-instantiation.

Note that such ({mathcal {A}}) is not concerned with the exact states of individual attractors but instead provides a very general overview (in terms of stability, oscillation and disorder) of what is admissible within the given network. In some instances, further investigation into the internal structure of the attractors within each behaviour class may be beneficial (as is also the case for bifurcation analysis in continuous systems). We address this aspect in more detail later in the text.

Overall, we believe bifurcation analysis to be an excellent tool for high-level analysis of the parameter space, which can then guide further experiments. Additionally, as we show in this case study, it can help identify critical network parameters that negatively affect the network’s behaviour.