Dynamics of Boolean networks [Elektronische Ressource] / by Florian Greil

Florian.Greil<At>Physik.Tu-Darmstadt.De

Sujets

• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2009
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

DynamicsofBoolean
Networks
DynamikBoolescherNetzwerke
ForgraduationasDoktorderNaturwissenschaften (Dr.rer.nat.)
acceptedPhD-ThesisbyDipl.-Phys. FlorianGreilfromDarmstadt
Summer2009—Darmstadt—D17
FachbereichPhysik
Institut fürFestkörperphysik
Hochschulstr. 6
D-64289DarmstadtDynamicsofBooleanNetworks
DynamikBoolescherNetzwerke
acceptedPhD-ThesisbyDipl.-Phys. FlorianGreilfromDarmstadt
st1 review: Prof. BarbaraDrossel
nd2 review: Prof. GernotAlber
Dateofsubmission: 2009,May25th
Dateofexam: 2009, July15th
—Darmstadt—D17Scienceis what weunderstandwellenoughto
explaintoa computer. Art is everythingelsewedo.
DONALD KNUTH, computerscientist
Prefacetothebook “A=B”,1996.Abstract
Networks are used to model systems consisting of many interacting units. The topology of net-
works has been studied extensively while there are still many open questions concerning the
dynamics of and on networks. Boolean networks refer to a class of dynamics on networks; it
is the simplest possible dynamics which allows for analytical studies and easy computer imple-
mentation. ApplicationsofnetworksingeneralandBooleannetworksinparticularcanbefound
innumerousfields,rangingfromchemistry,biology,economy,computersciences,linguistics,to
sociology andgeology.
A classical Boolean network was introduced by STUART KAUFFMAN as a simple model for gene
regulation. The Boolean state of a node is determined by a Booleanfunction whose arguments
are the states of its randomly chosen inputs. The inputs are those nodes from which a edge
of the network leads to the node under consideration. Key quantities for the dynamics are the
numberandsizeofattractors. Anattractorisarecurrentsetofanetwork’sstates. Althoughthe
classical model of random Boolean networks with synchronous updating has been introduced
in 1969 it took30 yearsfor ananalyticalunderstandingofits keyquantities.
ThepresentworkstudiesvariationsoftheclassicalimplementationofarandomBooleannet-
work, in particular models with differently defined dynamics (non-synchronous updating, the
ensemble of threshold functions instead of all Boolean functions) and systems with other con-
nectionpatterns(scale-freein-degreedistribution). Tostudythecharacteristicsofthedynamics
of thosevariationsboth,computer simulationsandanalyticmethods, areused.
For the classical critical Boolean network(with synchronous updating)it is knownthat both,
the mean number and the length of attractors, diverge faster than any power law with the
numberofnodes. Itisshownhowthischangesforasynchronousupdatingschemes,inparticular
for a deterministic asynchronous one. Boolean threshold functions lead new phases of the
dynamicswhicharenotpredictedbytheusualmean-fieldconsiderations,realgeneticnetworks
might therefore also have a richer dynamical behaviour than the classical dynamical phases.
For the scale-free topology, the number of the non-frozen nodes scales in a different way as in
networks with a fixed number of inputs. Here, it is possible to analytically explain numerical
findings inliterature.Zusammenfassung
Netzwerkewerden alsModell fürSysteme mit vielenwechselwirkendenEinheitenbenutzt. Die
Topologie von Netzwerken sind intensiv untersucht worden, wogegen es viele offene Fragen
bei der Dynamik von und auf Netzwerken gibt. Boolesche Netzwerke stellen ein Klasse der
Dynamik auf Netzwerken dar. EinesolcheDynamikistdieeinfachstedenkbareDynamik,essind
analytische Untersuchungen möglich und die Umsetzung in Computer-Programmen ist leicht.
AnwendungenvonNetzwerkenimAllgemeinenundvonBooleschenNetzwerkenimSpeziellen
finden sich in den unterschiedlichsten Gebieten, angefangen von Chemie, Biologie, Wirtschaft,
Informatik,Sprachwissenschaften,bishin zurAnwendunginder Soziologieund Geologie.
Ein klassisches Boolesches Netzwerk wurde von STUART KAUFFMAN als Modell für die Gen-
regulation eingeführt. Der Boolesche Wert eines Knoten ist durch eine Boolesche Funktion
bestimmt, deren Argumente die Werte der zufällig verknüpften Eingänge sind. Eingänge sind
hierbei jene Knoten, von denen eine Verknüpfung des Netzwerks zu dem gerade betrachten
Knoten führt. Schlüsselgrößen für die Dynamik bilden die Zahl und die Größe der Attraktoren.
EinAttraktoristeineMengewiederkehrenderNetzwerkzustände. ObwohldasklassischeModell
zufälliger Boolescher Netzwerke 1969 eingeführt wurde, dauerte es 30 Jahre bis die Schlüssel-
größenanalytisch verstandenwaren.
Die vorliegende Arbeit untersucht Variationen der klassischen Implementierung eines zufäl-
ligen Booleschen Netzes, insbesondere Modelle mit abweichend definierter Dynamik (nicht-
synchroneAktualisierung,EnsemblederSchwellenwert-Funktionenanstelledesjenigenmitallen
BooleschenFunktionen)undSystememitanderenVerknüpfungsmustern(skalenfreieEingangs-
grad-Verteilung). Um die Eigenschaften der Dynamik dieser Variationen zu studieren werden
sowohlComputer-Simulationenalsauch analytischeMethoden benutzt.
Es ist bekannt, dass für klassische, kritische Boolesche Netzwerke (mit synchroner Aktual-
isierung) sowohl die mittlere Anzahl als auch die mittlere Länge der Attraktoren schneller als
jedes Potenz-Gesetz mit der Zahl der Knoten anwächst. Es wird gezeigt, wie sich das für an-
dereAktualisierungsschemataändert,insbesonderewirddabeieindeterministisch-asynchrones
Schema betrachtet. Boolesche Schwellenwert-Netze können zu neuen Phasen der Dynamik
führen, die von den üblichen Meanfield-Überlegungen nicht vorhergesagt werden; auch echte
genetischeNetzwerkekönntendahereinvielfältigeresVerhaltenzeigenalsdieklassischenPhasen
derDynamik. FürskalenfreieTopologieskaliertdieZahldernicht-gefrorenenKnotenandersals
bei Netzwerken mit festen Zahl der Eingänge. Es ist hier möglich die numerischen Befunde in
der Literatur analytischzuerklären.
Zusammenfassung vviContents
Abstract iii
Contents vii
1 Introduction 1
2 Networksandtheirdynamics 3
2.1 Some examplesofnetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Quantifyingthe Topology. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Introducing dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 The N-K model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 ClassicalcriticalBooleannetworks 17
3.1 ClassicalBooleannetworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Differenttypes of nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Conceptof relevantcomponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 The attractor length distributioninliterature . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Calculatingthe attractor distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Varyingtheupdatingscheme 25
4.1 Fluctuationsinthe updatingtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Asynchronousstochasticupdating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1 Results forcritical ARBNswith k=2 . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Adeterministicasynchronousupdatingscheme . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1 The concept ofeffective nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.2 Loopswith onedelayed node . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.3 Loopswith multiple delayed nodes . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3.4 Twoloopswith across-link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3.5 Aloopwith oneadditionallink . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.6 Results forthe entire network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Varyingthechoiceofthefunctions 47
5.1 Definingthreshold networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Differentcriticality conditionsforthe dynamics. . . . . . . . . . . . . . . . . . . . . . 49
5.3 Probabilityto flipbetweenthe two outcomes . . . . . . . . . . . . . . . . . . . . . . . 51
5.4 Applicationtothreshold networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5 The non-frozenregime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5.1 Oscillationswithperiod 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Contents vii5.6 Numericaltest of the newlyfoundtransitions . . . . . . . . . . . . . . . . . . . . . . . 58
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6 Varyingthetopology 63
6.1 Introductionto scale freenetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Booleandynamics onascale-freenetwork . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.3 The stochasticprocess todetermine the frozencore . . . . . . . . . . . . . . . . . . . 67
6.4 Analyticalprediction forthe finalcontainercontent . . . . . . . . . . . . . . . . . . . 71
6.4.1 Me