Protein-proteininteraktioner (PPI) och deras nätverk spelar en central roll i alla biologiska processer. I likhet med den fullständiga sekvenseringen av genom och deras jämförande analys, är fullständiga beskrivningar av interactomes och deras jämförande analys grundläggande för en djupare förståelse av biologiska processer. Ett första steg i en sådan analys är att anpassa två eller flera PPI-nätverk. Här introducerar vi en algoritm, IsoRank, för global anpassning av flera PPI-nätverk. Den vägledande intuitionen här är att ett protein i ett PPI-nätverk är en bra match för ett protein i ett annat nätverk om deras respektive sekvenser och kvarter topologier är en bra match. Vi kodar denna intuition som ett eigen value problem på ett sätt som liknar Googles PageRank metod. Med hjälp av IsoRank beräknar vi en global anpassning av Saccharomyces cerevisiae, Drosophila melanogaster, Caenorhabditis elegans, Mus musculus, och Homo sapiens PPI nätverk. Vi visar att inkorporering av PPI data i ortolog förutsägelse resulterar i förbättringar över befintliga sekvens-endast metoder och över förutsägelser från lokala anpassningar av jäst och flugnätverk. Tidigare metoder har varit effektiva för att identifiera bevarade, lokaliserade nätverk mönster över par av nätverk. Detta arbete tar ytterligare ett steg för att genomföra en global anpassning av flera PPI-nätverk. Samtidigt används sekvenslikhet och nätverksdata och, till skillnad från tidigare metoder, modellerar man uttryckligen den kompromiss som ingår i att kombinera dem. Vi förväntar oss att IsoRank-med sin samtidiga hantering av nodlikhet och nätverk likhet-att tillämpas inom många vetenskapliga områden. biologiska nätverk  på grafen isomorfism  på nätet anpassning av protein-protein interaktioner  på funktionell sammanhållning Ett grundläggande mål för biologin är att förstå cellen som ett system av interagerande komponenter. Särskilt upptäckten och förståelsen av interaktioner mellan proteiner har fått betydande uppmärksamhet under de senaste åren. Mot detta mål, highthroughput experimentella tekniker [t.ex., jäst tvåhybrid (1, 2) och coimmunoprecipitation (3)] har uppfunnits för att upptäcka protein-protein interaktioner (PPI). Data från dessa tekniker, som fortfarande håller på att fulländas, kompletteras med högkonfidentiella beräkningsprognoser och analyser av PPI (4-6). Ett kraftfullt sätt att representera och analysera denna stora corpus av data är PPI-nätverket: Ett nätverk där varje nod motsvarar ett protein och en kant indikerar en direkt fysisk interaktion mellan proteinerna. Eftersom storleken på PPI-datamängderna för olika arter snabbt ökar, har jämförande analyser av PPI-nätverk mellan olika arter visat sig vara ett värdefullt verktyg. En sådan analys liknar i andemeningen traditionella sekvensbaserade jämförande genomiska analyser; den utlovar också motsvarande insikter. Som ett fylogenetiskt verktyg erbjuder det ett funktionsinriktat perspektiv som kompletterar traditionella sekvensbaserade metoder. Jämförande nätverksanalys gör det också möjligt för oss att identifiera bevarade funktionella komponenter över arter (7) och utföra högkvalitativa ortolog förutsägelser (dvs. identifiera gener i olika arter som härrör från samma anortal region). Att lösa dessa problem är avgörande för att överföra insikter och information över olika arter, så att vi kan utföra experiment i (säg) jäst eller flyga och tillämpa dessa insikter mot förståelse mekanismer för mänskliga sjukdomar (8). Verkligen, Bandyopadhyay et al. (9) har visat att användningen av PPI-nätverk vid beräkning av ortologer producerar ortologikartläggningar som bättre bevarar proteinfunktionen mellan olika arter (dvs. funktionella ortologer). Tidigare arbete med anpassning av PPI-nätverk har nästan uteslutande fokuserat på det lokala nätets anpassningsproblem (se Global vs. Local Network Alignment) och har hittills endast inriktat sig på parvisa anpassningar. Kelley et al:s pionjärarbete. (10, 11) beskrev hur BLAST likhetspoäng och PPI-nätverksinformation kunde användas för att identifiera bevarade funktionella motiv. Koyuturk m.fl. (12) föreslog en annan metod som motiveras av biologiska modeller för duplicering och radering. Nyligen, Flannick et al. (7) föreslog ett nytt effektivt tillvägagångssätt med hjälp av moduler av proteiner för att dra slutsatsen om anpassningen. Berg och Lassig (13) har föreslagit en Bayesiansk strategi för detta problem. Många av dessa metoder begränsar uppsättningen möjliga node-parnings baserat på sekvensbaserade likhetspoäng eller ortologi förutsägelser, och sedan lägga till i nätverksdata för att härleda anpassningen. Detta tillvägagångssätt bidrar till att minska problemets komplexitet, men saknar flexibiliteten att producera nodepareringar som avviker från sekvensbaserade förutsägelser. Vi noterar här att problemet med grafjustering också har studerats inom andra områden. Till exempel, i datorseende, problemet med att matcha en frågebild till en befintlig bild i databasen har ofta formulerats som en graf-matchning problem, varje bild representeras som en graf. Några av de lösningar som föreslås i den domänen använder spektralteknik, dvs. de använder eigenvärden som beräknas baserat på varje graf (14, 15). Vårt tillvägagångssätt, som också konstruerar ett eigen value problem (även om, inte för enskilda grafer) kan vara relevant inom detta område också. I denna artikel introducerar vi en strategi för jämförande analys av PPI-nätverk för att ta itu med problemet med att hitta den optimala globala anpassningen mellan två eller flera PPI-nätverk, som syftar till att hitta en överensstämmelse mellan noder och kanter av inmatningsnäten som maximerar den totala "matchen" mellan nätverken. Vi föreslår IsoRank-algoritmen för flera nätverksanpassningar. IsoRank-algoritmen använder samtidigt både PPI-nätverksdata och sekvenslikviditetsdata i ett eigen value-baserat ramverk för att beräkna nätverksanpassningar, där de två datakällornas relativa vikt är en fri parameter. Vi använder IsoRank för att samtidigt anpassa PPI-nätverken av Saccharomyces cerevisiae, Drosophila melanogaster, Caenorhabditis elegans, Mus musculus, och Homo sapiens, de arter som utgör huvuddelen av tillgängliga PPI data. De bevarade subgraferna i denna anpassning är större och mer varierande än de som producerades av tidigare metoder, som utförde parvisa nätverksanpassningar. Vi använder också anpassningsresultaten för att förutsäga funktionella ortologs över olika arter och visar att om PPI-data införlivas i ortolog förutsägelse resulterar i förbättringar över befintliga sekvensbara tillvägagångssätt såsom Homologene (www.ncbi.nlm.nih.gov/sites/ entrez?db-homologene) och Inparanoid (16); dessutom finner vi våra resultat jämföra gynnsamt med de från lokala anpassningar på jäst- och fluganätverk (9). För att testa den biologiska kvaliteten på våra förutsägelser introducerar vi en direkt, automatiserad metod för att poängsätta kvaliteten på en ortologlista. Global vs. lokal nätverksanpassning. I allmänhet är målet i ett nätanpassningsproblem att hitta en gemensam subgraf (dvs. en uppsättning bevarade kanter) över inmatningsnätverken. Motsvarar dessa bevarade kanter, det finns en kartläggning mellan noderna i nätverken. Till exempel, när protein en 1 från nätverk G 1 kartläggs till proteiner en 2 från G 2 och en 3 från G 3, sedan en 1, en 2, och en 3 hänvisar till samma nod i uppsättningen av bevarade kanter. Det som gör problemet svårt är kompromissen: Maximera överlappningen mellan nätverken (dvs. antalet bevarade kanter), samtidigt som man ser till att de proteiner som kartlagts till varandra så långt som möjligt är evolutionärt relaterade. I de flesta befintliga tillvägagångssätt, och i den här artikeln, används sekvenslikhet som ett mått på evolutionärt förhållande, om än ungefärligt. Men mer sofistikerade åtgärder är säkert möjliga, t.ex. de som innehåller genordning (synteny). Problemet med nätanpassning kan formuleras på olika sätt, beroende på vilken typ av inmatning (parvis jämfört med flera justeringar) och omfattningen av nodkartläggning som önskas. Här drar vi en analogi från sekvensanpassningsproblemet för att skilja mellan lokal och global nätanpassning, den senare är fokus i denna artikel.
Till exempel, IsoRank REF anpassar olika grafer girigt baserat på parvis topologi likheter (dvs, nod likhet) beräknas med spektral graf teori och finner anpassningen genom att lösa den maximala bipartite matchning.
Global alignment of multiple protein interaction networks with application to functional orthology detection
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Biology', 'Medicine', 'Computer Science']}