Booleovská síť - Boolean network

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Ne důvod vyčištění bylo upřesněno. Prosím pomozte vylepšit tento článek jestli můžeš. (Srpna 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

Stavový prostor booleovské sítě s N = 4 uzly a K = 1 Odkazy na uzel. Uzly lze zapnout (červená) nebo vypnout (modrá). Tenké (černé) šipky symbolizují vstupy Booleovská funkce což je jednoduchá funkce „kopírování“ pro každý uzel. Tlusté (šedé) šipky ukazují, co synchronní aktualizace dělá. Celkem jich je 6 (oranžová) atraktory, 4 z nich jsou pevné body.

A Booleovská síť se skládá z diskrétní sady booleovské proměnné každý z nich má Booleovská funkce (případně odlišný pro každou proměnnou), který je jí přiřazen, který bere vstupy z podmnožiny těchto proměnných a výstup, který určuje stav proměnné, které je přiřazena. Tato sada funkcí ve skutečnosti určuje topologii (konektivitu) na sadě proměnných, které se poté stanou uzly v a síť. Dynamika systému je obvykle brána jako diskrétní časové řady kde je stav celé sítě v čase t+1 je určeno vyhodnocením funkce každé proměnné na stavu sítě v čase t. To může být provedeno synchronně nebo asynchronně.^[1]

Logické sítě se v biologii používají k modelování regulačních sítí. Ačkoli booleovské sítě představují hrubé zjednodušení genetické reality, kde geny nejsou jednoduché binární přepínače, existuje několik případů, kdy správně zachycují správný vzorec exprimovaných a potlačovaných genů.^[2][3] Zdánlivě matematický snadný (synchronní) model byl plně pochopen až v polovině roku 2000.^[4]

Klasický model

Booleovská síť je zvláštní druh sekvenční dynamický systém, kde čas a stavy jsou diskrétní, tj. jak sada proměnných, tak sada stavů v časové řadě mají každý a bijekce na celočíselnou řadu. Takové systémy jsou jako mobilní automaty v sítích, s výjimkou skutečnosti, že když jsou nastaveny, každý uzel má pravidlo, které je náhodně vybráno ze všech 2^2K. možné s K. vstupy. S K = 2 chování třídy 2 má tendenci dominovat. Ale pro K> 2, chování, které člověk vidí, se rychle blíží tomu, co je typické pro náhodné mapování, ve kterém síť představující vývoj 2^N státy N podkladové uzly je sám připojen v podstatě náhodně.^[5]

A náhodná logická síť (RBN) je ten, který je náhodně vybrán ze sady všech možných booleovských sítí určité velikosti, N. Poté lze statisticky studovat, jak očekávané vlastnosti těchto sítí závisí na různých statistických vlastnostech souboru všech možných sítí. Například lze studovat, jak se chování RBN mění, jak se mění průměrná konektivita.

První booleovské sítě navrhl Stuart A. Kauffman v roce 1969, as náhodný modely genetické regulační sítě^[6] ale jejich matematické porozumění začalo až v roce 2000.^[7][8]

Atrakce

Protože booleovská síť má pouze 2^N možných stavů, trajektorie dříve či později dosáhne dříve navštíveného stavu, a proto, protože dynamika je deterministická, trajektorie spadne do ustáleného stavu nebo cyklu zvaného atraktor (i když v širším poli dynamických systémů je cyklus pouze přitahovatelem, pokud k němu odchylky vedou zpět). Pokud má atraktor pouze jediný stav, nazývá se a bodový atraktor, a pokud se atraktor skládá z více než jednoho stavu, nazývá se a přitahovač cyklu. Soubor stavů, které vedou k atraktoru, se nazývá Umyvadlo atraktoru. Stavy, které se vyskytují pouze na začátku trajektorií (žádné trajektorie nevedou na je) Rajská zahrada státy^[9] a dynamika toku sítě z těchto států směrem k atraktorům. Nazývá se čas potřebný k dosažení atraktoru přechodný čas.^[4]

S rostoucím výkonem počítače a rostoucím porozuměním zdánlivě jednoduchého modelu poskytli různí autoři různé odhady průměrného počtu a délky atraktorů, zde je stručné shrnutí klíčových publikací.^[10]

Autor	Rok	Střední délka atraktoru	Průměrné číslo atraktoru	komentář
Kauffmann [6]	1969	${displaystyle langle Aangle sim {sqrt {N}}}$	${displaystyle langle u angle sim {sqrt {N}}}$
Bastolla / Parisi[11]	1998	rychlejší než zákon o moci, ${displaystyle langle Aangle> N ^ {x} pro všechny x}$	rychlejší než zákon o moci, ${displaystyle langle u angle> N ^ {x} pro všechny x}$	první číselné důkazy
Bilke / Sjunnesson[12]	2002		lineární s velikostí systému, ${displaystyle langle u angle sim N}$
Socolar / Kauffman[13]	2003		rychlejší než lineární, ${displaystyle langle u angle> N ^ {x}}$ s ${displaystyle x> 1}$
Samuelsson / Troein[14]	2003		superpolynomiální růst, ${displaystyle langle u angle> N ^ {x} pro všechny x}$	matematický důkaz
Mihaljev / Drossel[15]	2005	rychlejší než zákon o moci, ${displaystyle langle Aangle> N ^ {x} pro všechny x}$	rychlejší než zákon o moci, ${displaystyle langle u angle> N ^ {x} pro všechny x}$

Stabilita

V teorii dynamických systémů odpovídá struktura a délka atraktorů sítě dynamické fázi sítě. The stabilita booleovských sítí záleží na jejich spojení uzly. Booleovská síť může vykazovat stabilní, kritické nebo chaotické chování. Tento jev je řízen kritickou hodnotou průměrného počtu připojení uzlů (${displaystyle K_ {c}}$) a lze jej charakterizovat pomocí Hammingova vzdálenost jako míra vzdálenosti. V nestabilním režimu vzdálenost mezi dvěma původně blízkými stavy v průměru v čase exponenciálně roste, zatímco ve stabilním režimu exponenciálně klesá. V tomto případě znamená „původně zavřené stavy“, že Hammingova vzdálenost je malá ve srovnání s počtem uzlů (${displaystyle N}$) v síti.

Pro N-K model^[16] síť je stabilní, pokud ${displaystyle K$, kritické, pokud ${displaystyle K = K_ {c}}$a nestabilní, pokud ${displaystyle K> K_ {c}}$.

Stav daného uzlu ${displaystyle n_ {i}}$ je aktualizován podle jeho pravdivostní tabulka, jehož výstupy jsou náhodně vyplněny. ${displaystyle p_ {i}}$ označuje pravděpodobnost přiřazení vypnutého výstupu k dané řadě vstupních signálů.

Li ${displaystyle p_ {i} = p = konst.}$ u každého uzlu závisí přechod mezi stabilním a chaotickým rozsahem ${displaystyle p}$. Podle Bernard Derrida a Yves Pomeau^[17], kritická hodnota průměrného počtu připojení je ${displaystyle K_ {c} = 1 / [2p (1-p)]}$.

Li ${displaystyle K}$ není konstantní a neexistuje korelace mezi in-stupně a out-stupně, podmínky stability jsou určeny ${displaystyle langle K ^ {in} úhel}$^[18][19][20] Síť je stabilní, pokud ${displaystyle langle K ^ {in} úhel$, kritické, pokud ${displaystyle langle K ^ {in} angle = K_ {c}}$a nestabilní, pokud ${displaystyle langle K ^ {in} angle> K_ {c}}$.

Podmínky stability jsou stejné v případě sítí s bez měřítka topologie kde je distribuce dovnitř a ven stupeň distribuce podle zákona o moci: ${displaystyle P (K) propto K ^ {- gama}}$, a ${displaystyle langle K ^ {in} angle = langle K ^ {out} angle}$, protože každý out-link z uzlu je in-link do jiného.^[21]

Citlivost ukazuje pravděpodobnost, že se změní výstup booleovské funkce daného uzlu, pokud se změní jeho vstup. Pro náhodné booleovské sítě${displaystyle q_ {i} = 2p_ {i} (1-p_ {i})}$. Obecně platí, že stabilita sítě se řídí největší vlastní číslo ${displaystyle lambda _ {Q}}$ matice ${displaystyle Q}$, kde ${displaystyle Q_ {ij} = q_ {i} A_ {ij}}$, a ${displaystyle A}$ je matice sousedství sítě.^[22] Síť je stabilní, pokud ${displaystyle lambda _ {Q} <1}$, kritické, pokud ${displaystyle lambda _ {Q} = 1}$, nestabilní, pokud ${displaystyle lambda _ {Q}> 1}$.

Variace modelu

Další topologie

Jedním z témat je studium různé podkladové topologie grafů.

• Homogenní případ jednoduše odkazuje na mřížku, která je jednoduše redukcí na slavnou Isingův model.
• Bez vodního kamene pro booleovské sítě lze zvolit topologie.^[23] Lze rozlišit případ, kdy se distribuuje pouze in-stupeň distribuce v power-law,^[24] nebo pouze out-stupeň distribuce nebo obojí.

Další schémata aktualizace

Klasické booleovské sítě (někdy nazývané CRBN, tj. Classic Random Boolean Network) jsou synchronně aktualizovány. Motivováno skutečností, že geny obvykle nemění svůj stav současně,^[25] byly zavedeny různé alternativy. Běžná klasifikace^[26] je následující:

• Deterministické asynchronní aktualizované booleovské sítě (DRBNs) nejsou synchronně aktualizovány, ale deterministické řešení stále existuje. Uzel i bude aktualizováno, když t ≡ Q_i (mod P_i) kde t je časový krok.^[27]
• Nejobecnějším případem je úplná stochastická aktualizace (GARBN, obecné asynchronní náhodné booleovské sítě). Zde je v každém výpočetním kroku vybrán jeden (nebo více) uzlů, které mají být aktualizovány.
• The Částečně pozorovaný booleovský dynamický systém (POBDS)^{[28][29][30][31]} signální model se liší od všech předchozích deterministických a stochastických modelů booleovské sítě odstraněním předpokladu přímé pozorovatelnosti booleovského stavového vektoru a umožněním nejistoty v procesu pozorování při řešení scénáře, se kterým se setkáváme v praxi.

Aplikace booleovských sítí

Klasifikace

• The Škálovatelná optimální Bayesiánská klasifikace^[32] vyvinuli optimální klasifikaci trajektorií zohledňujících nejistotu potenciálního modelu a také navrhli klasifikaci trajektorie na základě částic, která je vysoce škálovatelná pro velké sítě s mnohem nižší složitostí než optimální řešení.

Viz také

• Model NK

Reference

• Dubrova, E., Teslenko, M., Martinelli, A., (2005). *Kauffman Networks: Analýza a aplikace, v „Sborník mezinárodní konference o počítačově podporovaném designu“, strany 479-484.

externí odkazy

• DDLab
• Analýza dynamických algebraických modelů (ADAM) v1.1
• RBNLab
• NetBuilder Boolean Networks Simulator
• Open Source Boolean Network Simulator
• Síť JavaScript Kauffman
• Pravděpodobnostní booleovské sítě (PBN)
• Nástroj založený na SAT pro výpočet atraktorů v Boolean Networks
• CoLoMoTo (Konsorcium pro logické modely a nástroje)