Network Biologiche
Indice
Esempi di network biologiche
– Network di interazione proteina proteina (PPI networks)
– Network metaboliche
– Pathway
Caratterizzazione delle network (grafi)
– Grafi random
– Network scale-free
– Network gerarchici
Esempi di topologie scale-free e gerarchiche
Rilevamento della struttura modulare
– Algoritmi tradizionali
Misure di distanza
Single linkage clustering
Average linkage clustering
– Algoritmi basati su betweenness centrality (Girvan, Newman)
– Applicazioni su network sociologiche, metaboliche e biochimiche
PPI network
Interazioni tra proteine
– Una proteina crea un legame
temporaneo o permanente con
un’altra proteina o con un gruppo di
proteine
– Nel caso di legame di lungo periodo
si ha un complesso proteico
– I legami per brevi periodi servono a
svolgere alcune funzioni della cellula:
trasporto, segnalazione etc.
– Tutte le interazioni possono essere
rappresentate attraverso una grande
network in cui i nodi sono proteine e
gli archi rappresentano le interazioni
tra proteine
Colicin-immunity protein complex
David Masica, Mike Daily, and Jeff Gray, March 2004
RanGTP Cycle and Nuclear Import/Export
(Nakielny and Dreyfuss, 1999)
Network metaboliche
Rappresentano un insieme di
reazioni chimiche in una cellula
– Un insieme di metaboliti
(composti chimici) subiscono
delle trasformazioni (reazioni
chimiche) catalizzate da altre
sostanze (enzimi)
– Alla network possono essere
aggiunti altri elementi:
interazioni con proteine,
elementi regolatori
Schwarz et al. BMC Bioinformatics 2007
Pathway
Una pathway rappresenta un
determinato processo
biologico (es. apoptosi)
– Nodi: proteine, metaboliti, piccole
molecole, geni, RNA, tutto ciò che è
coinvolto nei processi in questione
– Archi: relazioni tra i nodi (interazioni,
trasformazioni, etc.)
Indice
Esempi di network biologiche
– Network di interazione proteina proteina (PPI networks)
– Network metaboliche
– Pathway
Caratterizzazione delle network (grafi)
– Grafi random
– Network scale-free
– Network gerarchici
Esempi di topologie scale-free e gerarchiche
Rilevamento della struttura modulare
– Algoritmi tradizionali
Misure di distanza
Single linkage clustering
Average linkage clustering
– Algoritmi basati su betweenness centrality (Girvan, Newman)
– Applicazioni su network sociologiche, metaboliche e biochimiche
Caratteristiche di una network
Grado
– Di un nodo: numero di archi entranti e/o uscenti
– Di un grafo: media dei gradi dei nodi
Distribuzione del grado
– P(k) = N(k) / n
– Poisson
– Esponenziale
Lunghezza del cammino minimo
– Tra due nodi
– Media di un grafo
Coefficiente di clustering
– Di un nodo: Ci = 2ni/[ki(ki-1)]
– Di un grafo: media dei coefficienti dei nodi
– Dipendenza dal grado: C(k)
Network Biology
COEFFICIENTE DI CLUSTERING
In molte network se A è connesso con B (con un link diretto) e B è
connesso con C allora con alta probabilità anche A ha un link diretto a
C.
Questo fenomeno può essere quantificato con
Ci 
2ni
k (k  1)
Dove ni è il numero di link che connettono i k vicini del nodo i ad ogni
altro.
La media <C> caratterizza la tendenza globale dei nodi a formare
cluster.
Network Biology
COEFFICIENTE DI CLUSTERING
In altre parole Ci da il numero di
triangoli che passano attraverso i.
k(k-1)/2 è il numero massimo
possibile di triangoli.
Esempio:
Solo B e C fra i vicini di A sono
linkati. Quindi:
nA=1 CA=2/20
Invece per F si ha CF=0
Network Biology
COEFFICIENTE DI CLUSTERING
Ha molta importanza anche la funzione C(k) definita come la media
del coefficiente di clustering per tutti i nodi con k link.
Per molte network reali si ha:
C (k )  k 1
Ciò caratterizza una rete gerarchica.
Grafi random
Presi n nodi, per ogni coppia di nodi si inserisce un arco
con probabilità p
Caratteristiche
– Grado medio: p(N-1)
– Distribuzione del grado: di Poisson
– Lunghezza del cammino minimo: l  log n
– Coefficiente di clustering medio: C = p
– Coeff. clustering costante al variare del numero di nodi
I grafi random presentano caratteristiche differenti
da quelle delle network biologiche (e in generale
di altri tipi di network). Infatti, le network risentono
dei fenomeni di attaccamento preferenziale e
duplicazione genica.
I grafi random non descrivono bene le reti reali
Attaccamento
preferenziale
Duplicazione
genica
Network scale-free
I nodi vengono aggiunti uno per volta. Ogni nuovo nodo
viene connesso a un altro nodo i della rete con
probabilità i = ki /j kj
Caratteristiche
– Distribuzione del grado esponenziale: P(k)  k -
<3. Infatti più piccolo è il valore di  più i clusters sono rilevanti.
Con >3 i clusters perdono di importanza e non è più scalefree
– Presenza di hub
– Lunghezza del cammino minimo: l  log log n.
– Coefficiente di clustering basso
– Coeff. clustering non dipendente dal grado
– Coeff. di clustering decrescente sul numero di nodi (N-0,75)
Network gerarchiche
Caratteristiche delle network gerarchiche
Topologia scale-free
– Distribuzione di grado esponenziale
– Presenza di hub
– Lunghezza del cammino minimo: l  log log n.
Clustering
– Alto coefficiente di clustering medio C = 0,6
– Dipendenza del coefficiente di clustering dal grado:
C(k) = 1/k
– Coeff. clustering costante al variare del numero di nodi
Struttura delle network gerarchiche
Modularità: la rete è suddivisa in sottoinsiemi di nodi detti moduli (o
cluster)
– connessioni tra nodi dello stesso cluster molto dense
– connessioni tra nodi di differenti cluster poco dense
Struttura gerarchica
– I moduli sono connessi formando meta-moduli
– I meta-moduli sono connessi in maniera più debole formando una
gerarchia di moduli (gerarchia di cluster)
Confronti
Grafi
random
scale-free
gerarchiche
Distribuzione di grado
Poisson
esponenziale
esponenziale
No
Si
Si
Lungh. Cammino minimo
 log n
 log log n
 log log n
Coeff. di clustering medio
p
basso
alto (0,6)
Coeff. di clustering - grado
no
no
1/k
costante
decrescente
N-0,75
costante
Esistenza di hub
Coeff. di clustering - nodi
Esempi di network scale-free e gerarchiche
Network sociologiche
– Network di conoscenze
– Network di collaborazione
Reti tecnologiche
– Internet
– World Wide Web
– Reti elettriche
Network biologiche
– Network di interazioni (tra proteine, RNA, DNA, piccole molecole)
– Network metaboliche
– Network cellulari
– Food web
Indice
Esempi di network biologiche
– Network di interazione proteina proteina (PPI networks)
– Network metaboliche
– Pathway
Caratterizzazione delle network (grafi)
– Grafi random
– Network scale-free
– Network gerarchici
Esempi di topologie scale-free e gerarchiche
Rilevamento della struttura modulare
– Algoritmi tradizionali
Misure di distanza
Single linkage clustering
Average linkage clustering
– Algoritmi basati su betweenness centrality (Girvan, Newman)
– Applicazioni su network sociologiche, metaboliche e biochimiche
Rilevamento della struttura modulare
Network sociologiche
– Gruppi di individui legati da interessi in comune
– Gruppi reali, società, club, associazioni, famiglie
Reti tecnologiche (web)
– Gruppi di pagine su argomenti correlate (reti di link)
– Gruppi di articoli su uno stesso argomento (reti di citazioni)
Network biologiche
– Gruppi funzionali o moduli (reti metaboliche)
Rilevamento della struttura modulare
Albero di clustering o Dendogramma
Algoritmi di clustering
Tradizionali
– Si calcola un peso Wij per ogni coppia di nodi i, j del grafo
Overlap topologico
Numero di path indipendenti (massimo flusso)
Numero di path totali
– Si applica un algoritmo di clustering classico usando come distanza
l’inverso del peso (approccio bottom-up)
Single linkage clustering
Average linkage clustering
Basati su betweenness centrality
– Approccio top-down. Si eliminano gli archi meno centrali (con maggiore
betweenness)
Overlap topologico
Overlap topologico OT(i,j) tra due nodi i e j
– Numero di nodi vicini di i oppure di j
– Numero di nodi vicini sia di i che di j
– Rapporto tra i due valori
OT(i,j) = 1 se i e j sono connessi agli stessi nodi
OT(i,j) = 0 se i e j non hanno vicini in comune
Numero di path indipendenti
Numero di cammini indipendenti tra due nodi
– Due cammini sono indipendenti se non hanno archi in comune
Trovare il massimo flusso tra i nodi (max-flow)
Equivalente a trovare il taglio minimo (minimum-cut)
Algoritmo Ford-Fulkerson (tempo polinomiale)
Algoritmo Ford-Fulkerson
4
2
5
3
1
1
1
2
s
2
4
3
t
2
1
3
Esempio: trovare il massimo flusso tra s e t
Ford-Fulkerson Max Flow
1
2
5
1
1
2
s
2
4
2
t
2
3
Questo è il massimo flusso
27
Numero di path totali
Numero di cammini tra due nodi (non per forza indipendenti)
Problema
– Se un cammino ha un ciclo esistono infiniti cammini
Soluzione
– ogni cammino è pesato di un fattore αl con l = lunghezza del path
Single linkage clustering
Definita una funzione distanza tra nodi d(xi,xj) mediante matrice di
adiacenza
Si prende l’insieme di nodi senza archi
Si seleziona la distanza più bassa. Si aggiunge un arco tra i nodi
coinvolti. Se l’arco unisce due cluster si genera un nuovo cluster che
li contiene
Si procede iterativamente prendendo distanze via via crescenti
Alla fine si ottiene un albero rappresentante la gerarchia di cluster
Average linkage clustering
Definita una funzione distanza tra nodi d(xi,xj) mediante matrice di
adiacenza
Si definisce la distanza tra due cluster CK, CL come la media delle distanze
tra tutte le copie appartenenti a cluster diversi
Si sceglie la coppia di nodi con distanza minore e si uniscono in un
cluster.
Si calcola la distanza del nuovo cluster da tutti gli altri nodi della rete
(come media delle distanze di ogni nodo dai nodi del cluster)
Si aggiornano le entry della matrice di adiacenza relative ai nodi del
cluster mettendo le distanze del cluster
Si procede in maniera iterativa
Rilevamento della struttura modulare
Consideriamo la network metabolica dell’
Escherichia coli, la cui classificazione
funzionale dei metaboliti è stata ben studiata
Applichiamo l’algoritmo average-linkage
clustering per rilevare la struttura modulare
della network metabolica
Confrontiamo i risultati (moduli rilevati) con le
caratteristiche conosciute (caratterizzazione
funzionale dei metaboliti)
Ravasz et. al.
Algoritmo
Calcoliamo la matrice di overlap OT(i,j) della network metabolica
Applichiamo l’algoritmo di clustering gerarchico (average-linkage
method of Sokal e Michener)
Output: albero di clustering gerarchico (dendogramma)
Esempio
Ravasz et. al.
Risultati
Blu = metabolismo dei
carboidrati
Rosso = metabolismo dei
nucleotidi e acido nucleico
Verde = metabolismo delle
proteine e aminoacidi
Ciano = metabolismo dei
lipidi
Rosa = metabolismo dei
composti aromatici
Giallo = metabolismo dei
composti del carbonio
Arancione = metabolismo dei
coenzimi
Ravasz et. al.
Problemi
Overlap topologico
– Vengono considerate solo le caratteristiche locali ad ogni nodo
Numero di path indipendenti
– Se un nodo e connesso con un unico link, il numero di path indipendenti
con tutti gli altri nodi è 1 (minore di tutti gli altri nodi)
– Scarsi risultati su network la cui struttura modulare è ben conosciuta
Indice
Esempi di network biologiche
– Network di interazione proteina proteina (PPI networks)
– Network metaboliche
– Pathway
Caratterizzazione delle network (grafi)
– Grafi random
– Network scale-free
– Network gerarchici
Esempi di topologie scale-free e gerarchiche
Rilevamento della struttura modulare
– Algoritmi tradizionali
Misure di distanza
Single linkage clustering
Average linkage clustering
– Algoritmi basati su betweenness centrality (Girvan, Newman)
– Applicazioni su network sociologiche, metaboliche e biochimiche
Approccio Girvan-Newman
Si parte dal grafo completo
Si identificano gli archi (o i nodi) meno centrali (con alta betweenness)
Si eliminano gli archi (o i nodi) meno centrali e poi via via quelli più
centrali. Ogni volta che si separano due componenti, queste vengono
riportate nell’albero di clustering
Betweenness di un nodo
Proposta originariamente da Freeman
– Fissato un nodo r
– Tra tutte le coppie di nodi si considerano i cammini minimi (per ogni
coppia ce ne può essere più di uno)
– Tra tutti i cammini minimi di una coppia di nodi m, m’ (mm’) si prendono
tutti i cammini minimi che passano per r (mm’ (r))
– Si calcola il rapporto mm’ (r) / mm’
– Si sommano tutti i rapporti calcolati per tutte le coppie di nodi
Betweenness di un arco
Analoga alla betweenness di un nodo
Algoritmo di Newman per il calcolo delle betweenness di tutti gli archi
– Complessità O(mn)
Algoritmo
Calcola la betweenness di tutti gli archi del grafo utilizzando
l’algoritmo di Newman
Rimuovi l’arco con betweenness più alta
Ricalcola la betweenness di tutti gli archi della componente affetta
dalla rimozione
Ripeti iterativamente finchè non ci sono più archi da rimuovere
Complessità: O(m2n) (in media è inferiore)
Indice
Esempi di network biologiche
– Network di interazione proteina proteina (PPI networks)
– Network metaboliche
– Pathway
Caratterizzazione delle network (grafi)
– Grafi random
– Network scale-free
– Network gerarchici
Esempi di topologie scale-free e gerarchiche
Rilevamento della struttura modulare
– Algoritmi tradizionali
Misure di distanza
Single linkage clustering
Average linkage clustering
– Algoritmi basati su betweenness centrality (Girvan, Newman)
– Applicazioni su network sociologiche, metaboliche e biochimiche
Karate club di Zachary
Osservazioni su 34 membri di un karate club in un periodo di 2 anni
– Rete di amicizie tra i membri del club
Durante lo studio ci fu un disaccordo tra l’amministratore del club e
l’istruttore
L’istruttore lasciò il club e ne creò un altro portando con se circa la
metà dei membri
Karate club di Zachary
Nuovo club
Dendogramma
Rete di amicizie
Club originario
Classificazione
non corretta
Incontri di football americano
Istituto Santa Fe
Chesapeake Bay food web
Applicazione alle network cellulari
Struttura network biochimiche (grafo bipartito)
– Sostanze: Metaboliti, Macromoduli, Complessi
– Reazioni
– Ogni sostanza è collegata ad un’altra attraverso una reazione
– Una reazione ha archi entranti (sostanze che partecipano alla reazione)
e archi uscenti (il risultato della reazione)
Algoritmo di Girvan Newman modificato
– Si calcola la betweenness per tutti i nodi reazione e si divide per il
numero di archi entranti
– Si eliminano i nodi reazione in sequenza (analogamente all’algoritmo di
Girvan e Newman)
Applicazione alle network cellulari
Struttura network biochimiche (grafo bipartito)
– Sostanze: Metaboliti, Macromoduli, Complessi
– Reazioni
– Ogni sostanza è collegata ad un’altra attraverso una reazione
– Una reazione ha archi entranti (sostanze che partecipano alla reazione)
e archi uscenti (il risultato della reazione)
Algoritmo di Girvan Newman modificato
– Si calcola la betweenness per tutti i nodi reazione e si divide per il
numero di archi entranti
– Si eliminano i nodi reazione in sequenza (analogamente all’algoritmo di
Girvan e Newman)
Risultati
Holme, Huss, Jeong
Topologie
Sono presenti due diverse topologie:
– Community-type ordering (fig. a): c’è una netta suddivisione tra i moduli
– Shell-type ordering (fig. b): partendo da un modulo più piccolo vengono
aggiunti nuovi elementi generando moduli sempre più grandi (struttura a
conchiglia)
Holme, Huss, Jeong
Conclusioni
L’analisi delle network è un processo importante nella comprensione dei
processi cellulari. PPI networks e network metaboliche sono molto
importanti in biologia.
Il modello che meglio si adatta allo studio di network presenti in natura
(biologiche, sociologiche) è la network gerarchica
Gli algoritmi di clustering sono molto utili per identificare insiemi di
componenti che contribuiscono a svolgere una stessa funzione (moduli
funzionali o complessi). Algoritmi di clustering tradizionali possono essere
utilizzati con opportune misure di distanza. Gli algoritmi basati su
betweenness centrality hanno dato risultati migliori rispetto agli algoritmi
classici.
Approfondimenti
Network biology: Understanding the cell’s functional organization
Ravasz, Somera, Mongru, Oltvai, Barabàsi – Science 297 (2002)
Hierarchical organizzation of modularity in metabolic network
Ravasz, Somera, Mongru, Oltvai, Barabàsi – Science 297 (2002)
Community structure in social and biological networks
Michelle Girvan, M. E. J. Newman – Proc. Natl. Acad. Sci. USA 99 (2002)
Subnetwork hierarchies of biochemical pathways
Holme, Huss, Jeong – Bioinformatics 19 (2003)
Modular organization of cellular network
River, Galitski - Proc. Natl. Acad. Sci. USA 100 (2003)