title: Harmonic analysis of Boolean networks: determinative power and perturbations.
abstract: : Consider a large Boolean network with a feed forward structure. Given a probability distribution on the inputs, can one find, possibly small, collections of input nodes that determine the states of most other nodes in the network? To answer this question, a notion that quantifies the determinative power of an input over the states of the nodes in the network is needed. We argue that the mutual information (MI) between a given subset of the inputs X={X1,...,Xn} of some node i and its associated function fi(X) quantifies the determinative power of this set of inputs over node i. We compare the determinative power of a set of inputs to the sensitivity to perturbations to these inputs, and find that, maybe surprisingly, an input that has large sensitivity to perturbations does not necessarily have large determinative power. However, for unate functions, which play an important role in genetic regulatory networks, we find a direct relation between MI and sensitivity to perturbations. As an application of our results, we analyze the large-scale regulatory network of Escherichia coli. We identify the most determinative nodes and show that a small subset of those reduces the overall uncertainty of the network state significantly. Furthermore, the network is found to be tolerant to perturbations of its inputs.
authors: Department of Information Technology and Electrical Engineering, ETH, Zürich, Zürich, Switzerland. heckel@nari.ee.ethz.ch.
authors: Reinhard
authors: R
authors: Heckel
authors: Steffen
authors: S
authors: Schober
authors: Martin
authors: M
authors: Bossert
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Jan;77(1 Pt 1):011901
references: 18351870
references: J Theor Biol. 2002 Oct 7;218(3):331-41
references: 12381434
references: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Aug;72(2 Pt 2):026137
references: 16196674
references: PLoS Comput Biol. 2007 Aug;3(8):e163
references: 17722974
references: PLoS One. 2008 Feb 27;3(2):e1672
references: 18301750
references: Nature. 2004 May 6;429(6987):92-6
references: 15129285
references: Pac Symp Biocomput. 1998;:18-29
references: 9697168
references: Biosystems. 2006 May;84(2):81-90
references: 16384633
references: Proc Natl Acad Sci U S A. 2004 Apr 6;101(14):4781-6
references: 15037758
references: Nature. 1969 Oct 11;224(5215):177-8
references: 5343519
references: J Theor Biol. 1969 Mar;22(3):437-67
references: 5803332