Vi beskriver en algoritm, IsoRank, för global anpassning av två protein-protein interaktion (PPI) nätverk. IsoRank syftar till att maximera den totala matchningen mellan de två nätverken; däremot har mycket av tidigare arbete fokuserat på den lokala anpassningen problem-identifiera många möjliga anpassningar, var och en motsvarar en lokal region av likhet. IsoRank styrs av intuitionen att ett protein bör matchas med ett protein i det andra nätverket om och endast om grannarna till de två proteinerna också kan matchas väl. Vi kodar denna intuition som ett eigen value problem, på ett sätt som liknar Googles PageRank metod. Vi använder IsoRank för att beräkna den första kända globala anpassningen mellan S. cerevisiae och D. melanogaster PPI-nätverk. Den gemensamma subgrafen har 1420 kanter och beskriver bevarade funktionella komponenter mellan de två arterna. Jämförelser av våra resultat med de av en välkänd algoritm för lokal nätverksanpassning indikerar att den globalt optimerade anpassningen löser tvetydighet som införts av flera lokala anpassningar. Slutligen tolkar vi resultaten av global anpassning för att identifiera funktionella ortologs mellan jäst och fluga; vår funktionella ortolog förutsägelse metod är mycket enklare än en nyligen föreslagen strategi och ändå ger resultat som är mer omfattande. Motsvarande författare. Även med Institutionen för matematik, MIT interaktion mellan proteiner. Beräkningsanalyser av dessa nätverk har redan gett värdefulla insikter: den skalfria karaktären hos dessa nätverk och den oproportionerliga betydelsen av "hub"-proteiner [30], kombinationen av dessa nätverk med genuttrycksdata för att urskilja några av cellens dynamiska karaktär [8], användningen av PPI-nätverk för att härleda biologisk funktion [20], etc. När fler PPI-data blir tillgängliga, visar sig jämförande analys av PPI-nätverk (överart) vara ett värdefullt verktyg. En sådan analys liknar i andemeningen traditionella sekvensbaserade jämförande genomiska analyser; den utlovar också motsvarande insikter. En sådan analys kan identifiera bevarade funktionella komponenter mellan olika arter [15]. Som ett fylogenetiskt verktyg erbjuder det ett funktionsinriktat perspektiv som kompletterar traditionella sekvensbaserade metoder. Det underlättar också överföring av kommentarer mellan arter. Verkligen, Bandyopadhyay et al. [3] 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. I detta dokument undersöker vi en ny metod för jämförande analys av PPI-nätverk. Särskilt anser vi att problemet med att hitta den optimala globala anpassningen mellan två PPI-nätverk, som syftar till att hitta en korrelation mellan noder och kanter av inmatningsnäten som maximerar den totala matchningen mellan de två nätverken. För detta problem, föreslår vi en ny pairwise global anpassningsalgoritm, IsoRank.
Som ett exempel på spektralmetoder, IsoRank REF - ett av de tidigaste globala anpassning arbete i beräkningsbiologi-förslag ett eigen value problem som approximerar målet att hitta den maximala gemensamma subgraf.
Pairwise global alignment of protein interaction networks by matching neighborhood topology
{'venue': 'RECOMB', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}