Reduction of Boolean network models
Highlights
► A powerful reduction method for Boolean networks is proposed. ► It can help in understanding dynamical properties of large networks. ► It is proven that the reduction method preserves the steady states and topological features. ► Steady states of Boolean models can easily be identified.
Introduction
Boolean networks have been successfully used in modelling gene regulatory networks such as the Drosophila segment polarity network (Albert and Othmer, 2003), the yeast cell-cycle network (Li et al., 2004), the Th regulatory network (Mendoza and Xenarios, 2006) and the lac operon (Veliz-Cuba and Stigler, 2011). Boolean networks provide a nice framework that allows for qualitatively and theoretical analysis.
A Boolean network can be viewed as a function where each fi is a Boolean function. The wiring diagram of a Boolean network is a graph with vertices and an edge from i to j if fj depends on xi (the i-th variable). An edge is positive if ; the edge is negative if the inequality is reversed. If all Boolean functions are unate or biological meaningful functions (Raeymaekers, 2002), then all edges can be given a sign assignment. The dynamics of a Boolean network are given by iteration of f. More precisely, the dynamics of f are given by the state space graph, defined as the graph with vertices in and an edge from to if . In this context, it is of interest to find the steady states ( such that ) and attractors . Other types of updating schemes are sequential and asynchronous. Notice that the state space has vertices.
Since the state space of Boolean networks grows exponentially with the number of nodes, their analysis is not a trivial task. For example, even the problem of finding steady states has been shown to be NP-complete (Zhao, 2005). Many mathematical and computational tools have been proposed to facilitate the analysis of Boolean networks (Gonzalez et al., 2006, Jarrah et al., 2007; Jarrah et al.; Remy and Ruet, 2008, Veliz-Cuba et al., 2010). While these tools allow to answer important questions, such as what the steady states are, it is often not intuitive why such answers were obtained.
In this paper a reduction method for Boolean networks is proposed. The reduction method decreases the size of Boolean networks, while preserving important dynamical properties. The reduced network can help in determining and understanding the dynamical properties of the original Boolean network. We will focus on the existence, number and type of steady states. Also, we will apply our results to analyze Boolean models of biological systems. This paper is organized as follows: in Section 2 we present the reduction method, algorithms and small illustrative examples. Properties of the reduction method are also presented. It is shown that the reduction method preserves steady states and topological features. We apply our results to analyze Boolean models of Th-lymphocyte differentiation and the lac operon in Section 3. We close with a discussion in Section 4.
Section snippets
Reduction steps
We now provide the reduction steps to reduce a Boolean network and its corresponding wiring diagram. The idea behind the reduction method is simple: the wiring diagram and Boolean functions should reflect actual regulation and hence nonfunctional edges and variables should be removed; on the other hand, vertices can be deleted, without losing important information, by allowing its functionality to be “passed on” to other variables.
- (1)
We simplify the Boolean functions and wiring diagram:
- (a)
Reduce
- (a)
Th-lymphocyte differentiation
We now consider the Boolean model presented in Remy et al. (2006). It is a Boolean model for Th-lymphocyte differentiation. Its wiring diagram is given in Fig. 5. The variables and Boolean functions of the model are given in Table 1.
Notice that this Boolean network has states.
Using our reduction algorithm (see Examples 2.1, 2.2) to eliminate the variables we obtain the following reduced model, , with wiring diagram given in Fig. 6 and Boolean functions given in
Discussion
In this paper we have proposed a reduction method that can facilitate the analysis of Boolean networks. The main properties of the reduction method are that it preserves the steady states (Theorem 2.4) and topological features (Theorem 2.6). It is important to mention that a reduction from n to k variables in the wiring diagram causes a reduction from to in the state space; that is, the reduction method decreases the size of the state space exponentially.
We applied the reduction method to
References (15)
- et al.
The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster
J. Theor. Biol.
(2003) - et al.
Mapping multivalued onto Boolean dynamics
J. Theor. Biol.
(2011) - et al.
Reverse-engineering of polynomial dynamical systems
Adv. Appl. Math.
(2007) Dynamics of boolean networks controlled by biologically meaningful functions
J. Theor. Biol.
(2002)- et al.
Ginsim: a software suite for the qualitative modelling, simulation and analysis of regulatory networks
Biosystems
(2006) - Hinkelmann, Franziska, Brandon, Madison, Guang, Bonny, McNeill, Rustin, Blekherman, Grigoriy, Veliz-Cuba, Alan,...
- Jarrah, A., Laubenbacher, R., Vastani, H., DVD: discrete visualizer of dynamics. Available at:...
Cited by (95)
The maximal coordination principle in regulatory Boolean networks
2024, Journal of Computer and System SciencesAn approach to structured multilinear modeling with relaxed Boolean output functions
2023, IFAC-PapersOnLineBilevel integer programming on a Boolean network for discovering critical genetic alterations in cancer development and therapy
2022, European Journal of Operational ResearchCitation Excerpt :Furthermore, our method may be improved by reducing a solution space with graph-theoretic properties of interactions among genes (Naldi, Remy, Thieffry, & Chaouiya, 2011; Samaga et al., 2010; Veliz-Cuba, 2011).
Boolean modelling as a logic-based dynamic approach in systems medicine
2022, Computational and Structural Biotechnology JournalCitation Excerpt :Identifying an attractor in a complex network is challenging. Many reduction techniques were implemented to simplify the original BFs to include a fewer number of operations [58,67,68]. This can be achieved by removing components that do not affect the behaviour of the original BFs.