# Dynamics and evolution of random Boolean networks

### Mihaljev, Tamara (2008):Dynamics and evolution of random Boolean networks.Darmstadt, Technische Universität, [Ph.D. Thesis]

 Preview
PDF
Doktorarbeit.pdf
Available under CC-BY-NC-ND 2.5 de - Creative Commons, Attribution Non-commerical, No-derivatives.

Item Type: Ph.D. Thesis
Title: Dynamics and evolution of random Boolean networks
Language: English
Abstract:

Random Boolean networks are used as generic models for the dynamics of complex systems of interacting entities, such as social and economic networks, neural networks, and gene or protein interaction networks. The model studied in this thesis was introduced by S. Kauffman as a simple model for gene regulation. The system consists of N nodes, each of which receives inputs from K randomly chosen nodes. The state of a node is a Boolean function of the states of its input nodes. The functions are assigned to the nodes at random, and the states of all nodes in a network are updated in parallel. Asymptotic dynamical states of a network are represented by attractors in state space. Thus, their number and lengths are important features of the networks. The nodes in a network can be classified as frozen, irrelevant, or relevant, according to their dynamics on an attractor. The relevant nodes determine completely the number and the period of attractors. Although the random Boolean network model is simple, it shows a rich dynamical behavior with a phase transition between a frozen and a disordered phase and a very complex dynamics at the critical point between the phases. In this thesis dynamics and evolution of random Boolean networks are studied. The investigation of the dynamical properties of the model starts with the simplest realization of a random Boolean network, that is, with the network with one input per node. The topology of these networks is analyzed by generating networks through a growth process. Using probabilistic arguments and estimating the lower bounds, it is analytically proven that in this class of networks both, the mean number and the mean length of attractors grow faster than any power law with the size of the network. Next, the dynamics of critical networks with two inputs per node is studied and these studies are then generalized to networks with a larger number of inputs. Using methods from the theory of stochastic processes, the scaling behavior of the numbers of nonfrozen and relevant nodes is determined analytically. For all critical networks with K > 1 the same power-laws are found. The results obtained for the K = 1 networks are then used to show that in all critical random Boolean networks the mean number and length of attractors diverge faster than any power law with the network size. For the modeling of gene regulatory networks this means that the attractors are too long and too many to represent cellular differentiation, to which the model was originally applied. However, real networks are not random but are the result of evolutionary processes. Therefore, the evolution of populations of random Boolean networks under selection for robustness of the dynamics under small perturbations is investigated. The results of this study show that the fitness landscape contains a huge plateau of maximum fitness that spans the entire network space. It is found that the networks evolved on such a landscape are robust to changes in their structure, while being at the same time able to preserve their function under small environmental changes.

Alternative Abstract:
Alternative AbstractLanguage
Boolesche Zufallsnetzwerke finden ihre Anwendung als generisches Modell für die Dynamik von komplexen Systemen wechselwirkender Einheiten wie zum Beispiel soziale oder ökonomische Netzwerke, neuronale Netzwerke und Gen- oder Proteinwechselwirkungsnetzwerke. Das Modell, das im Rahmen dieser Arbeit untersucht wird, wurde von S. Kauffman als ein einfaches Modell für Genregulation eingeführt. Das System besteht aus N Knoten, von denen jeder Eingänge von K zufällig ausgewählten Knoten erhält. Der Zustand eines Knotens ist eine Boolesche Funktion der Zustände seiner Eingangsknoten. Diese Funktionen werden den Knoten zufällig zugewiesen und die Zustände aller Knoten eines Netzwerkes werden parallel aktualisiert. Asymptotische dynamische Zustände eines Netzwerkes werden durch Attraktoren im Zustandsraum repräsentiert. Ihre Anzahl und Länge sind wichtige Eigenschaften der Netzwerke. Die Knoten eines Netzwerkes können, gemäß ihrer Dynamik auf einem Attraktor, als gefroren, irrelevant oder relevant klassifiziert werden. Die relevanten Knoten bestimmen vollständig die Anzahl und die Periode der Attraktoren. Obwohl Boolesche Zufallsnetzwerke ein einfaches Modell sind, zeigen sie ein vielfältiges dynamisches Verhalten mit einem Phasenübergang zwischen einer gefrorenen und einer ungeordneten Phase und eine sehr komplexe Dynamik am kritischen Punkt zwischen diesen Phasen. In dieser Arbeit werden die Dynamik und die Evolution von Booleschen Zufallsnetzwerken untersucht. Die Untersuchung der dynamischen Eigenschaften des Modells beginnt mit der einfachsten Realisierung eines Booleschen Zufallsnetzwerkes, das heißt mit Netzwerken mit nur einem Eingang pro Knoten. Die Topologie dieser Netzwerke wird analysiert, indem Netzwerke mit Hilfe eines Wachstumsprozesses generiert werden. Mit Hilfe wahrscheinlichkeitstheoretischer Argumente und durch Abschätzung unterer Grenzen, wird analytisch bewiesen, dass in dieser Klasse von Netzwerken sowohl die mittlere Anzahl als auch die mittlere Länge der Attraktoren schneller als jedes Potenzgesetz mit der Netzwerkgröße anwächst. Als nächstes wird die Dynamik von kritischen Netzwerken mit zwei Eingängen pro Knoten untersucht und diese Untersuchungen werden für Netzwerke mit einer größeren Anzahl von Eingängen pro Knoten verallgemeinert. Mit Hilfe von Methoden aus der Theorie stochastischer Prozesse, wird das Skalenverhalten der Anzahl von nicht-gefrorenen und relevanten Knoten analytisch bestimmt. Für alle kritischen Netzwerken mit K > 1 werden die gleichen Potenzgesetze gefunden. Die Ergebnisse, die für die K = 1 - Netzwerke erhalten wurden, werden dann benutzt um zu zeigen, dass in allen kritischen Netzwerken die mittlere Anzahl und Länge der Attraktoren schneller als jedes Potenzgesetz mit der Netzwerkgröße divergiert. Für die Modellierung von Genregulationsnetzwerken bedeutet das, dass die Attraktoren zu lang sind und dass es zu viele von ihnen gibt, als dass sie zelluläre Differentiation repräsentieren könnten, auf die das Modell ursprünglich angewendet wurde. Reale Netzwerke sind nicht zufällig, sondern das Ergebnis evolutionärer Prozesse. Deswegen wird die Evolution von Populationen von Booleschen Netzwerken unter Selektion für Robustheit der Dynamik gegen kleine Störungen untersucht. Die Ergebnisse dieser Untersuchung zeigen, dass die Fitnesslandschaft ein riesiges Plateau maximaler Fitness enthält, das den gesamten Netzwerkraum umspannt. Es kann gezeigt werden, dass die Netzwerke, die in einer solchen Fitnesslandschaft evolviert wurden, robust sind gegen Änderungen in ihrer Struktur, während sie zur gleichen Zeit in der Lage sind ihre Funktion unter kleinen Änderungen der Umweltbedingungen aufrechtzuerhalten.German
Uncontrolled Keywords: Networks, Kauffman model, Random Boolean networks, genetic regulation, attractors, universal scaling, dynamics, evolution
Alternative keywords:
Alternative keywordsLanguage
Networks, Kauffman model, Random Boolean networks, genetic regulation, attractors, universal scaling, dynamics, evolutionEnglish
Classification DDC: 500 Naturwissenschaften und Mathematik > 530 Physik
Divisions: 05 Department of Physics > Institute for condensed matter physics
Date Deposited: 24 Nov 2008 08:34