Pavia, 15 Aprile 2014
Almo Collegio Borromeo
Caratterizzazione assiomatica di un
indice di rilevanza
Giulia Cesari
Politecnico di Milano
Université Paris Dauphine
[email protected]
…
Array1
Array2
Array3
rapporto di espressione del
gene 5 nell’array 4
Scendono in campo i geni …
• I giocatori sono proprio i geni
• Ma chi fornisce la regola decisionale nel contesto
dei geni?
• Possibile risposta: costruiamo una regola decisionale
sulla base dei dati di espressione genica
• Definiamo un criterio per stabilire quali geni si
comportano in maniera “anormale” su ciascun array.
array1
array1
gene1
1.121
gene1
0
gene2
2.453
gene2
1
gene3
3.586
gene3
1
Regola decisionale
Un gruppo di geni è “vincente” in un singolo
esperimento se tutti i geni che si comportano
in maniera anormale nell’ esperimento sono
contenuti in quel gruppo.
array1
gene1
0
gene2
1
gene3
1
Esempio:
Il gruppo {gene2, gene3} e il gruppo
{gene1, gene2, gene3} sono entrambi
vincenti.
…
Array1
Array2
Array3
array1
array2
array3
gene1
0
1
0
gene2
1
1
0
gene3
1
0
1
•Il gruppo {gene2, gene3} è vincente due volte su tre;
•Il gruppo {gene1, gene2} è vincente una volta su tre
•Così via per tutti i possibili gruppi…
Esempio:
A questa matrice corrisponde il
g1
Array1
Array2
Array3
0
1
0
g2
1
g3
1
1
0
microarray game <{g1,g2,g3},v> tale
che
0
v()=v({g1})=v({g2})=0
1
v({g1,g3})=v({g1,g2})=v({g3})=1/3
v({g2,g3})=2/3
v({g1,g2,g3})=1.
Il valore Shapley è:
Shg1=1/6
Shg2=1/3
Shg3=1/2
Il valore Shapley come indice di rilevanza di geni
• Perché possiamo usare il valore Shapley In questo
contesto?
• Approccio assiomatico: giustifichiamo l’uso del
valore Shapley attraverso alcune proprietà che esso
soddisfa
• Proprietà con interpretazione biologica
Gene regulatory pathway (GRP)
Un insieme di geni in una cellula che interagiscono tra loro,
regolando il livello di espressione dei geni all’interno
dell’insieme stesso.
Il meccanismo di regolazione dell’espressione genica in molti
pathway è tutt’ora lungi dall’essere compreso a pieno.
Una delle maggiori difficoltà nella comprensione dei
meccanismi che governano tali pathway è l’alto numero di
geni coinvolti in un’analisi con i microarray.
Ricostruire pathway da dati di espressione genica è un passo
cruciale nella comprensione della funzione di geni
nell’insorgere di una malattia genetica.
Partnership di geni
Un gruppo di geni S tale che non esiste un sottoinsieme proprio ()
di S in grado di contribuire al cambiamento del valore del gruppo
esterno ad S.
Esempio
a1 a2 a3
Questi due
insieme sono
partnership di geni
nel gioco di
microarray
corrispondente
g1
0
1
1
g2
0
1
1
g3
1
0
1
Partnership di geni
Il concetto di partnership in TU-games è stato introdotto in
Kalai e Samet (1988) in un contesto che non coinvolge geni
per caratterizzare quelle coalizioni che si comportano come
un individuo (tutte le sottocoalizioni non hanno alcun potere).
Motivazioni nell’adottare la definizione di partnership di geni
come una buona rappresentazione di un GRP:
 Non richiede informazioni a priori sui meccanismi di
regolazione tra geni
 Richiede che non esista un sottogruppo proprio di geni he
interagisca con un gene o con un gruppo di geni esterni per
provocare l’insorgenza della malattia.
Assiomi per il valore Shapley sui microarray games
Proprietà 1: Gene Nullo (NG)
un indice di rilevanza deve attribuire rilevanza nulla ai geni che
non sono mai anormalmente espressi nelle cellule malate.
Proprietà 2: Equal Splitting (ES)
tutti gli esperimenti devono essere considerati ugualmente affidabili e
quindi avere lo stesso peso nel calcolo del potere dei geni.
g1
g2
g3
a1
0 1
0 2
1 3
+
a2
1 ’1
1 ’2
0 ’3
=
a1
g1 0
g2 0
g3 1
a2
1
1
0
(1+’1)/2
(2+ ’2)/2
(3+ ’3)/2
Proprietà 3: Monotonia delle Partnership (PM)
Se si hanno due partnerships di geni S e T, con |T||S| e che siano
 disgiunte (ST=),
equivalenti v(S)=v(T) ed
esaustive (v(ST)=v(N))
i geni nella partnership meno numerosa S devono ricevere più
rilevanza di quelli in T.
Esempio
1
2
3
4
5
g
1
g
2
g
3
g
4
g
s1
0
0
1
1
1
s2
1
1
0
0
0
i ≥ k
For each
i1,2
k3,4,5
Proprietà 4: Razionalità di partnership (PR)
Il valore totale di rilevanza ricevuta da una partnership S dovrebbe
essere non inferiore a v(S)
Proprietà 5: Fattibilità di partnership (PF)
Il valore totale di rilevanza ricevuta da una partnership S dovrebbe
essere non superiore a v(N)
Teorema (Moretti, Patrone, Bonassi (2007)):
Il valore Shapley è l’unico indice che
soddisfa le proprietà NP, ES, PM, PR, PF
sulla classe dei giochi di microarray.
Esercizio:
gene1
gene2
gene3
gene4
gene5
gene6
gene7
gene8
gene9
gene10
sample1
sample2
sample3
sample4
0
1
0
1
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
1
0
0
0
0
0
1
0
1
•Calcolare il valore Shapley del
gioco di microarray associato a
questa tabella.
•La coalizione {gene2, gene3,
gene 4} è una partnership?
•La coalizione {gene2, gene 8} è
una partnership?
Identification of low intratumoral gene expression heterogeneity in neuroblastic tumors
by genome‐wide expression analysis and game theory
Cancer
Volume 113, Issue 6, pages 1412-1422, 31 JUL 2008 DOI: 10.1002/cncr.23720
http://onlinelibrary.wiley.com/doi/10.1002/cncr.23720/full#fig1
Teoria dei giochi
&
network
Network di comunicazione
• Un gioco cooperativo descrive una situazione in cui
tutti i giocatori possono liberamente interagire tra
loro
 tutte le coalizioni sono ammissibili
• Facciamo cadere questa ipotesi:
 introduciamo una restrizione sulle possibilità di
interazione tra i giocatori
• Come possiamo rappresentare questa restrizione
delle coalizioni di giocatori?
 attraverso un network
Situazione di comunicazione
( communication situation )
• E’ una terna (N,v,Γ):
 (N,v) è un gioco di coalizione: rappresenta le
possibilità “economiche” delle coalizioni
 Γ=(N,E) è un network di comunicazione:
rappresenta le restrizioni di comunicazione tra i
giocatori
Gioco a priori
Dato il gioco a priori v:
come incorporare l’informazione
sulla restrizione di comunicazione
tra i giocatori?
Situazione di comunicazione (Myerson 1977)

Il gioco ristretto al grafo (N,vΓ) è definito da
per ogni S2N\{}.
Ricordiamo che:
connesse in
è l’insieme delle componenti
Gioco a priori
Gioco ristretto al grafo
Esempio
Consideriamo un gioco di maggioranza pesata ({1,2,3},v)
con quota q=2/3. I voti dei giocatori 1, 2, e 3 sono,
rispettivamente, 40%, 20%, e 40%.Allora, v(1,3)=v(1,2,3)=1
e v(S)=0 per tutte le restanti coalizioni.
Il network di comunicazione è:
1
2
3
Allora, vΓ(1,2,3)=1, e vΓ (S)=0 per tutte le rimanenti
coalizioni.
Soluzioni per le situazioni di comunicazione


Myerson (1977) è stato il primo a studiare soluzioni per le
situazioni di comunicazione.
Una soluzione Ψ è una mappa definita per ogni situazione di
comunicazione (N,v,Γ) a valori in ℝN.
Proprietà 1 Component Efficiency (CE)
Per ogni situazione di comunicazione (N,v,Γ) e C  CΓs vale che:
iC Ψi(N,v,L) = v(C).

La proprietà 1 è una condizione di “efficienza” che si suppone
valida solo per le coalizioni I cui giocatori sono in grado di
comunicare tra loro e non sono connessi ad altri giocatori.
(componenti connesse massimali)
Soluzioni per le situazioni di comunicazione (2)
Proprietà 2 Fairness (F) Per ogni situazione di comunicazione
(N,v,Γ) e per ogni {i,j}  E vale che
Ψi(N,v,Γ) −Ψi(N,v,Γ\{{i, j}}) = Ψj(N,v,Γ)− Ψj(N,v,Γ\{{i, j }}).

La proprietà 2 dice che due giocatori dovrebbero ottenere lo
stesso guadagno (o perdita), quando si aggiunge (o si
elimina) un link diretto tra di loro.
Il valore Myerson
Teorema (Myerson (1977))
Esiste un’unica soluzione (N,v,Γ) che soddisfi CE e
F sulla classe delle situazioni di comunicazione.
Inoltre,
(N,v,Γ)= (vΓ)
dove (vΓ) è il valore Shapley del gioco ristretto al
grafo vΓ.
Esempio
Consideriamo un gioco di maggioranza pesata ({1,2,3},v)
con quota q=2/3. I voti dei giocatori 1, 2, e 3 sono,
rispettivamente, 40%, 20%, e 40%.Allora, v(1,3)=v(1,2,3)=1
e v(S)=0 per tutte le restanti coalizioni.
Il network di comunicazione è:
1
2
3
Allora, vΓ(1,2,3)=1, e vΓ (S)=0 per tutte le rimanenti
coalizioni.
(v)=(1/2,0,1/2) e (N,v,Γ)= (vL)=(1/3,1/3,1/3).
Tornando ai geni…
• Un gioco cooperativo descrive una situazione in cui tutti i
giocatori possono liberamente interagire tra loro
 tutte le coalizioni sono ammissibili
• Facciamo cadere questa ipotesi:
 introduciamo una restrizione sulle possibilità di
interazione tra i giocatori
 Qual è il significato di imporre una restrizione sulle
possibilità di interazione tra geni?
 Quali informazioni ci fornisce un network di geni al fine di
individuare geni rilevanti all’interno di un contesto
biologico?
… network biologici
• I meccanismi di interazione tra geni, RNA e proteine sono
molto complessi e oggetto di grande interesse nel campo
della ricerca biomedica e epidemiologica.
• Tali meccanismi sono descritti da reti di regolazione genica:
gene regulatory network o gene regulatory pathway.
• La ricostruzione dei meccanismi di regolazione a livello
cellulare sulla base dei dati di espressione genica è
fondamentale per la comprensione delle funzioni di geni nella
determinazione di una certa condizione biologica di interesse,
come l’insorgere di una malattia genetica.
• L’interpretazione dell’interazione tra geni all’interno di network
biologici rende dunque necessaria l’individuazione di misure
dell’importanza di geni all’interno di tali network.
Rilevanza di geni in un network biolgico
Centralità in un network
• Cosa si intende con centralità in un network?
• Quali sono possibili misure di centralità di geni in un network
biologico?

Non solo Myerson…
• Esistono in letteratura altre soluzioni per le situazioni di
comunicazione (vedi [1],[2],[3])
• Tra queste citiamo il position value (Meesen, 1988 ; Borm et
al. 1992)
Non solo Myerson…
Esempio
Consideriamo un gioco di maggioranza pesata ({1,2,3},v)
con quota q=2/3. I voti dei giocatori 1, 2, e 3 sono,
rispettivamente, 40%, 20%, e 40%.Allora, v(1,3)=v(1,2,3)=1
e v(S)=0 per tutte le restanti coalizioni.
Il network di comunicazione è:
1
2
3
Allora, vL(1,2,3)=1, e vL (S)=0 per tutte le rimanenti
coalizioni. (v)=(1/2,0,1/2), (N,v,Γ)= (vL)=(1/3,1/3,1/3) e
il position value è
π(v)=(1/4,1/2,1/4)
Buona Pasqua!