Analiza wykresu mocy - Power graph analysis
W biologii obliczeniowej , analiza wykres mocy jest sposób analizy i reprezentacji złożonych sieci . Analiza wykresu mocy to obliczenie, analiza i wizualna reprezentacja wykresu mocy z wykresu ( sieci ).
Analiza wykresów mocy może być traktowana jako algorytm bezstratnej kompresji wykresów. Rozszerza składnię grafów o reprezentacje klik , bilik i gwiazd . Dla złożonych sieci biologicznych uzyskano poziomy kompresji do 95% .
Hipergrafy to uogólnienie grafów, w których krawędzie to nie tylko pary węzłów, ale dowolne n-krotki . Wykresy potęgi nie są kolejnym uogólnieniem grafów, lecz nowatorską reprezentacją grafów, która proponuje przejście od języka „węzłów i krawędzi” do języka wykorzystującego kliki, bicliques i gwiazdy jako prymitywy.
Wykresy mocy
Reprezentacja graficzna
Wykresy są rysowane za pomocą okręgów lub punktów reprezentujących węzły i linii łączących pary węzłów reprezentujących krawędzie . Wykresy mocy rozszerzają składnię grafów z węzłami mocy , które są rysowane jako okrąg obejmujący węzły lub inne węzły mocy , oraz krawędzie mocy , które są liniami między węzłami mocy.
Bicliques to dwa zestawy węzłów z krawędzią między każdym członkiem jednego zbioru a każdym członkiem drugiego zbioru. Na wykresie mocy biclique jest reprezentowane jako krawędź między dwoma węzłami mocy.
Kliki to zbiór węzłów z krawędzią między każdą parą węzłów. Na wykresie mocy klika jest reprezentowana przez węzeł mocy z pętlą .
Gwiazdy to zbiór węzłów z krawędzią pomiędzy każdym członkiem tego zbioru a pojedynczym węzłem poza zbiorem. Na wykresie mocy gwiazda jest reprezentowana przez krawędź mocy między zwykłym węzłem a węzłem mocy.
Formalna definicja
Biorąc pod uwagę wykres gdzie jest zbiorem węzłów i jest zestaw brzegach, wykres mocy jest wykresem zdefiniowana w zbiorze mocy w węzłach energii połączonych ze sobą krawędziach zasilania : . Stąd grafy potęgowe są definiowane na zbiorze potęgowym węzłów oraz na zbiorze potęgowym krawędzi grafu .
Semantyka grafów mocy jest następująca: jeśli dwa węzły mocy są połączone krawędzią mocy, oznacza to, że wszystkie węzły pierwszego węzła mocy są połączone ze wszystkimi węzłami drugiego węzła. Podobnie, jeśli węzeł mocy jest połączony ze sobą krawędzią mocy, oznacza to, że wszystkie węzły w węźle mocy są połączone ze sobą krawędziami.
Wymagane są dwa następujące warunki:
- Warunek hierarchii węzłów zasilania: dowolne dwa węzły zasilania są albo rozłączne, albo jeden jest zawarty w drugim.
- Warunek rozłączności krawędzi mocy: Istnieje mapowanie na krawędzie oryginalnego wykresu do krawędzi mocy.
Analogia do analizy Fouriera
Analizy Fouriera z funkcji może być postrzegane jako przepisywanie funkcji pod względem funkcji harmonicznej zamiast pary. Transformacja ta zmienia punkt widzenia z dziedziny czasu do dziedziny częstotliwości i umożliwia wiele interesujących zastosowań w analizie sygnałów , kompresji danych i filtrowanie. Podobnie, Power Graph Analysis to przepisanie lub dekompozycja sieci przy użyciu bilic, klik i gwiazd jako elementów pierwotnych (podobnie jak funkcji harmonicznych w analizie Fouriera). Może służyć do analizy, kompresji i filtrowania sieci. Istnieje jednak kilka kluczowych różnic. Po pierwsze, w analizie Fouriera dwie przestrzenie (domeny czasu i częstotliwości) są tą samą przestrzenią funkcji – ale ściślej, grafy mocy nie są grafami. Po drugie, nie istnieje unikalny wykres mocy reprezentujący dany wykres. Jednak bardzo interesującą klasą grafów mocy są grafy mocy minimalne, które mają najmniej krawędzi mocy i węzłów mocy niezbędnych do przedstawienia danego grafu.
Wykresy mocy minimalnej
Ogólnie rzecz biorąc, nie ma unikalnego wykresu minimalnej mocy dla danego wykresu. W tym przykładzie (po prawej) wykres czterech węzłów i pięciu krawędzi dopuszcza dwa grafy mocy minimalnej o dwóch krawędziach mocy każdy. Główną różnicą między tymi dwoma wykresami mocy minimalnej jest wyższy poziom zagnieżdżenia drugiego wykresu mocy, a także utrata symetrii w stosunku do wykresu poniżej. Utrata symetrii jest problemem tylko w małych przykładach zabawek, ponieważ złożone sieci rzadko wykazują takie symetrie. Dodatkowo można zminimalizować poziom zagnieżdżenia, ale nawet wtedy na ogół nie ma unikalnego wykresu minimalnej mocy minimalnego poziomu zagnieżdżenia.
Algorytm zachłanny wykresu mocy
Algorytm zachłanny wykresu potęgi opiera się na dwóch prostych krokach, aby przeprowadzić dekompozycję:
W pierwszym kroku węzły energetyczne identyfikuje kandydat za pośrednictwem hierarchicznego grupowania węzłów w sieci na podstawie podobieństwa ich sąsiednich węzłów. Podobieństwo dwóch zestawów sąsiadów jest traktowane jako indeks Jaccarda tych dwóch zestawów.
Drugi etap przeprowadza chciwy poszukiwania możliwych krawędzi energetycznych pomiędzy węzłami mocy kandydatem. Krawędzie mocy abstrahujące większość krawędzi w oryginalnej sieci są dodawane jako pierwsze do wykresu mocy. W ten sposób biclique, kliki i gwiazdy są stopniowo zastępowane krawędziami mocy, aż wszystkie pozostałe pojedyncze krawędzie również zostaną dodane. Kandydujące węzły mocy, które nie są punktem końcowym żadnej krawędzi mocy, są ignorowane.
Rozkład modułowy
Dekompozycji modułowej można użyć do obliczenia wykresu mocy przy użyciu silnych modułów dekompozycji modułowej. Moduły w dekompozycji modularnej to grupy węzłów w grafie, które mają identycznych sąsiadów. Silny moduł to moduł, który nie nakłada się na inny moduł. Jednak w złożonych sieciach silne moduły są raczej wyjątkiem niż regułą. Dlatego wykresy mocy uzyskane poprzez dekompozycję modułową są dalekie od minimum. Główną różnicą między dekompozycją modularną a analizą grafów potęgi jest nacisk na analizę grafów potęgi w dekompozycji grafów nie tylko za pomocą modułów węzłów, ale także modułów krawędzi (kliki, bicliques). Rzeczywiście, analizę grafów mocy można postrzegać jako bezstratne jednoczesne grupowanie zarówno węzłów, jak i krawędzi.
Aplikacje
Sieci biologiczne
Wykazano, że analiza wykresów mocy jest przydatna do analizy kilku rodzajów sieci biologicznych, takich jak sieci interakcji białko-białko , motywy wiążące domena-peptyd, sieci regulacyjne genów i sieci homologiczne/paralogia. Niedawno zwizualizowano i przeanalizowano za pomocą Power Graphs sieć istotnych par choroba-cecha.
Kompresja sieci, nowa miara wywodząca się z wykresów mocy, została zaproponowana jako miara jakości sieci interakcji białek.
Repozycjonowanie leku
Wykresy mocy zostały również zastosowane do analizy sieci lek-cel-choroba w celu repozycjonowania leków .
Portale społecznościowe
Wykresy mocy zostały zastosowane do danych o dużej skali w sieciach społecznościowych, do eksploracji społeczności lub do modelowania typów autorów.