imported>Wilkibur |
imported>LoRo |
||
| Zeile 1: | Zeile 1: | ||
[[Datei:Hou710 BooleanNetwork.svg|mini|Zustandsraum eines '''Booleschen Netzwerks''' mit ''N=4 ''[[Knoten_(Graphentheorie)|Knoten]] und ''K=1'' [[Kante_(Graphentheorie)|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.]] | [[Datei:Hou710 BooleanNetwork.svg|mini|Zustandsraum eines '''Booleschen Netzwerks''' mit ''N=4 ''[[Knoten_(Graphentheorie)|Knoten]] und ''K=1'' [[Kante_(Graphentheorie)|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.]] | ||
'''Boolesche Netzwerke''' bezeichnen ein Modell aus der [[Statistische_Physik|Statistischen Physik]]. Sie können als Generalisierung des [[Ising-Modell]]s verstanden werden, nämlich als eine [[Spin]]-Dynamik auf einem [[Graph_(Graphentheorie)|Digraph]] <math>G=(V,E)</math>. Jedem [[Knoten_(Graphentheorie)|Knoten]] V sind dabei sowohl ein boolescher Zustand (oder | '''Boolesche Netzwerke''' bezeichnen ein Modell aus der [[Statistische_Physik|Statistischen Physik]]. Sie können als Generalisierung des [[Ising-Modell]]s verstanden werden, nämlich als eine [[Spin]]-Dynamik auf einem [[Graph_(Graphentheorie)|Digraph]] <math>G=(V,E)</math>. Jedem [[Knoten_(Graphentheorie)|Knoten]] <math>V</math> sind dabei sowohl ein boolescher Zustand (oder Spin) als auch eine [[Boolesche Funktion]] über die Zustände der eingehenden Knoten zugeordnet. | ||
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<ref name=KauffmanOriginal>{{cite journal|last1=Kauffman|first1=Stuart|title=Homeostasis and Differentiation in Random Genetic Control Networks|journal=Nature|date=1969-10-11|volume=224|issue=5215|pages=177–178|doi=10.1038/224177a0}}</ref> und zwar für den Spezialfall, dass es <math>N</math> [[Knoten_(Graphentheorie)|Knoten]] (oder [[Gen]]e) gibt die jeweils exakt von <math>K</math> anderen [[Knoten_(Graphentheorie)|Knoten]] abhängen, deswegen wird diese Variation auch <math>N</math>-<math>K</math>-Modell genannt. Obwohl Boolesche Netzwerke durch einfache Regeln definiert sind, wurde die Systemdynamik erst nach 2000 mathematisch verstanden.<ref>{{cite journal|last1=Drossel|first1=Barbara|title=Chapter 3. Random Boolean Networks|date=2009-12|doi=10.1002/9783527626359.ch3|arxiv=0706.3351v2|journal=Cornell University}}</ref> | 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<ref name=KauffmanOriginal>{{cite journal|last1=Kauffman|first1=Stuart|title=Homeostasis and Differentiation in Random Genetic Control Networks|journal=Nature|date=1969-10-11|volume=224|issue=5215|pages=177–178|doi=10.1038/224177a0}}</ref> und zwar für den Spezialfall, dass es <math>N</math> [[Knoten_(Graphentheorie)|Knoten]] (oder [[Gen]]e) gibt die jeweils exakt von <math>K</math> anderen [[Knoten_(Graphentheorie)|Knoten]] abhängen, deswegen wird diese Variation auch <math>N</math>-<math>K</math>-Modell genannt. Obwohl Boolesche Netzwerke durch einfache Regeln definiert sind, wurde die Systemdynamik erst nach 2000 mathematisch verstanden.<ref>{{cite journal|last1=Drossel|first1=Barbara|title=Chapter 3. Random Boolean Networks|date=2009-12|doi=10.1002/9783527626359.ch3|arxiv=0706.3351v2|journal=Cornell University}}</ref> | ||
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 $ G=(V,E) $. Jedem Knoten $ V $ sind dabei sowohl ein boolescher Zustand (oder Spin) als auch eine Boolesche Funktion über die Zustände der eingehenden Knoten zugeordnet.
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 $ N $ Knoten (oder Gene) gibt die jeweils exakt von $ K $ anderen Knoten abhängen, deswegen wird diese Variation auch $ N $-$ K $-Modell genannt. Obwohl Boolesche Netzwerke durch einfache Regeln definiert sind, wurde die Systemdynamik erst nach 2000 mathematisch verstanden.[2]
Obwohl Boolesche Netzwerke eine starke Vereinfachung darstellen (Gene sind nie einfach nur an oder aus), gibt es viele Beispiele, in denen ein Boolesches Modell die richtige Abfolge der Schaltereignisse in einem genetischen Netzwerk vorhersagt.[3][4]
Netzwerke sind eine Möglichkeit, die Eigenschaften komplexer Systeme zu untersuchen. Die Topologie eines Graphen spiegelt dabei wider, wie die verschiedenen Einheiten des Systems miteinander wechselwirken. Eine zusätzlich zu der Topologie definierte Dynamik kann dabei entweder die Kanten des Graphen im Laufe der Zeit verändern (Dynamik vom Netzwerk) oder nur die Werte der Knoten (Dynamik auf dem Netzwerk). Bei Booleschen Netzwerken handelt es sich um 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 $ 2^{N} $. Auch mit modernen Computern sind die Speichergrenzen schnell erreicht. Das einfachste Ensemble sind die zufälligen Booleschen Netzwerke (englisch: {{Modul:Vorlage:lang}} Modul:Multilingual:149: attempt to index field 'data' (a nil value), 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 $ N $ der Knoten zu charakterisieren.
| Autoren | Jahr | Mittlere Attraktorlänge $ \langle A\rangle $ | Mittlere Attraktorzahl $ \langle \nu \rangle $ |
|---|---|---|---|
| Kauffman[1] | 1969 | $ \langle A\rangle \sim {\sqrt {N}} $ | $ \langle \nu \rangle \sim {\sqrt {N}} $ |
| Bastolla/ Parisi[5] | 1998 | schneller als ein Potenzgesetz, $ \langle A\rangle >N^{x}\forall x $ | schneller als ein Potenzgesetz, $ \langle \nu \rangle >N^{x}\forall x $ |
| Bilke/ Sjunnesson[6] | 2002 | linear mit der Systemgröße, $ \langle \nu \rangle \sim N $ | |
| Socolar/Kauffman[7] | 2003 | schneller als linear, $ \langle \nu \rangle >N^{x} $ with $ x>1 $ | |
| Samuelsson/Troein[8] | 2003 | Beweis des superpolynomiales Wachstum, $ \langle \nu \rangle >N^{x}\forall x $ | |
| Mihaljev/Drossel[9] | 2005 | analytisches Argument für superpolynomiales Wachstum, $ \langle A\rangle >N^{x}\forall x $ | analytisches Argument für superpolynomiales Wachstum, $ \langle \nu \rangle >N^{x}\forall x $ |
