Effektgrafanalys

Inom beräkningsbiologi är effektgrafanalys en metod för analys och representation av komplexa nätverk . Effektgrafanalys är beräkning, analys och visuell representation av en effektgraf från en graf ( nätverk ).

Effektgrafanalys kan ses som en förlustfri komprimeringsalgoritm för grafer. Den utökar grafsyntaxen med representationer av klicker , bicliquer och stjärnor . Kompressionsnivåer på upp till 95 % har erhållits för komplexa biologiska nätverk .

Hypergrafer är en generalisering av grafer där kanter inte bara är par av noder utan godtyckliga n-tupler . Kraftgrafer är inte en annan generalisering av grafer, utan istället en ny representation av grafer som föreslår en förskjutning från språket "nod och kant" till ett som använder klicker, bicliquer och stjärnor som primitiver.

Effektgrafer

De primitiva motiv som används för effektgrafanalys och deras motsvarande schematiska representation: biclique, klick och stjärna.

Grafisk representation

Grafer ritas med cirklar eller punkter som representerar noder och linjer som förbinder par av noder som representerar kanter . Effektgrafer utökar syntaxen för grafer med effektnoder , som ritas som en cirkel som omsluter noder eller andra effektnoder , och effektkanter , som är linjer mellan effektnoder.

Bicliques är två uppsättningar av noder med en kant mellan varje medlem i en uppsättning och varje medlem av den andra uppsättningen. I en effektgraf representeras en biclique som en kant mellan två effektnoder.

Klickor är en uppsättning noder med en kant mellan varje par av noder. I en effektgraf representeras en klick av en effektnod med en loop .

Stjärnor är en uppsättning noder med en kant mellan varje medlem i den uppsättningen och en enda nod utanför uppsättningen. I en effektgraf representeras en stjärna av en effektflank mellan en vanlig nod och en effektnod.

Formell definition

Givet ett diagram $G={\bigl (}{V,E}{\bigr )}$ där $V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}$ är uppsättningen av noder och $E\subseteq V\times V$ är uppsättningen av kanter, en effektgraf $G'={\bigl (}{V',E'}{\bigr )}$ är en graf definierad på effektmängden $V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}$ av effektnoder anslutna till varandra med effektkanter : $E'\subseteq V'\ gånger V'$ . Därför definieras effektgrafer på effektuppsättningen av noder såväl som på effektuppsättningen av kanter på grafen $G$ .

Semantiken för effektgrafer är följande: om två effektnoder är sammankopplade med en effektflank betyder detta att alla noder i den första effektnoden är anslutna till alla noder i den andra effektnoden. På liknande sätt, om en effektnod är ansluten till sig själv med en effektflank, betyder detta att alla noder i effektnoden är anslutna till varandra med flanker.

Följande två villkor krävs:

Kraftnodshierarkivillkor: Alla två effektnoder är antingen disjunkta eller så ingår den ena i den andra.
Tillstånd för osammanhängande effektkanter: Det finns en mappning från kanterna på den ursprungliga grafen till kraftkanterna. ^{[ citat behövs ]}

Analogi till Fourieranalys

Fourieranalysen av en funktion kan ses som en omskrivning av funktionen i termer av harmoniska funktioner istället för $\displaystyle t\mapsto x}$ { par. Denna transformation förändrar synvinkeln från tidsdomän till frekvensdomän och möjliggör många intressanta tillämpningar inom signalanalys, datakomprimering och filtrering. På liknande sätt är Power graph-analys en omskrivning eller nedbrytning av ett nätverk med hjälp av bicliques, cliques och stars som primitiva element (precis som harmoniska funktioner för Fourier-analys). Den kan användas för att analysera, komprimera och filtrera nätverk. Det finns dock flera viktiga skillnader. För det första, i Fourier-analys är de två utrymmena (tids- och frekvensdomäner) samma funktionsutrymme - men strikt sett är effektgrafer inte grafer. För det andra finns det ingen unik effektgraf som representerar en given graf. Ändå är en mycket intressant klass av effektgrafer minimala effektgrafer som har minst effektkanter och effektnoder som krävs för att representera en given graf.

Grafer för minimal effekt

Två olika effektgrafer som representerar samma graf.

I allmänhet finns det ingen unik graf för minimal effekt för en given graf. I det här exemplet (höger) tillåter en graf med fyra noder och fem kanter två minimala effektgrafer med två effektkanter vardera. Huvudskillnaden mellan dessa två minimala effektgrafer är den högre kapslingsnivån för den andra effektgrafen samt en förlust av symmetri med avseende på den underliggande grafen. Förlust av symmetri är bara ett problem i små leksaksexempel eftersom komplexa nätverk sällan uppvisar sådana symmetrier i första hand. Dessutom kan man minimera häckningsnivån, men även då finns det i allmänhet inte en unik minimal effektgraf med minimal häckningsnivå.

Kraftgraf girig algoritm

Algoritmen för giriga kraftgrafer bygger på två enkla steg för att utföra nedbrytningen:

Det första steget identifierar kandidateffektnoder genom en hierarkisk klustring av noderna i nätverket baserat på likheten hos deras angränsande noder. Likheten mellan två uppsättningar grannar tas som Jaccard-index för de två uppsättningarna.

Det andra steget utför en girig sökning efter möjliga effektkanter mellan kandidateffektnoder. Effektkanter som abstraherar flest kanter i det ursprungliga nätverket läggs först till effektdiagrammet. Således ersätts bicliquer, klicker och stjärnor stegvis med power edges, tills alla återstående enstaka kanter också läggs till. Kandidateffektnoder som inte är slutpunkten för någon effektkant ignoreras.

Modulär nedbrytning

Modulär nedbrytning kan användas för att beräkna en effektgraf genom att använda de starka modulerna i den modulära nedbrytningen. Moduler i modulär nedbrytning är grupper av noder i en graf som har identiska grannar. En stark modul är en modul som inte överlappar en annan modul. Men i komplexa nätverk är starka moduler mer undantag än regel. Därför är effektgraferna som erhålls genom modulär nedbrytning långt ifrån minimalitet. Huvudskillnaden mellan modulär nedbrytning och effektgrafanalys är betoningen av effektgrafanalys vid nedbrytning av grafer, inte bara med hjälp av moduler av noder utan också moduler av kanter (klickar, bicliques). Effektgrafanalys kan faktiskt ses som en förlustfri samtidig klustring av både noder och kanter.

Ansökningar

Biologiska nätverk

Effektgrafanalys har visat sig vara användbar för analys av flera typer av biologiska nätverk såsom protein-protein-interaktionsnätverk , domän-peptidbindande motiv, genreglerande nätverk och homologi/paraloginätverk. Även ett nätverk av signifikanta sjukdomsdragspar har nyligen visualiserats och analyserats med kraftgrafer.

Nätverkskomprimering, ett nytt mått som härrör från effektgrafer, har föreslagits som ett kvalitetsmått för proteininteraktionsnätverk.

Läkemedelsrepositionering

Effektgrafer har också använts för analys av läkemedel-mål-sjukdomsnätverk för läkemedelsrepositionering .

Sociala nätverk

Effektgrafer har tillämpats på storskalig data i sociala nätverk, för community mining eller för modellering av författaretyper.

Se även

externa länkar

[1] Power Graph Analysis-verktyg (CyOog v2.8.2) och exempelapplikationer
[2] Power Graph Analysis med CyOog v2.6