Logical Reduction of Biological Networks to Their Most Determinative Components.

Boolean networks have been widely used as models for gene regulatory networks, signal transduction networks, or neural networks, among many others. One of the main difficulties in analyzing the dynamics of a Boolean network and its sensitivity to perturbations or mutations is the fact that it grows exponentially with the number of nodes. Therefore, various approaches for simplifying the computations and reducing the network to a subset of relevant nodes have been proposed in the past few years. We consider a recently introduced method for reducing a Boolean network to its most determinative nodes that yield the highest information gain. The determinative power of a node is obtained by a summation of all mutual information quantities over all nodes having the chosen node as a common input, thus representing a measure of information gain obtained by the knowledge of the node under consideration. The determinative power of nodes has been considered in the literature under the assumption that the inputs are independent in which case one can use the Bahadur orthonormal basis. In this article, we relax that assumption and use a standard orthonormal basis instead. We use techniques of Hilbert space operators and harmonic analysis to generate formulas for the sensitivity to perturbations of nodes, quantified by the notions of influence, average sensitivity, and strength. Since we work on finite-dimensional spaces, our formulas and estimates can be and are formulated in plain matrix algebra terminology. We analyze the determinative power of nodes for a Boolean model of a signal transduction network of a generic fibroblast cell. We also show the similarities and differences induced by the alternative complete orthonormal basis used. Among the similarities, we mention the fact that the knowledge of the states of the most determinative nodes reduces the entropy or uncertainty of the overall network significantly. In a special case, we obtain a stronger result than in previous works, showing that a large information gain from a set of input nodes generates increased sensitivity to perturbations of those inputs.

Identification of Biologically Essential Nodes via Determinative Power in Logical Models of Cellular Processes.

A variety of biological networks can be modeled as logical or Boolean networks. However, a simplification of the reality to binary states of the nodes does not ease the difficulty of analyzing the dynamics of large, complex networks, such as signal transduction networks, due to the exponential dependence of the state space on the number of nodes. This paper considers a recently introduced method for finding a fairly small subnetwork, representing a collection of nodes that determine the states of most other nodes with a reasonable level of entropy. The subnetwork contains the most determinative nodes that yield the highest information gain. One of the goals of this paper is to propose an algorithm for finding a suitable subnetwork size. The information gain is quantified by the so-called determinative power of the nodes, which is obtained via the mutual information, a concept originating in information theory. We find the most determinative nodes for 36 network models available in the online database Cell Collective (http://cellcollective.org). We provide statistical information that indicates a weak correlation between the subnetwork size and other variables, such as network size, or maximum and average determinative power of nodes. We observe that the proportion represented by the subnetwork in comparison to the whole network shows a weak tendency to decrease for larger networks. The determinative power of nodes is weakly correlated to the number of outputs of a node, and it appears to be independent of other topological measures such as closeness or betweenness centrality. Once the subnetwork of the most determinative nodes is identified, we generate a biological function analysis of its nodes for some of the 36 networks. The analysis shows that a large fraction of the most determinative nodes are essential and involved in crucial biological functions. The biological pathway analysis of the most determinative nodes shows that they are involved in important disease pathways.

Asynchronous random Boolean network model based on elementary cellular automata rule 126.

This paper considers a simple Boolean network with N nodes, each node's state at time t being determined by a certain number k of parent nodes, which is fixed for all nodes. The nodes, with randomly assigned neighborhoods, are updated based on various asynchronous schemes. We make use of a Boolean rule that is a generalization of rule 126 of elementary cellular automata. We provide formulas for the probability of finding a node in state 1 at a time t for the class of asynchronous random Boolean networks (ARBN) in which only one node is updated at every time step, and for the class of generalized ARBNs (GARBN) in which a random number of nodes can be updated at each time point. We use simulation methods to generate consecutive states of the network for both the real system and the models under the various schemes. The results match well. We study the dynamics of the models through sensitivity of the orbits to initial values, bifurcation diagrams, and fixed point analysis. We show, both theoretically and by example, that the ARBNs generate an ordered behavior regardless of the updating scheme used, whereas the GARBNs have behaviors that range from order to chaos depending on the type of random variable used to determine the number of nodes to be updated and the parameter combinations.

Difference equation for tracking perturbations in systems of Boolean nested canalyzing functions.

This paper studies the spread of perturbations through networks composed of Boolean functions with special canalyzing properties. Canalyzing functions have the property that at least for one value of one of the inputs the output is fixed, irrespective of the values of the other inputs. In this paper the focus is on partially nested canalyzing functions, in which multiple, but not all inputs have this property in a cascading fashion. They naturally describe many relationships in real networks. For example, in a gene regulatory network, the statement "if gene A is expressed, then gene B is not expressed regardless of the states of other genes" implies that A is canalyzing. On the other hand, the additional statement "if gene A is not expressed, and gene C is expressed, then gene B is automatically expressed; otherwise gene B's state is determined by some other type of rule" implies that gene B is expressed by a partially nested canalyzing function with more than two variables, but with two canalyzing variables. In this paper a difference equation model of the probability that a network node's value is affected by an initial perturbation over time is developed, analyzed, and validated numerically. It is shown that the effect of a perturbation decreases towards zero over time if the Boolean functions are canalyzing in sufficiently many variables. The maximum dynamical impact of a perturbation is shown to be comparable to the average impact for a wide range of values of the average sensitivity of the network. Percolation limits are also explored; these are parameter values which generate a transition of the expected perturbation effect to zero as other parameters are varied, so that the initial perturbation does not scale up with the parameters once the percolation limits are reached.

Random Boolean network model exhibiting deterministic chaos.

This paper considers a simple Boolean network with N nodes, each node's state at time t being determined by a certain number of parent nodes, which may vary from one node to another. This is an extension of a model studied by Andrecut and Ali [Int. J. Mod. Phys. B 15, 17 (2001)]], who consider the same number of parents for all nodes. We make use of the same Boolean rule as Andrecut and Ali, provide a generalization of the formula for the probability of finding a node in state 1 at a time t, and use simulation methods to generate consecutive states of the network for both the real system and the model. The results match well. We study the dynamics of the model through sensitivity of the orbits to initial values, bifurcation diagrams, and fixed point analysis. We show that the route to chaos is due to a cascade of period-doubling bifurcations which turn into reversed (period-halving) bifurcations for certain combinations of parameter values.

Sensitivity analysis of biological Boolean networks using information fusion based on nonadditive set functions.

BACKGROUND: An algebraic method for information fusion based on nonadditive set functions is used to assess the joint contribution of Boolean network attributes to the sensitivity of the network to individual node mutations. The node attributes or characteristics under consideration are: in-degree, out-degree, minimum and average path lengths, bias, average sensitivity of Boolean functions, and canalizing degrees. The impact of node mutations is assessed using as target measure the average Hamming distance between a non-mutated/wild-type network and a mutated network. RESULTS: We find that for a biochemical signal transduction network consisting of several main signaling pathways whose nodes represent signaling molecules (mainly proteins), the algebraic method provides a robust classification of attribute contributions. This method indicates that for the biochemical network, the most significant impact is generated mainly by the combined effects of two attributes: out-degree, and average sensitivity of nodes. CONCLUSIONS: The results support the idea that both topological and dynamical properties of the nodes need to be under consideration. The algebraic method is robust against the choice of initial conditions and partition of data sets in training and testing sets for estimation of the nonadditive set functions of the information fusion procedure.

Clinical experience and examination performance: is there a correlation?

CONTEXT: The Liaison Committee on Medical Education (LCME) requires there to be: '...comparable educational experiences and equivalent methods of evaluation across all alternative instructional sites within a given discipline'. It is an LCME accreditation requirement that students encounter similar numbers of patients with similar diagnoses. However, previous empirical studies have not shown a correlation between the numbers of patients seen by students and performance on multiple-choice examinations. OBJECTIVE: This study examined whether student exposure to patients with specific diagnoses predicts performance on multiple-choice examination questions pertaining to those diagnoses. METHODS: The Department of Pediatrics at the University of Nebraska Medical Center has collected patient logbooks from clerks since 1994. These contain information on patient demographics and students' roles in patient care. During week 7 of an 8-week course, students took an examination intended to help them prepare for their final examination. Logbooks and pre-examination questions were coded using standard ICD-9 codes. Data were analysed using Minitab statistical software to determine dependence between patient encounters and test scores. Subjects comprised a convenience sample of students who completed the clerkship during 1997-2000. RESULTS: Our analysis indicates that performance on a multiple-choice examination is independent of the number of patients seen. CONCLUSIONS: Our data suggest knowledge-based examination performance cannot be predicted by the volume of patients seen. Therefore, too much emphasis on examination performance in clinical courses should be carefully weighed against clinical performance to determine the successful completion of clerkships.