Tecniche di network comparison / M-GRAAL - Seminario di...

Reti di interazione molecolareTecniche di network comparison

Network evolutionSviluppi della network comparison

M-GRAAL

Tecniche di network comparison / M-GRAALSeminario di Bioinformatica

Giovanni Micale

Universita di Catania

06/06/2011

Giovanni Micale Tecniche di network comparison / M-GRAAL



M-GRAAL

Overview

1 Reti di interazione molecolare

2 Tecniche di network comparisonNetwork alignmentNetwork integrationNetwork querying

3 Network evolution

4 Sviluppi della network comparison

5 M-GRAAL




M-GRAAL

Outline



3 Network evolution


5 M-GRAAL




M-GRAAL

Dati di interazione molecolare

Negli ultimi anni c’e stato un notevole incremento dei dati diinterazione molecolare;

Varie tecnologie usate:

mass spectrometry;genome-wide chromatin immunoprecipitation;yeast two-ibrid essays;combinatorial reverse genetic screens;tecniche mining.

Oggi si conoscono migliaia di interazioni sull’uomo e altriorganismi;




M-GRAAL

Alcuni database di interazioni

IntAct: database di interazioni molecolari;

Biomolecular Interaction Network Database (BIND);

Database of Interacting Proteins (DIP);

Molecular INTeractions database (MINT);

General Repository for Interaction Datasets (GRID);

Pathway Interaction Database (PID);

Interaction Web DataBase (IWDB);

Search Tool for the Retrieval of Interacting Genes/proteins(STRING).




M-GRAAL

Network di interazioni

Vari tipi:

Network PPI;Network genetiche;Network trascrizionali;Network metaboliche;...

’Fotografano’ il comportamento di un sistema o di unprocesso sotto certe condizioni.




M-GRAAL

Protein-Protein Interactions Network

A PPI network of eukaryotic-like Ser/Thr protein kinases.




M-GRAAL

Genetic Interactions Network

Genetic interaction network representing the synthetic lethal/sick interactions in Yeast. Genes are colored accordingto their cellular roles.




M-GRAAL

Transcriptional Interactions Network




M-GRAAL

Metabolic Interactions Network

The Arachidonic Acid (AA) metabolic network.




M-GRAAL

Network alignmentNetwork integrationNetwork querying

Outline



3 Network evolution


5 M-GRAAL




M-GRAAL


Network comparison (1)

Obbiettivo: Sviluppare tecniche per filtrare, interpretare eorganizzare dati di interazione in modelli di funzione cellulare.

Come nel caso delle sequenze, l’analisi comparativa oevoluzionaria e la base per raggiungere questo obbiettivo.

Network comparison: confrontare due o piu reti diinterazione, che possono rappresentare diverse specie,condizioni e tipi di interazione.




M-GRAAL


Network comparison (2)

Risponde a varie domande:

1 Quali proteine, interazioni tra proteine e gruppi di interazionihanno funzioni equivalenti tra le specie?

2 A partire da queste similarita, possiamo predire nuovefunzionalita di alcune proteine e interazioni che sono pococaratterizzate?

3 Cosa ci dicono queste relazioni sull’evoluzione delle proteine,delle network e degli organismi?

4 Quali interazioni sono ’falsi positivi’ e quali rappresentanoeventi davvero collegati?

Misure di confidenza di un’interazione;Network comparison per aumentare la confidenza di un set diinterazioni che risultano conservate tra le specie.




M-GRAAL


Tecniche di network comparison

1 Network alignment: confrontare due o piu network dellostesso tipo ma di specie diverse, identificando regioni disimilarita e dissimilarita.

Individua sottoreti conservate tra le specie (moduli funzionali).

2 Network integration: combinare due o piu network di diversotipo ma della stessa specie e sullo stesso set di elementi.

Individua moduli di proteine che interagiscono allo stesso modomediante interazioni di diverso tipo;Aiuta a predire nuove interazioni tra proteine.

3 Network querying: ricercare, all’interno di una rete, sottoretisimili ad una sottorete query di interesse.

Identifica istanze duplicate o conservate di un modulo.




M-GRAAL


Outline



3 Network evolution


5 M-GRAAL




M-GRAAL


Network Alignment




M-GRAAL


Pairwise network alignment

Confrontare due reti dello stesso tipo in specie diverse, pertrovare:

coppie di singole interazioni, una per specie, di geni o proteinesimili (interologhi);strutture conservate: path lineari (signaling paths), cluster diinterazioni (complessi proteici).

Soluzioni efficienti per catene lineari di interazioni ma, ingenerale, e computazionalmente difficile;

Servono apposite euristiche.




M-GRAAL


Network alignment graph

Grafo che rappresenta l’allineamento di due subnetwork;Nodo: insieme di molecole, una per ciascuna rete,rappresentate con colori diversi;Arco: interazione molecolare (colori diversi a seconda dellarete in cui avviene l’iterazione).




M-GRAAL


Network alignment graph (cont.)

Una molecola puo trovarsi in uno o piu nodi differenti:

corrispondenza uno-uno;corrispondenza molti-molti (allineamento complesso).

Il grafo di allineamento guida e facilita la ricerca di networkconservate;

Trovare pathway e moduli conservati equivale a trovare,rispettivamente, cammini e cluster di geni o proteine nel grafodi allineamento con il punteggio piu alto.

Occorre stabilire una funzione di scoring e una procedura diricerca.




M-GRAAL


Schema generale di allineamento




M-GRAAL


Funzione di scoring

Misura la similarita di ogni sottorete con una strutturapredefinita di interesse e il livello di conservazione di questastruttura tra le sottoreti esaminate.

Due possibili schemi:

Evolution-based scoring scheme;Maximum log likelihood ratio.




M-GRAAL


Evolution-based scoring scheme

M = insieme di coppie di interazioni con match (interologhi), conrelazione di ortologia tra elementi corrispondenti nelle dueinterazioni;

N = insieme di coppie di interazioni mismatched, sempre conrelazione di ortologia tra proteine corrispondenti;




M-GRAAL


Evolution-based scoring scheme (cont.)

D = unione degli insiemi di coppie di proteine duplicate in ciascunanetwork.

Definiti dei punteggi per un match m, un mismatch n e unaduplicazione d , lo score complessivo di una network di proteine C e:

E (C ) =∑

α∈M m(α)−∑

β∈N n(β)−∑

χ∈D d(χ)

Il punteggio premia i match e penalizza i mismatch e leduplicazioni.




M-GRAAL


Log likelihood ratio

Misura la similarita della subnetwork con una strutturadesiderata (subnetwork model) in rapporto alla possibilitache la sottorete sia osservata in maniera random (nullmodel).

Subnetwork model: un complesso di proteine, in cui ognicoppia di proteine interagisce con alta probabilita β,indipendentemente dalle altre coppie.

Null model: un complesso in cui ogni coppia di proteine u, vinteragisce con probabilita p(u, v) che dipende dai gradi deidue nodi.




M-GRAAL


Log likelihood ratio (cont.)

Per costruire il null model si possono considerare versionirandomizzate delle reti di input (scambiando gli archi dei nodie mantenendo invariati i loro gradi);

p(u, v) sara il numero di reti random in cui esiste un link tra ue v .

La probabilita (likelihood) che un insieme di proteine C con unset di interazioni E(C) formi un complesso e:

L(C ) =∑

(u,v)∈E(C) log βp(u,v) +

∑(u,v)/∈E(C) log 1−β

1−p(u,v)




M-GRAAL


Procedura di ricerca

Metodo greedy (generale):

1 Si parte da seed promettenti, raffinati utilizzando una ricercalocale;

2 Iterativamente si effettua una modifica (inserimento ocancellazione di una proteina), quella che contribuiscemaggiormente ad aumentare lo score, finche non sono possibiliulteriori modifiche.




M-GRAAL


Predizione a partire dal network alignment

L’allineamento di network consente di predire:

funzioni e proprieta di geni e proteine su scala globale;nuove interazioni tra proteine, ortologie funzionali ecollegamenti tra processi cellulari.

Una subnetwork conservata che contiene molte proteine chesvolgono una stessa funzione conosciuta consente di dire cheanche le restanti proteine svolgono la stessa funzione.




M-GRAAL


Algoritmi di allineamento pairwise

PathBLAST (2003, Kelley et al.): usa lo schema di scoringlikelihood-based per ricercare pathway conservate.

Esteso nel 2005 (Sharan et al.), tramite euristica greedy, perdeterminare complessi di proteine conservati.

MaWISh (2006, Koyuturk et al.): usa lo schema di scoringevolution-based per trovare cluster di proteine conservati.

NetworkBLAST-E (2007, Hirsh e Sharan): introduce unmodello evoluzionario di network nella funzione di scoring.

MNAligner (2007, Li et al.): descrive un modello diprogrammazione quadratica intera per l’individuazione deicomplessi conservati.




M-GRAAL


Algoritmi di allineamento pairwise (cont.)

IsoRank (2007, Singh et al.): descrive un metodo ispirato alPage Rank di Google.

GRAAL, H-GRAAL, M-GRAAL (2010, Kuchaiev e Przulj).




M-GRAAL


Multiple network alignment

Generalizzazione del processo di network alignment al caso dipiu di due reti.

Nozione di network alignment graph e schemi di scoring estesi.

Aumento della complessita computazionale, proporzionale anhk−1 per k reti di dimensione n con un numero medio di hpossibili ortologhi per proteina in ogni specie.

k e il vero ’collo di bottiglia’ !




M-GRAAL


Algoritmi di allineamento multiplo

IsoRankN (2008, Singh et al.): descrive un metodo ispirato alPage Rank di Google per l’allineamento globale di 5 reti PPIdi eucarioti.

Graemlin (2006, Flannick et al.): capace di allineare almeno10 reti microbiali.

NetworkBLAST (2005, Sharan et al.): un’altra estensione diPathBLAST, puo allineare fino a 3 specie.

NetworkBLAST-M (2008, Kalaev, Sharan et al.): estensionedi NetworkBLAST, capace di allineare almeno 10 reti dimigliaia di proteine in pochi minuti. Attualmente e il piuaccurato e veloce.

LGA Gibbs Sampler (2011): ???




M-GRAAL


Outline



3 Network evolution


5 M-GRAAL




M-GRAAL


Network integration

Ogni tipo di network (PPI, genetica, ecc.) rappresenta unadiversa conoscenza di un processo biologico.

Integrare reti di tipo diverso permette di avere un quadrocomplessivo del sistema in esame.

Combinare dati provenienti da piu sorgenti permette di predirela funzione di una proteina e nuove interazioni.

Obbiettivo: unire le reti in un’unica network con piu tipi diinterazioni, ad esempio per individuare in essa modulifunzionali supportati da piu interazioni possibili.

Le reti devono essere definite sullo stesso set di elementi (ades. lo stesso set di proteine di una certa specie).




M-GRAAL


Un esempio di integrazione

Studio di correlazioni tra interazioni proteina-proteina einterazioni genetiche in Saccaromyces Cerevisiae (Kelley etal.).

Due strutture ricercate nella network integrata:

Subnetworks della PPI interconnesse tra loro tramite unelevato numero di interazioni genetiche;Cluster ’ricchi’ sia di interazioni genetiche che fisiche.

Il primo tipo di struttura e piu prevalente.

Interpretazione: le interazioni genetiche tendono a collegaregeni che operano in pathway diverse, piuttosto che occorrerein sottounita proteiche di una stessa pathway.




M-GRAAL


Un esempio di integrazione (cont.)

Blue versus dotted-red links correspond to protein-protein versus genetic interactions




M-GRAAL


Altri esempi

Studio di correlazione tra PPI, network di coespressi e networkdi similarita fenotipica in C. Elegans (Gunsalus et al).

Un cluster di interazioni supportato da piu reti rappresenta,con piu alta probabilita rispetto a uno che emerge in una solanetwork, un reale complesso di proteine.

Studio di sovra-rappresentazione di motivi in PPI e networktrascrizionali combinate (Yeger-Lotem et al.)

La maggior parte dei motivi trovati combina entrambi i tipi diinterazione: cio suggerisce la tendenza di questi set di proteinealla coregolazione e alla formazione di complessi.




M-GRAAL


Outline



3 Network evolution


5 M-GRAAL




M-GRAAL


Network querying

Approccio supervisionato al problema di identificare modulifunzionali.

Obbiettivo: data una subnetwork query, che si sa a prioriessere un modulo funzionale, identificare sottoreti in una datanetwork che sono simili alla query.

Algoritmi attualmente limitati a topologie sparse, come path ealberi.

PathBLAST (Kelley et al., 2003): utilizza una delle networkdell’allineamento come query;(Pinter et al., 2005): ricercare pathway metaboliche (anche aforma di albero) in network metaboliche.




M-GRAAL


Esempio di network querying

A query of a core pathway revealed in allantoin degradation pathway in E. Coli and a ureide degradation pathwayin yeast.




M-GRAAL


Riassumendo...




M-GRAAL

Outline



3 Network evolution


5 M-GRAAL




M-GRAAL

Network evolution

Capire come si evolve una network puo aiutare nello studio dinetwork comparison e nell’analisi di network in generale.

Due tipi di processi per spiegare l’evoluzione di una rete:1 Link attachment and detachment;2 Gene duplication.




M-GRAAL

Link attachment and detachment (Link dynamics)

Un gene muta nella sua sequenza;

La nuova proteina corrispondente puo acquisire nuoveconnessioni (attachment) o perdere alcune connessioniesistenti con altre proteine (detachment).




M-GRAAL

Gene duplication

Un gene viene duplicato;

Si produce una nuova proteina che si lega inizialmente aglistessi nodi vicini;

Alcune di queste connessioni vengono successivamenteperdute.




M-GRAAL

Osservazioni

La duplicazione del gene e ’imperfetta’.

Un gene duplicato dovrebbe interagire con gli stessi vicini delgene originale.

Sperimentalmente si osserva che le duplicazioni sono moltomeno frequenti rispetto ai link dynamics.

Per questo motivo alcuni link ridondanti vengonosuccessivamenti perduti.




M-GRAAL

Alcuni modelli di evoluzione

Berg et al.:

Le link dynamics influenzano soprattutto la topologia dellanetwork;I processi di duplicazione influenzano principalmente ladimensione della rete.

Barabasi e Albert:

La duplicazione e il meccanismo principale che determina latopologia scale-free delle PPI.Le molecole ’ancestrali’ sono anche quelle piu connesse.Reti metaboliche: i metaboliti di alcune delle piu antichepathway, come la glicolisi, sono tra i sottostrati piu connessi.PPI: correlazione positiva tra l’eta evoluzionaria di unaproteina e il suo grado di connessione.




M-GRAAL

Outline



3 Network evolution


5 M-GRAAL




M-GRAAL

Sviluppi della network comparison




M-GRAAL

Sviluppi della network comparison (cont.)

La network comparison e un ambito ’giovane’ e ancora poverodi metodologie computazionali avanzate.

Analogie con lo sviluppo della sequence comparison:

Passaggio dall’allineamento pairwise a quello multiplo;

Tante differenze:

Primi algoritmi di allineamento di reti proposti tre-quattro annidopo la nascita dei primi database di interazioni;Problema della ricerca di motivi nelle reti affrontatorelativamente presto nella network comparison;Differenze computazionali tra le due metodologie.Tecniche di integrazione presenti solo nel confronto tranetwork: combinare sequenze di nucleotidi e aminoacidi non hamolto senso.




M-GRAAL

Sviluppi della network comparison (cont.)

Un mapping sempre piu accurato e crescente delle varieinterazioni sara probabilmente cruciale nello sviluppo futuro ditecniche di network comparison.

Innovazioni simili al modello di sostituzione di nucleotidi diJukes/Cantor potrebbero contribuire alla creazione di funzionidi scoring piu legati al modello evoluzionario delle network.




M-GRAAL

Outline



3 Network evolution


5 M-GRAAL




M-GRAAL

Allineamento locale vs globale

Local alignment: trovare piccole subnetwork checorrispondono a pathway o complessi di proteine, conservati innetwork di diverse specie.

Puo essere ambiguo (diversi accoppiamenti per uno stessonodo).

Global alignment: misura la similarita complessiva di due opiu reti allineando ciascun nodo nella rete piu piccola con unoe un solo nodo nella rete piu grande.

Puo portare a match subottimali in alcune regioni locali.




M-GRAAL

Caratteristiche principali di M-GRAAL

Matching-based GRAph ALigner (Kuchaiev e Przulj, 2010).

Algoritmo di allineamento pairwise globale.

Applicabile a network di qualsiasi tipo.

Allineamento basato sulla topologia della rete.

Definisce una funzione di score (confidenza) degliaccoppiamenti basata sul concetto di graphlet degree (GRAALe H-GRAAL).

Utilizza un approccio greedy seed-and-extend per costruire unaccoppiamento ottimale (GRAAL).

Permette di costruire un albero filogenetico delle specie apartire dagli score di similarita pairwise di un insieme di reti.




M-GRAAL

Informazioni di similarita

M-GRAAL utilizza diverse sorgenti di informazioni pervalutare la similarita tra due nodi.

E’ possibile considerare qualsiasi numero e tipo di misure disimilarita.

Ogni tipo di misura contribuisce in maniera indipendente alpunteggio complessivo.

M-GRAAL combina queste misure per decidere se accoppiaredue nodi.




M-GRAAL

Informazioni di similarita (cont.)

Vantaggi:

Molto flessibile;

Permette di integrare informazioni di similarita molto diversetra loro (topologie, strutture, ontologie, sequenze);

Consente di risolvere facilmente le situazioni di parita negliscore:

Non abbiamo bisogno di fare scelte casuali per spezzare laparita;Algoritmo stabile, cioe non produce allineamentisostanzialmente diversi in varie esecuzioni.




M-GRAAL

Misure di similarita considerate

1 Graphlet degree signature distance (SD);

2 Relative degree difference (DD);

3 Relative clustering coefficient difference (CD);

4 Relative eccentricity difference (ED);

5 BLAST E-value for protein sequence similarity (SeqD).




M-GRAAL

Motivazioni

La graphlet degree signature distance ha gia dimostrato didare ottimi risultati nell’allineamento di network (GRAAL e H-GRAAL).

Grado, coefficiente di cluster e eccentricita sono tra le piucomuni e semplici misure topologiche di un nodo.

Gli E-values di BLAST sono una misura standard per stabilirese due proteine sono ortologhe.

Combinando queste misure si ottiene un algoritmo piu stabilee piu accurato.




M-GRAAL

Graphlet

Definizione

Un sottografo indotto su un insieme di nodi S ⊆ V di un grafo Ge un sottografo ottenuto considerando S e tutti gli archi di G chehanno entrambi i nodi in S .

Definizione

Un graphlet e un piccolo sottografo connesso e indotto di un grafopiu grande




M-GRAAL

Graphlet di 2, 3, 4 e 5 nodi




M-GRAAL

Graphlet degrees

Estendiamo il concetto di grado di un nodo.

Vogliamo definire un vettore di graphlet degrees, checontenga il numero di graphlet toccati dal nodo, per tutti igraphlet da 2 a 5 nodi.

La prima coordinata in questo vettore rappresenta il grado delnodo.

Problema: un nodo puo toccare un graphlet in uno dei suoinodi terminali o in un suo nodo interno. Occorre distinguerecasi del genere.

Il vettore di graphlet degrees dovra avere piu di 30componenti.




M-GRAAL

Esempio

Il nodo v del grafo G puo toccare il graphlet G1 in un nodo esterno(1) oppure nel nodo centrale (2).




M-GRAAL

Automorfismi

Questa distinzione e legata al fatto che G1 ammette unautomorfismo che mappa tra loro i suoi nodi terminali e il nodo dimezzo con se stesso.

Definizione

Un isomorfismo g dal grafo X al grafo Y e una biezione di nodidi X a nodi di Y tale che (x , y) e un arco di X se e solo se(g(x), g(y)) e un arco di Y .

Definizione

Un automorfismo e un isomorfismo da un grafo a se stesso.




M-GRAAL

Orbite di un nodo

L’insieme degli automorfismi di un grafo X , Aut(X ), e ungruppo.

Definizione

Sia x un nodo di X . L’orbita di x rispetto al gruppo degliautomorfismi di X , che chiamiamo semplicemente orbita di x , e:Orb(x) = {y ∈ V (X ) : y = g(x) per qualche g ∈ Aut(X )}

L’insieme V (X ) resta partizionato in classi di equivalenzadalla relazione Orb.




M-GRAAL

Esempio: automorfismi di G1

Orb(a) = Orb(c) = {a, c}, Orb(b) = {b};Due classi di equivalenza.




M-GRAAL

Segnatura di un nodo

Se calcoliamo, per ciascuno dei 30 graphlet e per ogni nodo diun graphlet, le orbite dei nodi restano individuatecomplessivamente 73 classi di equivalenza (una per G0, dueper G1, una per G2, ecc...).

Sfruttando la relazione di equivalenza, possiamo scegliere unrappresentante di ogni classe ed etichettarlo con un indice (da0 a 72), che individua l’orbita stessa.

Per ciascun nodo v costruiamo un vettore GDV di 73componenti, che chiamiamo segnatura di v , che conta ilnumero di volte che v e toccato dal graphlet nel nodorappresentante dell’orbita.




M-GRAAL

Le 73 orbite




M-GRAAL

Esempio di segnatura




M-GRAAL

Osservazioni

La segnatura di un nodo descrive la topologia locale del suo’vicinato’ e cattura la sua interconnettivita fino a distanza 4.

Confrontare la segnatura di due nodi permette di misurare laloro similarita topologica locale.

Considerare graphlet piu grandi non ha senso:

Natura small-world di molte reti reali;Il numero di graphlet con n nodi aumenta esponenzialmentecon n.




M-GRAAL

Distanza tra orbite

Sia u un nodo del grafo G e ui l’i-esima componente dellasegnatura di u. La distanza Di (u, v) tra l’i-esima orbita di u equella di v e definita da:

Di (u, v) = wi × | log(ui+1)−log(vi+1)|log(max{ui ,vi}+2)

wi e un peso fissato per lo score della i-esima orbita, che tieneconto delle dipendenze tra le orbite.

Pesi decrescenti all’aumentare di i .

Ad esempio, una differenza nell’orbita 0 implica una differenzain tutte le altre orbite tra i due nodi.




M-GRAAL

Graphlet degree signature distance (SD)

SD(u, v) =∑72

i=0 Di (u,v)∑72i=0 wi

Valore normalizzato tra 0 e 1;

Distanza 0 significa che le segnature di u e v sono identiche;

Bassa distanza = alta similarita topologica tra i vicinati (finoa distanza 4) di u e v .




M-GRAAL

Relative degree difference (DD)

Sia degree(x) il grado di un nodo x in un grafo.

DD(u, v) = |degree(u)−degree(v)|max{degree(u),degree(v)}




M-GRAAL

Relative clustering coefficient difference (CD)

Sia c(u) il coefficiente di clustering del nodo u in un grafo.

c(u) = 2×Eudegree(u)×(degree(u)−1)

dove Eu e il numero di archi tra i vicini di u.

CD(u, v) = |c(u)−c(v)|max{c(u),c(v)}




M-GRAAL

Relative eccentricity difference (ED)

L’eccentricita di un nodo u in un grafo e la massima distanza diun qualsiasi altro nodo da u (nella componente connessa in cui sitrova u) in un cammino di lunghezza minima.Se con eccen(u) indichiamo l’eccentricita di u:

ED(u, v) = |eccen(u)−eccen(v)|max{eccen(u),eccen(v)}




M-GRAAL

Score di confidenza

Per ciascuna delle 5 misure di similarita considerate, si ottieneuna matrice di dimensione V1 × V2.

Siano SD,DD,CD,ED e SeqD le 5 matrici, i ∈ V1 e j ∈ V2

due nodi.

Indichiamo con confX (i , j) la frazione di elementi nella i-esimariga della matrice X che sono maggiori di X (i , j), dove X staper SD, DD, ED, CD oppure SeqD.

Se X (i , j) e il piu piccolo valore della riga i di X , allora ilgrado di ’confidenza’ con cui i debba essere allineato con j e il100%.




M-GRAAL

Score di confidenza (cont.)

Lo score di confidenza tra due nodi i e j e:

C (i , j) = confSD(i , j) + confDD(i , j) + confCD(i , j) + confED(i , j)+ confSeqD(i , j)




M-GRAAL

Qualita dell’allineamento

Sia f la mappa dell’allineamento delle network G1(V1,E1) eG2(V2,E2).

Supponiamo che |V1| ≤ |V2.

Definiamo la misura di Edge Correctness (EC):

EC = |{(u,v)∈E1 ∧ (f (u),f (v))∈E2}||E1| × 100%

Obbiettivo: massimizzare EC.




M-GRAAL

M-GRAAL - Passi preliminari

Costruzione della matrice C degli score di confidenza per tuttele coppie di nodi (i , j) con i ∈ V1 e j ∈ V2;

Costruzione di una coda di priorita di coppie di nodi in ordinedecrescente di score di confidenza.

La coda di priorita serve per identificare velocemente le coppieseed.




M-GRAAL

Identificazione del seed




M-GRAAL

Estensione della mappa dell’allineamento A




M-GRAAL

K-esimo vicinato di un nodo

Siano u e v due nodi di un grafo G . La distanza tra u e v ,distG (u, v), e la lunghezza di un cammino di lunghezzaminima da u a v in G .

Il k-esimo vicinato di u in G , NkG (u), e l’insieme dei nodi di

G a distanza al piu k da u.




M-GRAAL

Align-neighborhoods




M-GRAAL

’Compressione’ dei grafi




M-GRAAL

’Compressione’ dei grafi (cont.)

E’ possibile che l’algoritmo alla fine non riesca a mappare tuttii nodi di G1 con nodi di G2.

Un grafo G innalzato ad una potenza p e definito comeGp = (V (G ),Ep) dove:

Ep = {(u1, u2) : distG (u1, u2) ≤ p}Innalzando a potenza i due grafi (prima al quadrato, poi alcubo) si ottengono grafi ’compressi’ in cui i nodi si’avvicinano’.

Coppie che in precedenza nel grafo bipartito non eranocollegate ora potrebbero esserlo, cioe nuove coppie di nodipotrebbero aggiungersi all’allineamento parziale A prodotto.




M-GRAAL

Complessita computazionale

Costruzione matrice di confidenza e coda priorita:O(|V1| × |V2| ∗ log |V2|).

Align-neighborhoods:O(|N1 + N2| × (|E |+ |N1 + N2| × log(|N1 + N2|))).

Complessita:

temporale: O(|V1| × (|E1|+ |V1| × log(|V1|)).spaziale: O(|V1| × |V2|+ |E1|+ |E2|).

In pratica, le reti biologiche sono sparse, cioe |E | = O(|V |),quindi la complessita temporale e O(|V |2 log |V |).




M-GRAAL

Risultati

Allineamento yeast-human network PPI.

Indichiamo con σ la deviazione standard.

Tre tipi di test (30 esecuzioni):

Solo SD: max(EC) = 23.26%, σ = 1.39%;Solo SeqD: max(EC) = 13.73%, σ = 0.23%;Tutti e 5 gli score: max(EC) = 18.68%, σ prossima a zero.

Tempo di esecuzione: 1.5 ore.




M-GRAAL

Confronti

IsoRank: max(EC) = 3.89%, LCCS formata da 261 interazionitra 116 proteine;

GRAAL: max(EC) = 11.72%, LCCS formata da 900interazioni tra 267 proteine;

H-GRAAL: max(EC) = 10.92%, LCCS formata da 1290interazioni tra 317 proteine;

M-GRAAL: max(EC) = 23.26%, LCCS fomata da 3467interazioni tra 1858 proteine.




M-GRAAL

Albero filogenetico




M-GRAAL

Riferimenti bibliografici

Roded Sharan, Trey Ideker

Modeling cellular machinery through biological network comparison

Nature Biotechnology Vol. 24, Num. 4 (2006).

Natasa Przulj

Biological network comparison using graphlet degree distribution

Bioinformatics Vol. 26, 6 (2010).

Tijana Milenkovic, Weng Leong Ng, Wayne Hayes, Natasa Przulj

Optimal Network Alignment with Graphlet Degree Vectors

Cancer Informatics Vol. 9, 121-137 (2010).

Oleksii Kuchaiev, Natasa Przulj

Global Network Alignment

Nature Precedings (2010).


Tecniche di network comparison / M-GRAAL - Seminario di...

Documents

Transcript of Tecniche di network comparison / M-GRAAL - Seminario di...