Detection of attractors of large Boolean networks via exhaustive enumeration of appropriate subspaces of the state space

BMC Bioinformatics

Nikolaos Berntenis¹  Martin Ebeling¹ 

[1] Non-Clinical-Safety, F. Hoffmann – La Roche AG, Grenzacherstrasse 124, 4070, Basel, Switzerland

关键词: State space;    Regulatory network;    Cycle;    Fixed state;    Attractor;    Boolean network;   

Others  :  1087677
DOI  :  10.1186/1471-2105-14-361

 received in 2013-03-20, accepted in 2013-12-06,  发布年份 2013

【 摘 要 】

Background

Boolean models are increasingly used to study biological signaling networks. In a Boolean network, nodes represent biological entities such as genes, proteins or protein complexes, and edges indicate activating or inhibiting influences of one node towards another. Depending on the input of activators or inhibitors, Boolean networks categorize nodes as either active or inactive. The formalism is appealing because for many biological relationships, we lack quantitative information about binding constants or kinetic parameters and can only rely on a qualitative description of the type “A activates (or inhibits) B”. A central aim of Boolean network analysis is the determination of attractors (steady states and/or cycles). This problem is known to be computationally complex, its most important parameter being the number of network nodes. Various algorithms tackle it with considerable success. In this paper we present an algorithm, which extends the size of analyzable networks thanks to simple and intuitive arguments.

Results

We present lnet, a software package which, in fully asynchronous updating mode and without any network reduction, detects the fixed states of Boolean networks with up to 150 nodes and a good part of any present cycles for networks with up to half the above number of nodes. The algorithm goes through a complete enumeration of the states of appropriately selected subspaces of the entire network state space. The size of these relevant subspaces is small compared to the full network state space, allowing the analysis of large networks. The subspaces scanned for the analyses of cycles are larger, reducing the size of accessible networks. Importantly, inherent in cycle detection is a classification scheme based on the number of non-frozen nodes of the cycle member states, with cycles characterized by fewer non-frozen nodes being easier to detect. It is further argued that these detectable cycles are also the biologically more important ones. Furthermore, lnet also provides standard Boolean analysis features such as node loop detection.

Conclusions

lnet is a software package that facilitates the analysis of large Boolean networks. Its intuitive approach helps to better understand the network in question.

【 授权许可】

   
2013 Berntenis and Ebeling; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

【 参考文献 】

• [1]Kauffman S: Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol 1969, 22:437-467.
• [2]Glass L, Kauffman SA: The logical analysis of continuous non-linear biochemical control networks. J Theor Biol 1973, 103:103-129.
• [3]Thomas R: Boolean formalization of genetic control circuits. J Theor Biol 1973, 42:563-585.
• [4]Thomas R, Thieffry D, Kaufman M: Dynamical behaviour of biological regulatory networks-I. Biological role of feedback loops and practical use of the concept of the loop-characteristic state. Bull Math Biol 1995, 57:247-276.
• [5]Thieffry D, Thomas R: Dynamical behaviour of biological regulatory networks--II. Immunity control in bacteriophage lambda. Bull Math Biol 1995, 57:277-295.
• [6]Thomas R, Richard D’A: Biological Feedback. Boca Raton: CRC Press; 1990.
• [7]Garg A, Xenarios I, Mendoza L, DeMicheli G: Efficient methods for dynamic analysis of genetic networks and in silico gene perturbation experiments. Lect Notes Comput Sci 2007, 4453:62-76.
• [8]Di Cara A, Garg A, De Micheli G, Xenarios I, Mendoza L: Dynamic simulation of regulatory networks using SQUAD. BMC Bioinformatics 2007, 8:462. BioMed Central Full Text
• [9]Gonzalez AG, Naldi A, Sánchez L, Thieffry D, Chaouiya C: GINsim: a software suite for the qualitative modeling, simulation and analysis of regulatory networks. Biosystems 2006, 84(2):91-100.
• [10]Hinkelmann F, Brandon M, Guang B, McNeill R, Blekherman G, Veliz-Cuba A, Laubenbacher R: ADAM: Analysis of Discrete Models of Biological Systems Using Computer Algebra. BMC Bioinformatics 2011, 12:295. BioMed Central Full Text
• [11]Helikar T, Rogers JA: ChemChains: a platform for simulation and analysis of biochemical networks aimed to laboratory scientists. BMC Syst Biol 2009, 3:58. BioMed Central Full Text
• [12]Müssel C, Hopfensitz M, Kestler HA: BoolNet an R package for generation, reconstruction and analysis of Boolean networks. Bioinformatics 2010, 26(10):1378-1380.
• [13]Naldi A, Remy E, Thieffry D, Chaouiya C: Dynamically consistent reduction of logical regulatory graphs. Theor Comput Sci 2011, 412(21):2207-2218.
• [14]Veliz-Cuba A: Reduction of Boolean network models. J Theor Biol 2011, 289C:167-172.
• [15]Saadatpour A, Albert I, Albert R: Attractor analysis of asynchronous Boolean models of signal transduction networks. J Theor Biol 2010, 266:641-656.
• [16]Saadatpour A, Wang RS, Liao A, Liu X, Loughran TP, Albert I, Albert R: Dynamical and structural analysis of a T cell survival network identifies novel candidate therapeutic targets for large granular lymphocyte leukemia. PLoS Comput Biol 2011, 7(11):e1002267.
• [17]Ay F, Fei X, Kahveci T: Scalable Steady State Analysis of Boolean Biological Regulatory Networks. PLoS ONE 2009, 4(12):e7992.
• [18]Hinkelmann F: Algebraic theory for discrete models in systems biology. Virginia Polytechnic Institute, Mathematics Department; 2011. [PhD thesis]
• [19]Shu-Qin Z, Morihiro H, Tatsuya A, Wai-Ki C, Michael KN: Algorithms for finding small attractors in Boolean networks. EURASIP Journal on Bioinformatics and Systems Biology 2007, 2007:20180.