Computational core and fixed-point organisation in Boolean networks

Abstract

In this paper, we analyse large random Boolean networks in terms of a constraint satisfaction problem. We first develop an algorithmic scheme which allows to prune simple logical cascades and under-determined variables, returning thereby the computational core of the network. Second we apply the cavity method to analyse number and organisation of fixed points. We find in particular a phase transition between an easy and a complex regulatory phase, the latter one being characterised by the existence of an exponential number of macroscopically separated fixed-point clusters. The different techniques developed are reinterpreted as algorithms for the analysis of single Boolean networks, and they are applied to analysis and in silico experiments on the gene-regulatory networks of baker's yeast (saccaromices cerevisiae) and the segment-polarity genes of the fruit-fly drosophila melanogaster.

29 pages, 18 figures, version accepted for publication in JSTAT

References in corpus (7)

• The Yeast Cell-Cycle Network Is Robustly Designed
• The Bethe lattice spin glass revisited
• Random Boolean Network Models and the Yeast Transcriptional Network
• Genetic networks with canalyzing Boolean rules are always stable
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Higher-order QED corrections to single-W production in electron-positron collisions
• Core percolation and onset of complexity in Boolean networks

Cited by in corpus (10)

• Boolean Delay Equations: A simple way of looking at complex systems
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Finite size corrections to random Boolean networks
• Dynamically selected steady states and criticality in non-reciprocal networks
• Two faces of greedy leaf removal procedure on graphs
• Propagation of external regulation and asynchronous dynamics in random Boolean networks
• Feedback topology and XOR-dynamics in Boolean networks with varying input structure
• Boolean constraint satisfaction problems for reaction networks
• Connected components in networks with higher-order interactions
• Searching for feasible stationary states in reaction networks by solving a Boolean constraint satisfaction problem