Principia Cybernetica Web

Kauffman's NK Boolean networks

An NK automaton is an autonomous random network of N Boolean logic elements. Each element has K inputs and one output. The signals at inputs and outputs take binary (0 or 1) values. The Boolean elements of the network and the connections between elements are chosen in a random manner. There are no external inputs to the network. The number of elements N is assumed to be large.

An automaton operates in discrete time. The set of the output signals of the Boolean elements at a given moment of time characterizes a current state of an automaton. During an automaton operation, the sequence of states converges to a cyclic attractor. The states of an attractor can be considered as a "program" of an automaton operation. The number of attractors M and the typical attractor length L are important characteristics of NK automata.

The automaton behavior depends essentially on the connection degree K.

If K is large (K = N), the behavior is essentially stochastic. The successive states are random with respect to the preceding ones. The "programs" are very sensitive to minimal disturbances (a minimal disturbance is a change of an output of a particular element during an automaton operation) and to mutations (changes in Boolean element types and in network connections). The attractor lengths L are very large: L ~ 2N/2 . The number of attractors M is of the order of N. If the connection degree K is decreased, this stochastic type of behavior is still observed, until K ~ 2.

At K ~ 2 the network behavior changes drastically. The sensitivity to minimal disturbances is small. The mutations create typically only slight variations an automaton dynamics. Only some rare mutations evoke the radical, cascading changes in the automata "programs". The attractor length L and the number of attractors M are of the order of N1/2. This is the behavior at the edge of chaos, at the borderland between chaos and order.

The NK automata can be considered as a model of regulatory genetic systems of living cells. Indeed, if we consider any protein synthesis (gene expression) as regulated by other proteins, we can approximate a regulatory scheme of a particular gene expression by a Boolean element, so that a complete network of molecular-genetic regulations of a cell can be represented as a network of a NK automaton.

S.A.Kauffman argues that the case K ~ 2 is just appropriate to model the regulatory genetic systems of biological cellular organisms, especially in evolutionary context. The main points of this argumentation are as follows:

  • the regulatory genetic systems at the edge of chaos ensure both necessary stability and potential for progressive evolutionary improvements;

  • typical cellular gene regulation schemes include only a small number of inputs from other genes in accordance with the value K ~ 2;

  • if we compare the number of automaton attractors M at K = 2 (calculated for given number of genes N) with the number of different kind of cells ncells in biological organisms at various evolutionary levels, we find similar values; for example, for a human we have (N ~ 105): M = 370, ncells = 254 [4].

Because the regulatory structures at the edge of chaos (K ~ 2) ensure both stability and evolutionary improvements, they could provide the background conditions for an evolution of genetic cybernetic systems. That is, such systems have "the ability to evolve". So, it seems quite plausible, that such kind of regulatory genetic structures was selected at early stages of life, and this in turn made possible the further progressive evolution.

References

S. A. Kauffman. Scientific American. 1991. August. P. 64.

S. A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution, Oxford University Press, New York, 1993.

S. A. Kauffman.At Home in the Universe: The Search for Laws of Self-Organization and Complexity, Oxford University Press, Oxford, 1995.


Copyright© 1998 Principia Cybernetica - Referencing this page

Author
V.G. Red'ko

Date
Sep 9, 1998

Home

Metasystem Transition Theory

Evolutionary Theory

Self-organization / General Models of Evolution

Up
Prev. Next
Down



Discussion

Add comment...