New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
The role of certain Post classes in Boolean network models of genetic networks

Communicated by Leo P. Kadanoff, University of Chicago, Chicago, IL, July 28, 2003 (received for review September 3, 2002)
Abstract
A topic of great interest and debate concerns the source of order and remarkable robustness observed in genetic regulatory networks. The study of the generic properties of Boolean networks has proven to be useful for gaining insight into such phenomena. The main focus, as regards ordered behavior in networks, has been on canalizing functions, internal homogeneity or bias, and network connectivity. Here we examine the role that certain classes of Boolean functions that are closed under composition play in the emergence of order in Boolean networks. The closure property implies that any gene at any number of steps in the future is guaranteed to be governed by a function from the same class. By means of Derrida curves on random Boolean networks and percolation simulations on square lattices, we demonstrate that networks constructed from functions belonging to these classes have a tendency toward ordered behavior. Thus they are not overly sensitive to initial conditions, and damage does not readily spread throughout the network. In addition, the considered classes are significantly larger than the class of canalizing functions as the connectivity increases. The functions in these classes exhibit the same kind of preference toward biased functions as do canalizing functions, meaning that functions from this class are likely to be biased. Finally, functions from this class have a natural way of ensuring robustness against noise and perturbations, thus representing plausible evolutionarily selected candidates for regulatory rules in genetic networks.
Mathematical and computational modeling is becoming increasingly important for understanding the complex dynamical interactions in genetic regulatory systems. In light of recent development of highthroughput genomic technologies, modeling efforts have the potential to move from theory into practice. The understanding of the underlying mechanisms used by genetic networks not only sets the stage for a systematic view of physiology and pathophysiology but also carries tremendous practical potential in the context of model inference from real measurement data. Because the implications of the logic of genetic networks are difficult to deduce solely by means of experimental techniques, computational and mathematical modeling play a vital role (1).
Since their inception in 1969 by Kauffman, random Boolean networks (2–5) have been one of the most intensively studied models of discrete dynamical systems, enjoying a sustained interest from both the biology and physics communities. Considering their structural simplicity, these systems are capable of displaying a remarkably rich variety of complex behaviors and share many features of other dynamical system models. Analytical and numerical studies of the relationships between structural organization and dynamical behavior of Boolean networks have yielded important insights into the overall behavior of large genetic networks (5), evolutionary principles (6–8), and the development of chaos (9, 10).
Of particular interest are the relationships between local properties of the network and its global behavior. Various parameters specifying these local properties can be “tuned” such that the network is operating in one of several different regimes. In the ordered regime, the system behaves in a simple way, with most of its components being frozen. In this regime, the transfer of information between the components is impeded by large walls of frozen components. In the chaotic regime, the system behaves in the opposite way, with a perturbation of one component propagating to many others in an avalanchelike manner, with only a few isolated islands comprised of frozen components. Thus, networks in the chaotic regime are very sensitive to initial conditions and perturbations. The boundary between order and chaos is called the complex regime or the critical phase, with the networks undergoing a kind of phase transition (11). It is in this regime that the networks are most evolvable. Kauffman (5) argues that life must exist on the edge of chaos such that the networks representing real genetic regulatory networks operate at or near this critical phase. As Kauffman (12) puts it, “a living system must first strike an internal compromise between malleability and stability. To survive in a variable environment, it must be stable to be sure, but not so stable that it remains forever static.”
A Boolean network contains n elements (genes) {x_{1},..., x_{n}}. Each gene x_{i} ∈ {0, 1} (i = 1,..., n) is a binary variable, the value of which at time t + 1 is completely determined by the values of some other genes x_{j}_{1}_{(}_{i}_{)}, x_{j}_{2}_{(}_{i}_{)},..., x_{j}_{k}_{i}_{(i)} at time t by means of a Boolean function f_{i}:{0, 1}^{k}_{i} → {0, 1}. That is, there are k_{i} genes assigned to gene x_{i} and the mapping j_{k}:{1,..., n} → {1,..., n}, k = 1,..., k_{i} determines the “wiring” of gene x_{i}. Thus, we can write x_{i}(t + 1) = f_{i}(x_{j}_{1}_{(}_{i}_{)}(t), x_{j}_{2}_{(}_{i}_{)}(t),..., x_{j}_{k}_{i}_{(}_{i}_{)}(t)). All genes are assumed to update synchronously in accordance with the functions assigned to them, and this process is then repeated. In a random Boolean network, the functions f_{i} are selected randomly, as are the genes used as its inputs.
Let us briefly consider several properties known to have an impact on the mode of operation of Boolean networks. The first two are the connectivity K and the function bias p. K = n^{–1} k_{i} is the mean number of input variables used by the random Boolean functions f_{i}. We will assume in the sequel that k_{i} = K for all i = 1,..., n. The bias p of a random function f_{i} is the probability that it takes on the value 1. If p = 0.5, then the function is said to be unbiased. By varying these parameters, the network can be made to undergo a phase transition. For example, in the case of unbiased functions, the critical connectivity is K = 2, meaning that for K > 2, we observe chaotic behavior. In general, for a given bias p, the critical connectivity is equal to K_{c} = [2p(1 – p)]^{–}^{1} (ref. 13). Alternatively, by inverting this equation, a critical bias p_{c} can be found for an arbitrary connectivity K. Strongly biased functions (when p is far away from 0.5) are said to have a high degree of internal homogeneity (8) and are associated with increased order in Boolean networks. It has been known for quite some time that canalizing functions play a role in preventing chaotic behavior (2, 5, 14, 15). A canalizing function is one in which at least one of the input variables is able to determine the value of the output of the function regardless of the other variables. By increasing the percentage of canalizing functions in a Boolean network, one can move closer toward the ordered regime and, depending on the connectivity and the distribution of the number of canalizing variables in the randomly chosen canalizing functions (16), cross the phasetransition boundary. There is also strong evidence that many control rules governing transcription of eukaryotic genes are canalizing when viewed in the Boolean formalism (17).
Internal homogeneity (bias) and canalizing functions are, in fact, quite related. It is known that canalizing functions “prefer” a high degree of internal homogeneity (14). Consider the solidline plots in Fig. 1 a and c. These plots show histograms of the number of canalizing functions of K = 4 and 5 variables, respectively, versus the number of ones in their truth tables. Thus, for example, for K = 4, there are only 8 canalizing functions (of 3,514) that have exactly 8 ones in their truth table. The solidline plots in Fig. 1 b and d show the probability that a randomly generated Boolean function with bias p will be a canalizing function (for K = 4 and 5, respectively). Again, it can be seen that for p = 0.5 and K = 4, this probability is only ≈0.0536 (see ref. 14 for details). This phenomenon lends support to the observed role of canalizing functions in the formation of ordered behavior.
Although it is known that the average connectivity in real genetic networks, especially those of higher Metazoa, is considerably higher than K = 2 (ref. 18), real genetic networks are clearly not chaotic. Thus, a majority of regulatory functions must either be biased or canalizing. Aldana et al. (19) recently posed a profound question regarding canalizing functions. Although it is known that the fraction of canalizing functions is very small as K increases, how (and, we would like to add, why) did evolution select them to act as genetic regulatory rules? The first answer that comes to mind might be that evolution acted, by means of selection, to produce regulatory functions that in their totality would ensure that the overall behavior of the network is not chaotic. We suggest that such a view is somewhat flawed. This would be akin to designing a complex digital circuit to be highly noise and faulttolerant by first designing the whole circuit so that it produces the correct output, then testing to see how noisetolerant it really is, and if it is not, redesigning it again, and repeating this process until a satisfactory circuit is produced. A more reasonable and sustainable approach would be to develop a systematic way to design noise tolerance from the bottom up, for example by building in redundancy, exactly as von Neumann (20) envisioned in 1956. Thus, the issue is not whether evolution acted by means of random selection but what criteria or fitness functions it used to arrive at canalizing rules. As Sawhill and Kauffman (21) write, “canalization would be a natural way to design in robustness against noise and uncertainty.” It thus seems more plausible that evolution acted locally (at the level of regulatory rules) to ensure robustness and reliability, whereas global order came for free, exactly as Kauffman has been asserting.
If canalizing functions indeed were found randomly and then selected, then it must have been quite a difficult task for evolution to find so few needles in such a large haystack. If a different class of functions, much more abundant in number than canalizing functions, could exhibit the same high fitness in terms of robustness and globally ordered behavior, it would have been much more likely for evolution to stumble on and select it. This possibility serves as one of the motivations of this article.
There is another issue, however. Canalizing functions, strictly speaking, constitute a class of functions in the sense that a given function either belongs or does not belong to this class. Biased functions, on the other hand, do not constitute a class. That is, because the definition of bias is a probabilistic one, given a bias 0 < p < 1, any Boolean function can still be generated with a positive probability.¶ Thus, a pbiased random network, meaning one with functions that are all chosen randomly with a bias p, could potentially contain any Boolean function. Nonetheless, pbiased random Boolean networks possess an interesting property when the number, n, of genes is large, which is the case for real genetic regulatory networks.
Consider a transition of the network from state x(t) to state x(t + 1), where x ∈ {0, 1}^{n} is the state vector of genes. Clearly, n Boolean functions are used to make this transition. The same functions then are used again to move from state x(t + 1) to state x(t + 2). This situation corresponds to the socalled quenched network model, meaning that the randomly selected functions are kept the same for the entire future operation of the network. We then could ask the question: What Boolean functions will take us directly from x(t) to x(t + 2)? In other words, what Boolean functions will output x(t + 2) when the input is x(t)? The answer, of course, is the composition of the Boolean functions defining the network. That is, these Boolean functions themselves are used as input variables to the same Boolean functions. Let us give a simple example for illustration.
Example: Suppose we have three genes, x_{1}, x_{2}, and x_{3}. The corresponding three Boolean functions are given by , where addition represents disjunction and multiplication represents conjunction. The superscripts (1) signify that these are onestep functions, meaning that they output x(t + 1) given x(t). Let us compute the twostep functions, where we have skipped several straightforward algebraic steps.∥
When n → ∞, in the quenched model, with every step of the network, each new composition of functions results with high probability in a new Boolean function with even more inputs (taken from time 0). Because more and more functions, which were initially selected at random, are used to form the overall composition function, the latter is also random. This insight was used to propose the socalled annealed model (13), where at each step of the network a completely new random function is selected for each gene. It turns out that the quenched and annealed models exhibit very similar dynamics of state transitions (5, 13).
It is fairly straightforward to show that within the annealed approximation, if the onestep Boolean functions are random pbiased functions, then the twostep Boolean functions are also random pbiased functions. This is so because the functions at the second step are chosen independently of the state of the network after the first step. Clearly, by induction, this implies that threestep functions and beyond are all pbiased as well. Thus, it could be said that within the annealed approximation, pbiased functions have a type of closure property in the sense that compositions of pbiased random functions themselves are pbiased random functions. The implication of this result is that in an annealed random Boolean network consisting of pbiased functions, the probability that any given gene is equal to 1 is equal to p at every step of the network. The above pbiased closure property approximately holds true for large n in the quenchedmodel setting.
By contrast, the class of canalizing functions is not closed; that is, a composition of canalizing functions is not necessarily a canalizing function. This implies that a rule specifying a gene value several steps into the future is not necessarily a canalizing rule even if the network consists entirely of canalizing rules. Kauffman (8) recognized this issue and wrote that the necessary condition for such transitivity to hold is that “guaranteed values [of inputs and outputs] must propagate down a connected forcing structure.” In other words, the canalized value of one gene must also be its canalizing value when that gene is used as a canalizing variable in a function determining another gene. Thus, a second motivation of this article is to arrive at a class of Boolean functions that would be closed under composition analogously to the similar property of pbiased annealed networks but without requiring any additional assumptions such as the annealed approximation.
Let us summarize. We are looking for a class of Boolean functions such that:

it is much larger than the class of canalizing functions;

an abundance of functions from this class will tend to prevent chaotic behavior in networks;

it will be “compatible” with internal homogeneity much in the same way as are canalizing functions, meaning that functions from this class are likely to be biased;

functions from this class will have a natural way to ensure robustness against noise and uncertainty; and

it will be closed under the operation of composition, meaning that functions specifying the network state an arbitrary number of time steps into the future will also belong to this class, in the usual quenchedmodel setting.
Post Classes
In 1921, the American mathematician Emil Post (22, 23) characterized all classes of Boolean functions that are closed under composition. Several well known classes of Boolean functions such as monotone, linear, and selfdual functions fall into this category. For example, it is relatively straightforward to show that a composition of an arbitrary number of monotone Boolean functions results in a monotone Boolean function. Of course, the class of all Boolean functions is trivially a Post class as well. However, the class that we will consider is of a somewhat more mysterious nature.
To motivate the definition and make the connection with canalizing functions, recall that a function f:{0,1}^{n} → {0,1} is said to be canalizing if there exists an i ∈ {1,..., n} and u,v ∈ {0,1} such that for all x_{1},..., x_{n} ∈ {0,1}, if x_{i} = u then f(x_{1},..., x_{n}) = v. The input variable x_{i} is called the canalizing variable with canalizing value u and canalized value v. Equivalently, all vectors x ∈ {0,1}^{n} for which f(x) = v̄ must have x_{i} = ū. When u = v = 0, this condition reduces to the Post class,** which we will denote as A^{∞}. Thus, A^{∞} can be defined as follows.
Definition 1: A Boolean function f belongs to class A^{∞} if all vectors on which the function takes on the value 1 have a common component equal to 1. Similarly, we define the Post class a^{∞} by replacing ones by zeros in the previous sentence.
For example, the function f(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2}x_{3} belongs to a^{∞}, because all the vectors on which the function is equal to 0, namely (000), (001), and (010) have a common component equal to 0 (the first one). In this example, the first variable is canalizing and u = v = 1. In other words, if x_{1} = 1, then f(x_{1}, x_{2}, x_{3}) = 1. For simplicity, we will also say “f is a^{∞}.” If we denote the set of canalizing functions by C, then it is clear from the above definitions that A^{∞} ∪ a^{∞} ⊆ C. The class A^{μ} is defined as follows.
Definition 2: A Boolean function f belongs to class A^{μ}, μ ≥ 2, if any μ vectors on which the function takes on the value 1 have a common component equal to 1 (some of these μ vectors may be repeated). The class a^{μ} is defined by replacing ones by zeros in the previous sentence.
As an example, the function [1] is A^{2}, because any two vectors on which the function is equal to 1 have a common unity component. It is easy to see that if f is A^{μ}, then it is also A^{ν} for any ν satisfying 2 ≤ ν ≤ μ. A similar result holds for a^{μ}. Thus, these classes are nested with A^{2} (respectively, a^{2}) being the largest and A^{∞} (respectively, a^{∞}) being the smallest. Another interesting result is that if the function f:{0, 1}^{n} → {0, 1} is A^{μ}, then for μ ≥ n it is also A^{∞} (ref. 24).
It is easy to show that if f is A^{μ}, then any collection of m ≤ μ terms in the disjunctive normal form must contain a variable that belongs to each one of those terms. Thus, once again there is an interesting relationship to canalizing functions in the sense that the functions defined by those terms are themselves canalizing functions. For example, if we take any two terms from the function in Eq. 1, such as x_{1}x_{2} + x_{2}x_{3}, then the Boolean function corresponding to these terms is canalizing, with canalizing variable x_{2}.
Because the classes a^{∞}, A^{∞}, a^{μ}, and A^{μ} are all Post classes, they are closed under the operation of composition. This implies that a Boolean network constructed from one of these classes has the remarkable property that any tstep transition function (outputting the gene value t time steps into the future) also belongs to this class much like the property of pbiased annealed networks. Let us now look at the relationship to bias more closely.
Consider Fig. 1 once again and recall that the solidline plots refer to canalizing functions. The dashedline plots in the same figure have been constructed from the class A^{2} ∪ a^{2} for the same number of variables. We can notice a striking similarity between the solid and dashedline plots and can readily conclude that functions from A^{2} or a^{2} are also more likely to be biased, as suggested by the twopeaked histograms in Fig. 1 a and c. Similarly, Fig. 1 b and d show a marked tendency for a pbiased random Boolean function to be either A^{2} or a^{2} with increasing p (dashed line). A similar relationship exists for A^{μ} ∪ a^{μ}, μ > 2. Thus, it seems that the functions in A^{2} or a^{2} behave very similarly to canalizing functions in that they both prefer internal homogeneity. This is promising from the point of view of network behavior in terms of order and chaos. Had the situation been the opposite, namely, if functions in A^{2} or a^{2} were unlikely to be biased, then networks constructed from them would have been more likely to behave chaotically, especially for K > 2. However, before discussing this, let us address the question of the cardinality of these classes, especially as it compares to that of the class of canalizing functions.
Sizes of the Classes
As we discussed earlier, the proposed class of functions should be significantly larger than the class of canalizing functions under typical connectivity of real genetic networks for it to be a more evolutionarily plausible alternative. It is known (19) that the number of canalizing functions of K input variables is upperbounded by 4K · 2^{2}^{K–1}. At the same time, the exact number of A^{2} functions is known to be ψ(K)2^{2}^{K–1}, where the value ψ(K) is related to the number of selfdual monotone Boolean functions with K variables (25). Thus, for us to compare the number of canalizing functions with the number of A^{2} functions, it suffices to compare 4K with ψ(K) from the two formulas shown above. Fig. 2 compares these two values for K = 1,...,7 on a logarithmic scale. It is clear that although 4K is only linear, ψ(K) grows at a superexponential rate.
The cardinality of a^{2} is equal to that of A^{2}. Thus, we can say that the classes A^{2} and a^{2} are asymptotically much larger than the class of canalizing functions. For μ ≥ 3 (including μ = ∞) and K → ∞, we have the asymptotic formula A^{μ} = a^{μ} ∼ K · 2^{2}^{K–1} (ref. 26), which is of the same order as the upper bound for the number of canalizing functions.†† For K = 3, 4, and 5, the exact numbers of canalizing and A^{2} functions are shown in Table 1. The number of A^{2} functions begins to exceed the number of canalizing functions already for K = 5.
Dynamical Behavior of Networks Constructed from the Considered Post Classes
One of our requirements is that networks constructed from functions belonging to the considered Post classes should exhibit a tendency for ordered behavior. We have examined this question from several different points of view.
First, let us consider socalled Derrida curves (13), which are constructed as follows. Let x^{(1)}(t) and x^{(2)}(t) be two randomly chosen states at some time t. The normalized Hamming distance between them is , where ⊕ is addition modulo 2. Then, given a random Boolean network realization, let x^{(1)}(t + 1) and x^{(2)}(t + 1) be the successor states of x^{(1)}(t) and x^{(2)}(t), respectively. Similarly, let ρ(t + 1) be the Hamming distance between these successor states. The Derrida curve consists of plotting ρ(t + 1) versus ρ(t) and averaging over many random networks. If the network is operating in the chaotic regime, then small Hamming distances tend to diverge, and the Derrida curve lies above the main diagonal for small initial Hamming distances. This also implies that small gene perturbations (i.e., nearby states) tend to spread further apart and networks are sensitive to initial conditions, which is a hallmark of chaotic behavior. On the other hand, networks in the ordered regime exhibit convergence for nearby states, with the Derrida curve lying below the main diagonal. The more the Derrida curve lies above the main diagonal for small values of ρ(t), the more chaotic the network is.
Consider Fig. 3, where we have plotted the Derrida curves corresponding to networks constructed from several different classes of functions. In Fig. 3a, the dashdot line plot corresponds to random (and unbiased) Boolean networks for K = 4. As can be seen, the Derrida plot is significantly above the main diagonal for small ρ(t), indicating that K = 4 random Boolean networks behave chaotically. In the same plot, the solid line corresponds to networks constructed from canalizing functions, and the dashed line corresponds to networks constructed from A^{2} and a^{2} functions, also for K = 4. In both cases, these networks behave much less chaotically. In Fig. 3b, we compared the Post classes A^{2}, A^{3}, and A^{4} = A^{∞} for K = 4. It is evident that random networks constructed from A^{3} and A^{4} (which for the case of K = 4 differ only by two functions) exhibit even more ordered behavior than those constructed from A^{2}. This is intuitively clear, because A^{4} is a more restrictive condition than A^{2}. Finally, in Fig. 3c, we compared the behavior of networks constructed from A^{2} functions for K = 3, 4, and 5. As expected, networks with higher values of K behave relatively more chaotically than those with lower values of K.
We also consider the effect of these Post classes on the dynamical behavior of Boolean networks in terms of percolation (28–31). Here we consider genes to be placed on a square lattice. Unlike in random Kauffman networks, where the wiring for each gene is chosen randomly, on a square lattice, every gene receives inputs from its four nearest neighbors via a randomly chosen Boolean function. Thus, K = 4, as considered above. In percolation problems, one typically studies the fraction of points (sites) that must be occupied such that a continuous path of nearest neighbors is formed from one side to the other. Let r be the probability of site occupancy independent of all other sites. A percolation threshold is a critical probability r_{c} at which a spanning cluster of occupied sites suddenly begins to form and propagate infinitely. Thus, for r ≥ r_{c}, a single spanning cluster of occupied sites exists, whereas for r < r_{c}, no spanning cluster exists. The transition from no spanning cluster to a spanning cluster is also a type of phase transition. For example, for the twodimensional squarelattice model, the percolation threshold is r_{c} ≈ 0.592746.
In practice, lattices are finite, and thus the typical approach is to find the probability at which a horizontally (or vertically) spanning cluster emerges. This is done by Monte Carlo simulations with many randomly generated lattices and computing what fraction of those contains a horizontally spanning (percolating) cluster. For Boolean networks on square lattices, instead of varying the occupancy probability r, one can, for instance, vary the bias p of the random Boolean functions. Then, one can select a subset of genes according to some criterion and ask whether those genes percolate through the lattice. For example, to study the dynamical behavior of networks, we can ask whether the set of frozen genes (i.e., genes that eventually stop changing values) forms a percolating cluster through the network. It has been shown that the critical bias p_{c} for Boolean networks on square lattices is approximately equal to 0.72 (14, 29). Thus, if each function in the random Boolean network is biased with p > 0.72, then there exists a percolating cluster of frozen genes; for 0.5 ≤ p < 0.72, such a cluster does not form.‡‡
We can use these ideas to study the dynamical properties of networks constructed from various classes as follows. Rather than varying the bias p of the random Boolean functions, we can vary the probability that a random Boolean function will belong to a given class. For example, we can generate random networks in which 70% of the functions are guaranteed to be canalizing and the other 30% are chosen randomly from the set of all functions. Then, we can repeat this procedure many times and record the fraction of such networks in which a frozen cluster of genes percolates. We have performed such experiments with the classes A^{2}, A^{3}, A^{4} = A^{∞}, A^{2} ∪ a^{2}, and canalizing. The percolation results are shown in Fig. 4. The horizontal axis shows the probability q that a randomly selected function belongs to a given class. The vertical axis shows the fraction of networks for which a frozen cluster of genes percolates through the network.
In the twodimensional squarelattice framework, we can see that the Post classes A^{2}, A^{3}, and A^{4} = A^{∞} behave in the most orderly fashion. Even for ≈60% of functions belonging to one of these classes, the Boolean network is virtually guaranteed to contain a spanning cluster of frozen genes. The situation for canalizing functions is markedly different. Even at q = 1, when all functions are guaranteed to be canalizing, frozen genes percolate only ≈92% of the time. When the networks are constructed from A^{2} or a^{2} functions, they behave more orderly than canalizing networks for the same q.
An interesting observation is that A^{2} networks percolate at a lower value of q than A^{2} ∪ a^{2} networks. Although both classes contain mostly biased functions (as does the class of canalizing functions), the reason behind the more ordered behavior of A^{2} (as well as A^{3} and A^{4}) networks relative to A^{2} ∪ a^{2} networks on the square lattice is rooted in the fact that the former represent a considerably stronger constraint than the latter in terms of “information transfer.” Consider a state x of the lattice that has at least one gene ON (i.e., it is not allzero). If all genes are governed by A^{2} functions, then it follows that all pairs of “parent” states (that is, those states that lead directly to x in one step) must share at least one common gene that is ON. In fact, for every gene that is ON in x, every pair of parent states must share at least one neighbor of that gene that is ON. The same can be said about all pairs of states at exactly two steps before x due to the closure property, and so on. This represents a formidable constraint that does not need to hold for A^{2} ∪ a^{2} networks.
Discussion
Boolean functions from the Post classes that we have considered here represent plausible evolutionarily selected candidates for regulatory rules in genetic networks. These classes are compatible with a number of natural requirements. As we have demonstrated by means of Derrida curves on random Kauffman networks and percolation simulations on square lattices, networks constructed from functions belonging to these classes have a tendency toward ordered behavior. Thus, such networks with connectivity higher than 2, when purely random unbiased networks behave chaotically, can still avoid chaotic behavior. They are not overly sensitive to initial conditions, and damage does not spread throughout the network. On a squarelattice model, such networks exhibit a spanning cluster of frozen genes and isolated islands of twinkling genes that are functionally isolated from each other (5).
These classes, in particular A^{2} and its dual class a^{2}, are significantly larger than the class of canalizing functions for realistic K. In a sense, functions from these classes can be viewed as “softer” versions of canalizing functions. The parameter μ in A^{μ} and a^{μ} then is a way of tuning the canalizing property, with A^{∞} and a^{∞} being the most restrictive classes that, in fact, are subsets of the class of canalizing functions.
These Post classes exhibit the same kind of preference toward biased functions as do canalizing functions. In fact, the two peaks of the histograms in Fig. 1 a and c actually correspond to A^{2} (left peaks) and a^{2} (right peaks). Thus, we can conclude that functions from the Post class A^{2} prefer low bias (toward 0), whereas functions from a^{2} prefer high bias (toward 1). It is tempting to speculate that, because the majority of genes are typically unexpressed under any given condition, the regulatory rules are preponderantly from A^{μ} rather than a^{μ}.
The additional remarkable property of the Post classes that we considered here is the closure property. Any gene at any number of steps in the future is guaranteed to be governed by a function from the same class, much like the composition of pbiased random Boolean functions itself is a pbiased function in the annealed approximation. Canalizing functions do not possess this property. Obviously, this property carries with it a strong constraint and, consequently, a tendency toward ordered behavior in networks. We emphasize that the closure property is intrinsic to Post classes and holds true in the usual quenchedmodel setting. Another interesting implication of the closure property relates to the connection between “model time” and actual physical time. In the context of genetic regulatory networks, Boolean networks, which are discretetime systems, are idealizations of the real continuoustime systems that they represent. For instance, if we were to fit the models to real geneexpression data, we would typically sample the cell system at consecutive points in time (either uniformly or nonuniformly) and use the timeseries data to infer the Boolean functions in the network. Therefore, there is an implicit albeit unspecified mapping between the discretemodel time and the actual physical time of the cells. If genes are regulated by rules belonging to the considered Post classes, then regardless of how many discrete time steps correspond to the actual physical time interval (we emphasize that this mapping need not even be timeinvariant), the overall rule specifying the gene value at the end of the physical time interval still belongs to the same Post class. Thus, the plausibility of the Post classes representing gene regulatory mechanisms does not depend on the relationship between model time and physical time.
But what of robustness against noise and uncertainty? Canalizing functions are good candidates indeed for control networks in the presence of noise or misinformation (21). Are the classes A^{μ} and a^{μ} (μ = 2,..., ∞) really equipped with such a mechanism, which evolution would be inclined to use as a fitness criterion? The problem of reliable computation with unreliable components in the Boolean circuit setting dates back to von Neumann (20). The relevant characteristic of a reliable circuit is redundancy. Intuitively, higher redundancy ensures reliability. The aim is to construct such circuits that, with high probability, can compute the correct function even when their components are noisy.
In the 1960s, it was discovered that the Post classes A^{μ} and a^{μ} play a significant role in the synthesis and reliability of control systems and selfcorrecting circuits (32, 33). These results rest on the concept of basis functions. Any closed class of Boolean functions contains a set of basis functions such that any function in this class can be constructed by iterative composition of these basis functions. For example, because the class of all Boolean functions is a closed class (Post class), one possible set of basis functions is {x · y, x̄} (i.e., conjunction and negation). Thus, any Boolean function can be constructed by repeated composition of these two functions. The basis set for the class A^{2} is {x · ȳ, xy + xz + yz} (24). The second function is the well known majority (or threepoint median) function. These functions are essentially building blocks from which any function in A^{2} can be constructed. By cascading such building blocks a sufficient number of times, in a treelike fashion, it can be shown (33) that any Boolean function can be realized in a reliable manner, meaning that the correct output is guaranteed even when some of the components are faulty. Thus, Post classes A^{μ} and a^{μ} are strongly implicated in faulttolerant Boolean circuit synthesis. It thus can be speculated that evolution used a similar mechanism to give rise to highly resilient and robust genetic networks.
Acknowledgments
We are grateful to Stuart A. Kauffman and Maximino Aldana for careful reading of this manuscript, stimulating discussions, and useful suggestions.
Footnotes

↵† To whom correspondence should be addressed. Email: is{at}ieee.org.

↵¶ We can generate a random Boolean function with bias p by flipping a pbiased coin 2^{n} times and thus filling in the truth table.

↵∥ It is also interesting to note (details not shown) that the threestep functions are equal to the twostep functions . This implies that, regardless of the starting state, a fixedpoint attractor is reached in no more than three steps.

↵** Typically, notation such as 〈A^{∞}〉 is reserved to denote the property of a Boolean function. The original notation used by Post and subsequent authors (24) to denote the set of functions with such a property is, for example, . However, in this article we will simply use the simplified notation such as A^{∞} to denote the set of functions with the property 〈A^{∞}〉.

↵†† There is actually an exact formula for the number of functions in for any number of variables K (27).

↵‡‡ We note that the situation for p < 0.5 is symmetric, and the “polarity” of the bias p for each function can be different. In other words, some functions might be biased up (favoring 1), and some might be biased down (favoring 0).
 Received September 3, 2002.
 Copyright © 2003, The National Academy of Sciences
References
 ↵
 ↵
 ↵
Kauffman, S. A. (1993) The Origins of Order: SelfOrganization and Selection in Evolution (Oxford Univ. Press, New York).
 ↵
Stern, M. D. (1999) Proc. Natl. Acad. Sci. USA 96, 10746–10751.pmid:10485897

Bornholdt, S. & Sneppen, K. (2000) Proc. R. Soc. London Ser. B 266, 2281–2286.
 ↵
 ↵
 ↵
 ↵
Kadanoff, L. P. (2000) Statistical Physics: Statics, Dynamics and Renormalization (World Scientific, Singapore).
 ↵
Kauffman, S. A. (1995) At Home in the Universe (Oxford Univ. Press, New York).
 ↵
 ↵
 ↵
 ↵
Kauffman, S. A. (2000) Investigations (Oxford Univ. Press, New York).
 ↵
 ↵
 ↵
Aldana, M., Coppersmith, S. & Kadanoff, L. P. (2002) in Perspectives and Problems in Nonlinear Science, eds. Kaplan, E., Marsden, J. E. & Sreenivasan, K. R. (Springer, New York), pp. 23–89.
 ↵
von Neumann, J. (1956) in Automata Studies, eds. Shannon, C. E. & McCarthy, J. (Princeton Univ. Press, Princeton), pp. 329–378.
 ↵
Sawhill, B. K. & Kauffman, S. A. (1997) Santa Fe Institute Working Paper 9705038 (Santa Fe Inst., Santa Fe, NM).
 ↵
 ↵
Post, E. (1941) TwoValued Iterative Systems of Mathematical Logic (Princeton Univ. Press, Princeton).
 ↵
Yablonsky, S. V., Gavrilov, G. P. & Kudryavtsev, V. B. (1966) Functions of the Algebra of Logic and Post Classes (Nauka, Moscow).
 ↵
Pogosyan, G., Miyakawa, M., Nozaki, A. & Rosenberg, I. G. (1997) IEICE Trans. Fundam. E80A, 1502–1507.
 ↵
Korshunov, A. D. (1988) Trudy Inst. Mat. (Novosibirsk) 10, 159–204.
 ↵
Iovovich, V. & Kilibarda, G. (1999) Diskret. Mat. 11, 127–138; trans. (1999) Discrete Math. Appl. 9, 593–605.
 ↵
 ↵

Weisbuch, G. & Stauffer, D. (1987) J. Phys. 48, 11–18.
 ↵
 ↵
Muchnik, A. A. & Gindikin, S. G. (1962) Dokl. Akad. Nauk SSSR 144, 1007–1010.
 ↵
Kirienko, G. I. (1964) Probl. Kibernet. 12, 29–37.
Citation Manager Formats
More Articles of This Classification
Biological Sciences
Related Content
 No related articles found.