PERTURBATION STABILITY IN VARIABLE K BOOLEAN NETS
Barbara Remic, Metod Škarja,
Igor Jerman
Inštitut Bion, Stegne 21, 1000 Ljubljana
barbara.remic@guest.arnes.si
http:\\www.bion.si
Boolean networks are mathematical models of complex dynamic systems. We analysed homeostasis of variable K networks. It decreases with increasing number of perturbed elements. With constitutive elements perturbed, homeostasis is very low. Perturbations of attractors also turned out to be a very efficient method for exploring the network's state space. Quite a number of new attractors have been found that were not found with the random initial states method.
Boolean networks are mathematical models of complex dynamic systems. This type of systems are e.g. biological systems on various levels of organization (metabolic networks, genetic networks, neural networks, organisms, ecosystems,...).
A Boolean network consists of binary elements, connected with random connections. Each element has assigned a Boolean function, which determines the value of that element, according to the combination of its inputs. For instance, if the combination of inputs is 010011 the Boolean function determines the value of the element to be 0. The number of inputs per element can vary, which is called a variable K. Once the functions and the connections are determined, the initial state of the network (values of elements) is randomly chosen. The values of elements are synchronously updated in discrete time steps, so a network follows a succession of states. We can represent this states with a curve in the state space, which is called a trajectory. Eventually all trajectories run into attractors. Attractors are either point attractors or periodic attractors. All trajectories that converge into the same attractor constitute a basin of attraction. An external perturbation (switching the value of an element) causes a system to leap form one trajectory to another. This trajectory can run into the same attractor or into some other. Attractors define the network's dynamics, that can be either ordered or disordered. Point attractors as well as the short ones and the moderately long periodic ones denote ordered dynamics. The degree of order can be estimated from the number of attractors, their length, their similarity, the size of attractor basin, fraction of frozen elements,...
We realised that previously used models with constant K (Kauffman, 1993, 1996) are less appropriate for modelling real systems, because the number of inputs in real systems is not equal for all elements. A growing number of empirical evidences supports this presumption (Jeong et al. 2000, Kohn 1999, Tavazoie et al. 1999). Independently of a similar research (Fox and Hill, 2001) we introduced a variable K network model that distinguishes in some details from theirs. We also carried out different research and analysis.
3. SPECIFIC IN OUR RESEARCH
Apart from Fox and Hill we also allowed no-input and no-output elements. We assumed, that especially no-input elements markedly influence network dynamics. We confirmed that to be true, since increasing number of no-input or constitutive elements significantly increases dynamic diversity of the system. Dynamic diversity refers to the number and similarity of attractors. In this research we precisely analysed the sources of order. There are two major sources of order in Boolean networks: the first one is the distribution of inputs and the canalising properties of Boolean functions, that together determine a dynamically effective (or relevant) subnetwork, the second one is the complex dynamics itself. Each of these sources of order is accounted approximately for the half of frozen elements (used here as a measure of order) in K=2 networks.
We were interested in how resilient the asymptotic dynamic of networks is to perturbations. In other words - how much homeostatic are attractors. So in the following research we analysed the perturbations of attractors.
4. PERTURBATIONS OF ATTRACTORS
A perturbation means that the value of an element is switched from 0 to 1 or vice versa. So if we perturb a network settled in an attractor, the perturbation hurls the network out from the attractor onto a trajectory which can run into the same, or into some other attractor. How far from attractor the perturbations move the network depends on the number of perturbed elements. We expected that when only one element is perturbed, the networks mostly return into the same attractor, and that when we increase the number of perturbed elements this homeostasis decreases (they fall into other attractors more frequently). We also assumed that perturbations of constitutive elements hurl the network more often into other attractors, since they have stronger influence on network's dynamics.
5. METHODS
We randomly chose an attractor state and perturbed a given number of randomly chosen elements. We perturbed every attractor several hundred times (the number of perturbations depended on the number of attractors in the network), and counted how many times network fell into each of all the discovered attractors. Perturbations were made on all found attractors. We varied the number of perturbed elements, the number of perturbations on one attractor, we also perturbed only no-input (or constitutive) elements. Perturbations of attractors sometimes discovered new attractors, usually in networks with higher numbers of found attractors. We then further perturbed these newly discovered attractors.
6. RESULTS
The average homeostasis in networks with 2 attractors is very diverse, depending on the individual network and its attractors.
The average homeostasis in networks with more than 2 attractors is also quite diverse, though less than in networks with 2 attractors. It depends on the attractors the network has. Some have higher homeostasis than others. Resistance to perturbations is correlated to attractor basin size, the latter we estimated from relative portion of its frequency in random initial states method.
If we perturbe 50 elements this corresponds to a random initial state, so the fractions of attractors also match their relative portions, obtained with random initial states method.
Homeostasis of attractors is very diverse. Attractors with large basins are very resistant to perturbations. Attractors with smaller basins have all very similar homeostasis, despite their somewhat different sizes. Not until 20 elements are perturbed their size becomes discriminating.
Homeostasis of attractors in this network is again very diverse. It is interesting there are pairs of attractors with practically the same homeostasis. Network homeostasis with only constitutive elements perturbed (2 in this case) is very low, compared to other elements perturbed. The portion of returning into the same attractor is only 0.25. It takes 10 perturbations for two attractors with lowest homeostasis, to reach this point of disturbance.
The graph represents different networks with 2 constitutive elements that have different numbers of attractors. Attractors were sorted according to their portions in decreasing manner. Again their homeostasis is very diverse. It is interesting that attractors in a particular network seem to form groups with nearly same homeostasis - like some kind of discrete classes.
7. DISCUSSION AND CONCLUSIONS
The homeostasis of networks decreases with increasing number of perturbed elements. With one element perturbed, the network mostly returns into the same attractor, when the number of perturbed elements increases, the network falls into other attractors more frequently. With constitutive elements perturbed, the network mostly falls into some other attractor. So when constitutive elements are perturbed the homeostasis is significantly lower.
Attractors have very diverse homeostasis, that depends on its basin size. Attractors with large basins have higher homeostasis than attractors with smaller ones. If we arrange attractors within one network according to decreasing homeostasis, they form discrete groups where all members have nearly the same homeostasis.
Perturbations of attractors turned out to be a very efficient method for exploring the network's state space. With perturbations of the previously discovered attractors, new attractors have been found, that were not discovered with the random initial states method. With further perturbations of newly found attractors, some new attractors have been found again. This way we found some new orders of attractors. These clusters of higher order attractors seem to be closely connected, since the new attractors could be found only from the previously discovered ones. Higher order attractors are difficult to find with random searching, probably because they have small, irregularly shaped or fragmented basins, and they find themselves in the vicinity of larger attractors (their influence hides small attractors).
In genetic interpretation of the model no-input elements represent constitutive genes or external factors which influence gene expression. They dictate network's dynamics, since their perturbation usually diverts the network into some other attractor that represents a different gene expression pattern. Another way to divert the network into other attractor is to perturb more elements. This processes would happen during the cell differentiation or some pathological disturbance of normal gene expression pattern (carcinogenesis). This assumption is in accordance with present knowledge about neoplastic transformations of cells. It takes multiple mutations of genes, but only one or few mutations of onkogenes for cells to become transformed.
As all abstract models that represent material systems, this model is devoid of physical forces. So there are no thermodynamic fluxes, that would drive self-organization of the system. The order in these models originates solely from interactions of the elements. Non-equilibrium thermodynamics is therefore not the single source of order in nature.
It seems there are multiple organizational principles in matter. The matter is able to self-organize under favourable conditions. Emergent systems have a new level of organization and new structures that are resistant to perturbations and tend to maintain their own organization. May we assume also that such spontaneous organization and order is a sign of mind within the matter or at least the way to mind?
8. BIBLIOGRAPHY
Fox J.J., Hill C.C. (2001), From topology to dynamics in biochemical networks, Chaos 11, 809-815
Jeong H., Tombor B., Albert R., Oltvai Z.N., Barabasi A.-L. (2000), The large-scale organization of Metabolic Networks, Nature 406, 651-654.
Kauffman S. (1993), Origins of Order : Self-Organization and Selection in Evolution, Oxford , Oxford University Press
Kauffman S. (1996), At Home in the Universe: The Search for the Laws of Self-Organization and Complexity), Oxford , Oxford University Press
Kohn K.W. (1999), Molecular Interaction Map of the Mammalian Cell Cycle Control and DNA Repair Systems, Mol Biol of Cell 10, 2703-2734
Tavazoie S., Hughes J.D., Campbell M.J., Cho R.J., Church G.M. (1999), Systematic determination of genetworkic network architecture, Nature Genetworkics 22, 281-285