Boolesches Netzwerk

Boolesche Netzwerke bezeichnen ein Modell aus der Statistischen Physik. Sie können als Generalisierung des Ising-Modells verstanden werden, nämlich als eine Spin-Dynamik auf einem Digraph ${\displaystyle G=(V,E)}$. Jedem Knoten ${\displaystyle V}$ sind dabei sowohl ein boolescher Zustand (oder Spin) als auch eine Boolesche Funktion über die Zustände der eingehenden Knoten zugeordnet.

Zustandsraum eines Booleschen Netzwerks mit N=4 Knoten und K=1 Kanten pro Knoten (dünne schwarze Pfeile). Jeder Knoten kann entweder eingeschaltet sein (rot) oder ausgeschaltet (blau). Der Einfachheit halber werden hier nur Kopier-Funktionen verwendet. Die dicken (grauen) Pfeile symbolisieren, was eine (synchrone) Aktualisierung bewirkt. Insgesamt hat das Beispiel vier Fixpunkt-Attraktoren, die als große (orangefarbene) Kreise dargestellt sind. Ferner gibt es zwei Attraktoren der Länge zwei.

Diese Aktualisierungsregeln definieren die Systemdynamik, die trotz einfacher Regeln nicht trivial ist. Der Arzt Stuart Kauffman war 1969 der erste Wissenschaftler, der Boolesche Netzwerke als Modell für genetische Netzwerke vorschlug[1] und zwar für den Spezialfall, dass es ${\displaystyle N}$ Knoten (oder Gene) gibt die jeweils exakt von ${\displaystyle K}$ anderen Knoten abhängen, deswegen wird diese Variation auch ${\displaystyle N}$-${\displaystyle K}$-Modell genannt. Obwohl Boolesche Netzwerke durch einfache Regeln definiert sind, wurde die Systemdynamik erst nach 2000 mathematisch verstanden.[2]

Obwohl Boolesche Netzwerke e​ine starke Vereinfachung darstellen (Gene s​ind nie einfach n​ur an o​der aus), g​ibt es v​iele Beispiele, i​n denen e​in Boolesches Modell d​ie richtige Abfolge d​er Schaltereignisse i​n einem genetischen Netzwerk vorhersagt.[3][4]

Mathematischer Hintergrund

Netzwerke s​ind eine Möglichkeit, d​ie Eigenschaften komplexer Systeme z​u untersuchen. Die Topologie e​ines Graphen spiegelt d​abei wider, w​ie die verschiedenen Einheiten d​es Systems miteinander wechselwirken. Eine zusätzlich z​u der Topologie definierte Dynamik k​ann dabei entweder d​ie Kanten d​es Graphen i​m Laufe d​er Zeit verändern (Dynamik vom Netzwerk) o​der nur d​ie Werte d​er Knoten (Dynamik auf dem Netzwerk). Bei Booleschen Netzwerken handelt e​s sich u​m die zweite Variante.

Eine wichtige Fragestellung bei der Untersuchung Boolescher Netzwerke ist, die globalen Eigenschaften eines gegebenen Ensembles zu analysieren. Die Zahl und die Länge der Attraktoren sind eine Möglichkeit, die globalen Eigenschaften zu quantifizieren. Die Herausforderung ist dabei, dass der Zustandsraum extrem schnell wächst, nämlich mit ${\displaystyle 2^{N}}$. Auch mit modernen Computern sind die Speichergrenzen schnell erreicht. Das einfachste Ensemble sind die zufälligen Booleschen Netzwerke (englisch: Random Boolean Networks, RBN). Hier ist die Graph-Topologie ein Erdős-Rényi-Zufallsgraph. Für RBNS gab es viele Versuche, die Verteilung der Attraktoren mittels Mittelwerte in Abhängigkeit von der Anzahl ${\displaystyle N}$ der Knoten zu charakterisieren.

Autoren	Jahr	Mittlere Attraktorlänge ${\displaystyle \langle A\rangle }$	Mittlere Attraktorzahl ${\displaystyle \langle \nu \rangle }$
Kauffman[1]	1969	${\displaystyle \langle A\rangle \sim {\sqrt {N}}}$	${\displaystyle \langle \nu \rangle \sim {\sqrt {N}}}$
Bastolla/ Parisi[5]	1998	schneller als ein Potenzgesetz, ${\displaystyle \langle A\rangle >N^{x}\forall x}$	schneller als ein Potenzgesetz, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$
Bilke/ Sjunnesson[6]	2002		linear mit der Systemgröße, ${\displaystyle \langle \nu \rangle \sim N}$
Socolar/Kauffman[7]	2003		schneller als linear, ${\displaystyle \langle \nu \rangle >N^{x}}$ with ${\displaystyle x>1}$
Samuelsson/Troein[8]	2003		Beweis des superpolynomiales Wachstum, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$
Mihaljev/Drossel[9]	2005	analytisches Argument für superpolynomiales Wachstum, ${\displaystyle \langle A\rangle >N^{x}\forall x}$	analytisches Argument für superpolynomiales Wachstum, ${\displaystyle \langle \nu \rangle >N^{x}\forall x}$

Einzelnachweise

1. Stuart Kauffman: Homeostasis and Differentiation in Random Genetic Control Networks. In: Nature. 224, Nr. 5215, 11. Oktober 1969, S. 177–178. doi:10.1038/224177a0.
2. Barbara Drossel: Chapter 3. Random Boolean Networks. In: Cornell University. Dezember 2009. arxiv:0706.3351v2. doi:10.1002/9783527626359.ch3.
3. Réka Albert, Hans G Othmer: The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. In: Journal of Theoretical Biology. 223, Nr. 1, Juli 2003, S. 1–18. doi:10.1016/S0022-5193(03)00035-3.
4. J. Li, A. J. Bench, G. S. Vassiliou, N. Fourouclas, A. C. Ferguson-Smith, A. R. Green: Imprinting of the human L3MBTL gene, a polycomb family member located in a region of chromosome 20 deleted in human myeloid malignancies. In: Proceedings of the National Academy of Sciences. 101, Nr. 19, 30. April 2004, S. 7341–7346. doi:10.1073/pnas.0308195101.
5. U. Bastolla, G. Parisi: The modular structure of Kauffman networks. In: Physica D: Nonlinear Phenomena. 115, Nr. 3–4, Mai 1998, S. 219–233. doi:10.1016/S0167-2789(97)00242-X.
6. Sven Bilke, Fredrik Sjunnesson: Stability of the Kauffman model. In: Physical Review E. 65, Nr. 1, Dezember 2001. doi:10.1103/PhysRevE.65.016129.
7. J. Socolar, S. Kauffman: Scaling in Ordered and Critical Random Boolean Networks. In: Physical Review Letters. 90, Nr. 6, Februar 2003. arxiv:cond-mat/0212306. doi:10.1103/PhysRevLett.90.068702.
8. Björn Samuelsson, Carl Troein: Superpolynomial Growth in the Number of Attractors in Kauffman Networks. In: Physical Review Letters. 90, Nr. 9, März 2003. doi:10.1103/PhysRevLett.90.098701.
9. Tamara Mihaljev, Barbara Drossel: Scaling in a general class of critical random Boolean networks. In: Physical Review E. 74, Nr. 4, Oktober 2006. doi:10.1103/PhysRevE.74.046101.