Reti biologiche e
allineamento
Giovanni Micale
PhD student
Department of Computer Science
University of Pisa
[email protected]
Outline
• Reti biologiche
• Analisi comparativa di reti biologiche
• Allineamento di reti:
o Allineamento di reti PPI
• GASOLINE
o Allineamento di protein structure networks
• PROPOSAL
Reti biologiche
Definizione di rete
Una rete (o grafo) G=(V,E) è una struttura dati definita
da:
• V: insieme di nodi che rappresentano le entità di
una rete;
• E: insieme di archi che descrivono le relazioni tra le
entità. Un arco è una coppia ordinata di nodi.
A
C
A
C
B
D
B
D
Networks everywhere
Reti biologiche
• Descrivono processi biologici che avvengono nella
cellula a diversi ‘livelli di risoluzione’;
• Descrivono l’insieme delle interazioni fisiche o
reazioni chimiche tra vari tipi di molecole (es. RNA,
geni, proteine, metaboliti).
• Esempi di reti biologiche:
o
o
o
o
Reti di interazione proteina-proteina (PPI);
Reti trascrizionali;
Reti metaboliche;
Mappe di contatto;
Reti di interazione proteina-proteina (PPI)
• Nodi: proteine;
• Archi: contatti fisici che si stabiliscono tra le proteine come
conseguenza di eventi biochimici o forze elettrostatiche;
• Gli archi possono essere pesati con probabilità di interazione.
Due tipi di interazioni
• Signal transduction: una proteina interagisce con
una o più proteine per trasmettere un segnale o
uno stimolo esterno alla cellula (es. inizio
trascrizione)
o Interazioni a catena (solitamente mediante fosforilazione);
o Interazioni tipicamente transitoria.
• Complex assembly: un insieme di proteine si unisce
a formare una struttura cellulare più grande
(complesso)
o Interazioni stabili tra tutte le proteine del complesso
Identificare PPIs
• Metodi sperimentali e computazionali;
• Metodi per individuare interazioni fisiche:
o Yeast 2-hybrid (Y2H) screening;
o Mass spectrometry;
• Metodi per individuare associazioni funzionali:
o Correlazione di profili di espressione di mRNA;
o Interazioni genetiche;
o Metodi in silico (ad esempio gene fusion)
Banche dati di PPIs
• Biological General Repository for Interaction
Datasets (BioGRID)
• Human Protein Reference Database (HPRD)
• Saccharomyces Genome Database (SGD)
• Search Tool for the Retrieval of Interacting
Genes/Proteins (STRING)
• Molecular interaction database (IntAct)
• Database of Interacting Proteins (DIP)
• Molecular Interactions Database (MINT)
• …
Limitazioni su PPI data
• Alto tasso di falsi positivi e negativi;
• Incompletezza dei dati attuali su molte specie:
o Yeast  50%, Human  10%;
o Le PPI dei virus sono quelle più complete.
• Scarso overlap tra i vari dataset:
o Mancanza di uno standard;
o Inconsistenza del mapping.
• Mancanza di informazioni temporali e relative a
condizioni sperimentali;
• Relazione tra concentrazione di una proteina e il
suo insieme di interattori?
Reti trascrizionali
• Nodi: geni;
• Arco: un gene influenza la produzione di un altro gene, per
mezzo della sua corrispondente proteina (fattore di
trascrizione);
• Due tipi di archi: stimolazione o repressione dell’espressione
del gene.
Reti trascrizionali
• Le più complete sono relative a organismi modello
semplici (lievito, verme, moscerino della frutta);
• Alcune sorgenti di dati:
o
o
o
o
o
o
Kyoto Encyclopedia of Genes and Genomes (KEGG);
RegulonDB;
Reactome;
TRANSPATH;
TRANSFACT;
EcoCyc.
Reti metaboliche
• Usate per descrivere il metabolismo, cioè l’insieme
delle reazioni biochimiche che permettono
all’organismo, si crescere, riprodursi e rispondere
all’ambiente esterno;
• E’ formata da pathway metaboliche;
• La pathway descrive l’insieme delle reazioni
biochimiche necessarie per realizzare una funzione
(ad es. apoptosi e glicolisi)
Reti metaboliche
• I nodi della rete sono metaboliti ed enzimi;
• I metaboliti sono molecole e costituiscono prodotti
intermedi e finali del metabolismo (es. glucosio,
aminoacidi e polisaccaridi);
• Gli enzimi sono proteine che catalizzano le reazioni
chimiche;
• Gli archi (diretti) corrispondono alle reazioni
metaboliche, che convertono un metabolita in un
altro, mediante l’intervento di uno o più enzimi.
Reti metaboliche
Reti metaboliche
• Le reti metaboliche sono ottenute in parte
sperimentalmente e in parte per omologia;
• Dati disponibili per molti organismi;
• Alcuni database:
o
o
o
o
o
o
Kyoto Encyclopedia of Genes and Genomes (KEGG);
GeneDB;
BioCyc;
EcoCyc;
MetaCyc;
ERGO.
Mappe di contatto
• Nodi: aminoacidi;
• Un arco collega due amino acidi se sono sufficientemente
vicini nella struttura tridimensionale della proteina (ad es. 10
Angstrom);
Mappe di contatto
• Mappano la struttura 3D della proteina in modelli
2D (grafi), più semplici da analizzare;
• Invarianti a rotazioni e traslazioni;
• Sotto certe condizioni, è possibile ricostruire le
coordinate 3D di una proteina a partire dalla sua
contact map;
Altre reti biologiche
• Reti neurali: connessioni sinaptiche tra neuroni;
• Reti ecologiche: sistema prede – predatori;
• Reti di correlazioni: descrivono le correlazioni tra le
espressioni dei geni;
o Diversamente dalle reti trascrizionali non sono il risultato diretto di
esperimenti;
• Reti di associazione ‘disease-gene’: lega malattie
causate dallo stesso gene e geni che causano la
stessa malattia;
• Reti di associazione ‘drug-target’: lega drugs che
targettano lo stesso gene (o proteina) e geni (o
proteine) targettate dalla stessa drug.
Analisi comparativa di
reti biologiche
Network vs sequence analysis
• Per molti anni, la ricerca si è concentrata sull’analisi
di singoli geni o proteine, per capirne la loro
funzione;
• Tuttavia alcuni processi sono complessi e
coinvolgono molti geni o proteine;
• L’analisi delle reti biologiche può spiegare meglio il
funzionamento di questi processi
Proprietà delle reti biologiche
• Le reti biologiche (ed in particolare le reti PPI) sono
costituite da piccoli gruppi di proteine altamente
interconnessi (moduli);
• I moduli sono collegati tra loro da un ristretto
numero di proteine di grado elevato (hub), che
corrispondono a proteine ‘centrali’;
• I moduli coinvolgono tipicamente nodi che
svolgono una funzione comune o sono coinvolti
nello stesso processo (ad es. complessi).
Esempio su D. Melanogaster PPI
Analisi comparativa
• Il problema di individuare moduli funzionali nelle reti
biologiche è analogo al problema di individuare
elementi funzionali in sequenze di genomi o
proteine;
• Assunzione biologica: la ‘conservazione’ di una
sottorete di molecole nell’evoluzione di una specie
implica una rilevanza funzionale;
• Conservazione riguarda sia le molecole coinvolte
che le loro interazioni
Tecniche di network comparison
• Network alignment: confrontare due o più reti
biologiche dello stesso tipo ma di specie diverse,
identificando regioni di similarità;
o Individuare moduli funzionali conservati in specie diverse
• Network integration: combinare due o più reti di
diverso tipo ma della stessa specie e definite sullo
stesso set di elementi;
o Individuare moduli di proteine che interagiscono allo stesso modo
mediante interazioni di tipo diverso;
o Predire nuove interazioni.
• Network querying: ricercare, all’interno di una rete,
sottoreti simili ad una rete di interesse (query graph);
o Identificare istanze duplicate o conservate di un modulo
Esempio di network integration
Esempio di network querying
Allineamento di reti
Allineamento di reti
• Date N reti biologiche, individuare un insieme di N
sottoreti di W nodi, una per ogni rete, in modo tale
che la similarità tra le sottoreti sia massimizzata, in
termini di similarità molecolare e topologica;
• W può essere fissato oppure no.
Allineamento locale vs globale
• Allineamento locale: trovare sottoreti locali simili e
‘allineare’ le reti in corrispondenza di queste
sottostrutture;
• Allineamento globale: mappare tra loro i nodi delle
varie reti, cercando di massimizzare il numero di
archi conservati nelle varie reti.
Allineamento di reti PPI
Allineamento di reti PPI
• Allineamento locale: Individuare moduli funzionali
di proteine conservati in specie diverse:
o Complessi (tipicamente sottoreti dense);
o Pathway (tipicamente strutture ad albero o a catena).
• Allineamento globale: misurare la similarità tra
specie diverse a livello di reti PPI (analogo
all’allineamento genomico):
o Valutare la distanza evolutiva tra specie diverse
• Può essere pairwise (due reti) o multiplo (più reti)
Allineamento di reti PPI
• Quali proteine, interazioni tra proteine e gruppi di
interazione hanno funzioni equivalenti tra le specie?
• A partire da queste similarità, è possibile predire la
funzione alcune proteine e nuove interazioni?
• Cosa ci suggeriscono queste relazioni
sull’evoluzione delle proteine, di alcuni processi o
dell’intera rete nei vari organismi?
• E’ possibile migliorare la confidenza che abbiamo
su una interazione, se quest’ultima risulta
conservata tra specie diverse?
Funzione di similarità tra proteine
• Nell’allineamento di reti PPI, occorre definire una funzione di
similarità molecolare tra le proteine;
• Una scelta tipica è quella di considerare il BLAST E-value (o il
Bit Score);
• Le proteine che si corrispondono nell’allineamento sono
considerate ortologhe;
• Ortologhi: proteine che svolgono una funzione simile in specie
diverse;
• Ortologia e similarità sequenziale non sempre coincidono!;
Paraloghi e omologhi
• Una proteina può avere due o più ‘copie’ (più o
meno divergenti) nella stessa specie (paraloghi);
• La presenza di paraloghi è dovuta a processi di
duplicazione e successiva modificazione subiti dalle
proteine nel corso dell’evoluzione;
• Le modifiche possono riguardare anche la rete PPI;
• Paraloghi e ortologhi prendono anche il nome di
omologhi.
Duplication-divergence model
Mapping tra proteine allineate
• Nell’allineamento finale, il mapping prodotto può
essere uno-a-uno oppure molti-a-molti;
• Il mapping molti-a-molti è in grado di considerare
paraloghi e ortologhi, ma può essere più difficile da
interpretare.
Panoramica su algoritmi di allineamento di reti PPI
Un algoritmo di
allineamento di reti PPI:
GASOLINE
GASOLINE
GASOLINE: Greedy and Stochastic algorithm for
Optimal Local alignment of Interaction NEtworks
• Greedy: usa un approccio seed-extend per
cercare sottografi conservati, partendo da
allineamento di singoli nodi (seed
dell’allineamento);
• Stochastic: usa il Gibbs sampling, un metodo
stocastico e probabilistico, per cercare un mapping
ottimale tra i nodi.
Preprocessing
• Obbiettivo: ridurre lo spazio di ricerca per i
potenziali seed;
• Si ‘marcano’ le proteine che hanno ortologhi in
tutte le reti allineate e grado superiore un valore di
soglia σ;
• Tutti i nodi ‘marcati’ nella rete Gi sono aggiunti ad
un insieme Si;
• Gli insiemi S1, S2, …, Sk sono utilizzati come input per
GASOLINE e aggiornati ad ogni iterazione.
Descrizione generale di GASOLINE
Input:
G: set of N PPI networks
S1, S2, …, SN: set of nodes from
networks G1, G2, …, GN marked as
potential seeds
Bootstrap phase: find an
optimal alignment of seeds
False
All aligned
seeds are
orthologs
Remove seeds
from S1, S2, …, SN
True
Save the
alignment found
Iterative phase: iteratively remove and add nodes
True
Extension step:
extend seeds
until the degree
ratio increases
Removal step: remove
the set of mapped nodes
with minimum Goodness
score
S1, S2, …, SN
are not
empty
False
Output:
set of local
alignments of N
subgraphs
A running example
Gibbs sampling
• Sia la fase iniziale (bootstrap phase) che la fase
iterativa (e in particolare ogni estensione) sono
eseguite usando il Gibbs sampling
• Il Gibbs sampling è un metodo di campionamento,
che fa parte della classe dei metodi Markov Chain
Monte Carlo (MCMC);
• Il Gibbs sampling si basa sui concetti di catene di
Markov e distribuzione stazionaria;
Catena di Markov
Def: a catena di Markov è una tripla (Q, P(π1),A):
• Q è un insieme finite di k stati (o eventi);
• πi for i=1, 2, …, è lo stato della catena all’istante di
tempo i;
• P(π1) è la distribuzione di probabilità iniziale degli stati
(probabilità di trovarsi in uno stato all’istante iniziale);
• A = [aij] è una matrice di probabilità di transizione da
uno stato i ad uno stato j.
Tipi di catene di Markov
Def: una catena di Markov del primo ordine è
una catena in cui la probabilità di trovarsi in uno
stato al tempo i+1 dipende soltanto dallo stato
della catena al tempo i:
i ≥ 1, P(πi+1|π1, …, πi) = P(πi+1|πi)
Def: una catena di Markov è finita se l’insieme dei
suoi stati è finito.
Def: una catena di Markov è irriducibile se tutti I
suoi stati sono raggiungibili da qualsiasi stato della
catena.
Tipi di catene di Markov
Def: il periodo di uno stato s della catena di Markov è il numero
minimo di transizioni (con probabilità non nulla) che sono
necessari per tornare a s partendo da s stesso.
E3
E1
E3
E1 …
E4
E2
E4
E2 …
E1
Period(E1) = 2
Def: uno stato è aperiodico se ha periodo uguale a 1.
Def: una catena di Markov è aperiodica se tutti i suoi stati
sono aperiodici.
Distribuzione stazionaria
Def: Data una catena di Markov del primo ordine,
finita, aperiodica e irriducibile con n stati, un
vettore φ=(φ1, φ2, …, φn) è una distribuzione
stazionaria se:
φxA=φ
• Data una catena di Markov con queste proprietà trovare
la distribuzione stazionaria è semplice (risolvendo la
precedente equazione);
• Il problema inverso è computazionalmente difficile e si
può risolvere tramite metodi di campionamento (Gibbs
sampling, Hasting-Metropolis, etc…)
Bootstrap phase – Gibbs sampling
1. Sia M una catena di Markov in cui gli stati sono
combinazioni di k protein, una per ogni rete(prese
dagli insiemi Si);
2. Scegli in maniera random una proteina da ogni rete
e sia A questo allineamento iniziale;
3. Per i=1,2,…k
• Estrai in maniera random una proteina Ai da A;
• Sostituisci Ai con una proteina x della stessa
rete, sulla base di una probabilità di transizione
(ovvero cambia stato in M);
• Aggiungi x ad A;
4. Restituisci A.
Bootstrap phase – probabilità di trans.
• Supponiamo di voler sostituire Ai con x
nell’allineamento A;
• Sia S(a,b) lo score di similarità tra le sequenze delle
proteine a e b (es. BLAST Bit score);
• Label similarity score di x:
• Probabilità di transizione:
Bootstrap phase – terminazione
• Il Gibbs sampling viene iterato per un numero fissato
di volte;
• Al termine del Gibbs sampling, l’ultimo allineamento
ottenuto viene restituito.
Iterative phase – fase di estensione
1. Sia M una catena di Markov dove gli stati sono
combinazioni di k proteine, una per ogni rete (prese
dagli insiemi dei nodi adiacenti ai nodi già allineati);
2. Scegli in maniera random un nodo adiacente da
ogni insieme e sia A questo allineamento iniziale;
3. Per i=1,2,…k
• Estrai in maniera random una proteina Ai da A;
• Sostituisci Ai con una proteina x della stessa
rete, sulla base di una probabilità di transizione
P (cambia stato in M);
• Aggiungi x ad A;
4. Estendi ciascun seed con I nodi corrispondenti in A.
5. Ripeti finché il degree ratio dei sottografi allineati
cresce.
Iterative phase – Probabilità di trans.
• Supponiamo di rimpiazzare Ai con x
nell’allineamento A;
• Label similarity score di x:
• Per la similarità topologica, sia V(n) il vettore
topologico, un array che memorizza i pesi degli
archi che collegano un nodo n ai nodi della stessa
rete già allineati.
• La posizione dei pesi nel vettore segue l’ordine di
inserimento dei nodi nell’allineamento di sottografi
parziale.
Vettore di topologia - esempio
3
0.3
n
2
0.7
1
V(n) = [0.7, 0, 0.3]
Iterative phase – Probabilità di trans.
• Similarità tra i vettori topologici di due proteine a e b:
• Topology similarity score di x:
• Score di similarità complessivo di x:
• Probabilità di transizione di x:
dove Adj(k) è l’insieme degli adiacenti al sottografo
già allineato della k-esima rete.
Iterative phase – terminazione
• Il Gibbs sampling viene iterato per un numero fisso
di volte;
• Al termine del Gibbs sampling, l’ultimo allineamento
prodotto viene restituito.
Degree ratio
• Sia S un sottografo allineato, G il grafo di cui fa
parte, degInt(x) il numero di archi che collegano un
nodo x in S con i nodi di S e deg(x) il grado di x in G;
• Degree ratio di S:
• Degree ratio dell’allineamento A:
• Il processo di estensione viene eseguito finché il
degree ratio di A cresce.
Removal step
• Elimina dall’allineamento corrente l’insieme di nodi
allineati che dà il contributo minimo alla qualità
dell’allineamento;
• Rappresentiamo A come una matrice k x w, dove
ogni colonna contiene proteine allineate nelle varie
reti;
• Eliminiamo la colonna con Goodness score minimo;
• Goodness di una proteina A[i,j]:
• Goodness di una colonna j di A:
Score dell’allineamento finale
• La qualità dell’allineamento viene valutata in
termini di conservazione strutturale;
• Numero di interazioni conservate in nodi x e y di
diversi sottografi allineati:
• Score di similarità strutturale tra due sottografi
allineati P e Q:
dove P[i] and Q[i] sono nodi allineati in P and Q.
Score dell’allineamento finale
• Score di similarità strutturale di un allineamento A:
• Index of Structural Conservation (ISC) di A:
• ISC(A)  [0,1]
Postprocessing
• Obbiettivo: filtrare complessi che hanno un elevato
grado di overlap;
• Gli allineamenti vengono ordinati per dimensione e
ISC score;
• Sia S un sottografo dell’allineamento A e Perc(S) la
percentuale di proteine in S osservate in precedenti
allineamenti;
• Perc(A) è il valore medio di Perc(S) sui vari sottografi
allineati in A;
• Se Perc(A) è al di sopra di una certa soglia
l’allineamento viene scartato.
Test – alcuni risultati
Test – alcuni risultati
Test – alcuni risultati
Riferimenti bibliografici
Una app per Cytoscape
Una app per Cytoscape
Una app per Cytoscape
Una app per Cytoscape
Una app per Cytoscape
Una app per Cytoscape
Allineamento di reti di
strutture di proteine
Perché confrontare strutture 3D
• La funzione di una proteina è principalmente
legata alla sua struttura 3D oltre che alle proteine
con cui interagisce;
• La struttura 3D di una proteina è generalmente più
conservata della sua sequenza;
• L’analisi comparativa a livello strutturale può fornire
ancora più indizi sulla funzione di una proteina
rispetto a quella fatta a livello di sequenze.
Allineamento di protein structures
• Confrontare due o più strutture 3D di proteine al
fine di individuare delle similarità (locali o globali);
• Similarità relative sia agli aminoacidi coinvolti che
alle loro distanze dagli altri residui;
• Obbiettivo: trovare una sovrapposizione ottimale
delle strutture.
Allineamento di protein structures
Allineamento locale
• Individuare potenziali siti di legame con altre
molecole (proteine, RNA, ecc.) conservati in più
proteine;
• Applicazioni:
o Predire interazioni tra proteine a livello molecolare (docking molecolare);
o Drug design.
• L’allineamento si può fare sia a livello 3D che 2D
(contact maps);
• Il mapping a 2D viene fatto per ridurre la
complessità computazionale del problema.
Funzione di similarità tra aminoacidi
• Similarità tra le label dei nodi: matrici di sostituzione
(PAM, BLOSUM);
• BLOSUM: matrice di sostituzione, con score che
indicano la frequenza di sostituzione di aminoacidi
con altri, sulla base di allineamenti locali già
computati;
• BLOSUMx: matrice costruita usando sequenze con
non più del 62% di similarità;
• Per proteine distanti conviene usare BLOSUM33, per
proteine simili si può usare anche BLOSUM80;
Valutazione della qualità dell’allineamento
• La qualità dell’allineamento è misurata sulla base della
distanza media tra gli aminoacidi allineati;
• Dati due set di k residui allineati C e D, si cerca prima la
sovrapposizione ottimale di questi residui, quella che minimizza
la loro distanza nello spazio (tramite rotazioni e traslazioni);
• Quindi si calcola l’RMSD (Root Mean Square Deviation) a
partire dalle coordinate x,y,z dei residui allineate dopo la
trasformazione:
Panoramica su algoritmi di allineamento strutturale di proteine
• 3D structure comparison:
o
o
o
o
o
o
o
o
DALI;
VAST;
SSAP;
CE;
MultiProt;
TM-Align;
MATT;
DeepAlign.
• 2D contact maps comparison:
o
o
o
o
Apurva;
(Di Lena et al.);
MSVNS;
GR-Align.
• Local aligners (pairwise):
o
o
ProBiS;
SMAP.
Un algoritmo di
allineamento locale di
strutture: PROPOSAL
PROPOSAL
PROPOSAL: PROtein comparison through
Probabilistic Optimal Structure local ALignment
• Greedy: use a seed-extend approach to look for
conserved substructures, starting from the
alignment of triplets of aminoacids;
• Stochastic: use a Gibbs sampling strategy to find an
optimal mapping between aminoacids.
Descrizione di PROPOSAL
Differenze tra GASOLINE e PROPOSAL
• Gli allineamenti hanno dimensione fissata W;
• Si parte da allineamenti di triplette di aminoacidi e non più da
singoli nodi;
• L’estensione iniziale è fatta sempre fino a W aminoacidi, poi si
procede sempre per rimozione e aggiunta di singoli
aminoacidi allineati (da W-1 a W e viceversa);
• Cambiano le funzioni di scoring per Gibbs sampling;
• Goodness sostituita con Badness score.
Allineamento iniziale
• L’allineamento iniziale avviene a partire da triplette
di aminoacidi.
• Le triplette candidate ad essere allineate sono tutte
quelle in cui gli aminoacidi sono a distanza massima
di 10 Angstrom tra loro.
• Gli aminoacidi da allineare devono corrispondersi
(ad es. C deve essere mecciato con C, D con D,
ecc.)
Probabilità di transizione nella fase iniziale
• Siano S1, S2, …, SN le triplette di aminoacidi nell’alllineamento
corrente;
• Sia X la tripletta candidata a sostituire Si ad una certa
iterazione del Gibbs sampling;
• Distance similarity:
• La probabilità di transizione è ottenuta normalizzando Sim(X)
in [0,1].
Probabilità di transizione nella fase di estensione
• Siano S1, S2, …, SN le sottostrutture già allineate;
• Vogliamo estendere ogni sottostruttura già allineata con
l’aggiunta di un nuovo aminoacido della stessa struttura
tramite Gibbs sampling;
• Gli aminoacidi candidati sono quelli che si trovano a distanza
al più 10 Angstrom da almeno un residuo nella sottostruttura
corrispondente;
• Sia A l’allineamento corrente di aminoacidi nel Gibbs
sampling e supponiamo di sostituire Ai con x;
• La probabilità di transizione è calcolata considerando la
similarità tra x e gli altri aminoacidi in A e le distanze tra x e gli
altri aminoacidi in A;
Probabilità di transizione nella fase di estensione
• Similarità tra label:
• Distance similarity:
• La probabilità di transizione è il prodotto delle due
similarità
Badness score
• Nella refinement phase si rimuove il set di
aminoacidi allineati che dà il contributo ‘peggiore’
all’allineamento finale;
• Badness score:
• Si rimuove il set di aminoacidi allineati con più alto
Badness score.
Test – alcuni risultati
Test – alcuni risultati
Test – alcuni risultati
Riferimenti bibliografici
Considerazioni finali
• Gli algoritmi descritti possono essere generalizzati
ed estesi a qualsiasi tipo di rete e contesto;
• Qualsiasi funzione di similarità tra i nodi delle reti
può essere usata;
• Possibili estensioni:
o
o
o
o
Analisi di reti sociali;
Reti dinamiche;
Reti multidimensionali;
…
Questions?