Nätverksanpassning (NA) jämför nätverk med målet att hitta en nodkartläggning som avslöjar mycket liknande (konserverade) nätregioner. Befintliga NA-metoder är homogena, dvs. de kan endast hantera nätverk som innehåller noder och kanter av en typ. På grund av ökande mängder heterogena nätverksdata med noder eller kanter av olika typer, utökar vi tre nya toppmoderna homogena NA-metoder, WAVE, MAGNA++ och SANA, för att möjliggöra heterogen NA för första gången. Vi introducerar flera algoritmiska nyheter. Nämligen, dessa befintliga metoder beräkna homogena graflet-baserade nod likheter och sedan hitta hög-skorning anpassningar med avseende på dessa likheter, samtidigt maximera mängden bevarade kanter. I stället utvidgar vi homogena grafler till sina heterogena motsvarigheter, som vi sedan använder för att utveckla ett nytt mått på heterogen nodlikhet. Dessutom utökar vi S 3, ett toppmodernt mått på kantbevarande för homogen NA, till dess heterogena motsvarighet. Sedan finner vi en hög grad av anpassning med avseende på vår heterogena nodlikhet och åtgärder för att bevara kanterna. I utvärderingar av syntetiska och verkliga biologiska nätverk leder våra föreslagna heterogena NA-metoder till högre kvalitet och bättre robusthet till buller i data än deras homogena motsvarigheter. Programvaran och data från detta arbete finns på https://nd.edu/~cone/colored_ graflets/. På grund av utvecklingen av biotekniken för datainsamling blir allt fler biologiska nätverksdata tillgängliga 1–4. En framträdande typ av biologiska nätverk är protein-protein interaktion (PPI) nätverk. Anpassa PPI nätverk av olika arter fortsätter att vara viktiga 5-9. Detta beror på att nätanpassning (NA) syftar till att avslöja liknande nätverksregioner genom att hitta en nodkartläggning mellan jämfört PPI-nätverk. Sedan, i likhet med genomic sekvens anpassning, NA kan användas för att överföra funktionell kunskap över arter mellan deras bevarade PPI-nätverk (snarare än sekvens) regioner. Detta är nödvändigt eftersom funktioner av många proteiner förblir okända även för välstuderade arter. Proteinfunktionsförutsägelse via NA-baserad överföring över arter kan hjälpa till att täppa till detta gap. NA-metoder består vanligtvis av två huvudalgoritmiska komponenter. För det första beräknas likheten mellan par av noder från olika nätverk med avseende på ett visst mått av nodbevarande (NC). För det andra, en anpassningsstrategi (AS) identifierar snabbt anpassningar som maximerar den totala NC över alla anpassade noder och mängden bevarade kanter (dvs. kantbevarande, EG). Det är intuitivt, en bra anpassning bör både kartlägga liknande noder till varandra och bevara många kanter. Det finns olika typer av NA-metoder. För det första kan NA kategoriseras som lokal (LNA) eller global (GNA). LNA syftar till att hitta optimalt bevarade nätverksregioner, vilket vanligtvis resulterar i att de anpassade regionerna är små 10-18. Å andra sidan syftar GNA till att hitta en övergripande nodkartläggning mellan jämförbara nät, vilket ofta leder till att de samordnade nätregionerna blir stora men suboptimalt bevarade [19] [20] [21] [23] [24] [25] [26] [27] [28] [29] [30] [31]. Både LNA och GNA har (dis)fördelar 32, 33. Eftersom det mesta av det senaste arbetet har handlat om GNA 9, fokuserar vi också på GNA, men vårt arbete kan generaliseras till LNA också. För det andra kan NA kategoriseras som parvis (PNA) eller multipel (MNA). PNA är utformad för att hitta liknande regioner mellan exakt två nätverk, medan MNA kan anpassa mer än två nätverk. Eftersom MNA är mer Publicerad: xx xx xxxx OPEN www.nature.com/science reports/ 2 SciEntific RAPPORTER  på engelska (2018) 8:12524  med beräkningskomplex än PNA 34, och eftersom aktuella PNA-metoder också är mer exakta än nuvarande MNA-metoder 35, fokuserar vi på PNA, men vårt arbete kan generaliseras till MNA också. För det tredje kan NA delas in i två kategorier baserat på typen av dess larmsystem. En AS-typ är frö-och-utvidgning, där de första två mycket liknande noder (med avseende på vissa NC-mått) är anpassade, dvs. sådd. Sedan, fröets angränsande noder (eller helt enkelt grannar) som är liknande är jämbördiga, fröets granne grannar som är liknande är jämbördiga, och så vidare. Detta steg att sträcka sig runt utsädet och utforska fröets grannar är avsett att förbättra både NC och EC av den resulterande anpassningen. Utökningssteget fortsätter tills alla noder i de mindre av de två jämfört nätverken är anpassade (formellt, tills en en-till-en-nod kartläggning mellan de två nätverken produceras). WAVE 36 är ett toppmodernt så-och-utvidgat AS, som visade sig fungera bäst under en grafletbaserad NC åtgärd 23,37 (se nedan) och en poäng som kallas "viktad EC", som är hög om noderna i de bevarade kanterna (se nedan) också är liknande när det gäller NC-måttet. Den andra AS-typen är en sökalgoritm. Här, i stället för att anpassa nod av nod som med frö-och-extend AS, hela anpassningar utforskas och den som poäng den högsta baserat på någon objektiv funktion returneras. En typisk objektiv funktion optimerar något mått av NC, EC, eller en kombination av de två. MAGNA++ 38 och SANA 39 är två toppmoderna sökalgoritmer baserade på AS. MAGNA++ använder en genetisk algoritm som sin sökstrategi och det fungerar bäst under den objektiva funktion som optimerar graflet-baserad NC åtgärd 23,37 och S 3 EC åtgärd 38. SANA använder simulerad glödgning som sin sökstrategi, och det utvärderades under flera objektiva funktioner som optimerar EC, inklusive S 3. I vår studie lägger vi till EC (dvs. S 3 ) en del av SANA:s objektiva funktion samma grafletbaserade NC-mått som WAVE och MAGNA++ också optimerar, för att så rättvist som möjligt jämföra de tre NA-metoderna och deras heterogena motsvarigheter.
Ett nyligen utfört arbete av Gu et al. REF använde en avslappnad definition av färgade grafer för nätanpassning på mycket små heterogena nät.
From homogeneous to heterogeneous network alignment via colored graphlets
{'venue': 'Scientific Reports', 'journal': 'Scientific Reports', 'mag_field_of_study': ['Computer Science', 'Medicine', 'Biology']}