Caratterizzazione assiomatica di un indice di rilevanza

Giulia Cesari

Politecnico di Milano Université Paris Dauphine

giulia.cesari@polimi.it

Pavia, 15 Aprile 2014 Almo Collegio Borromeo

rapporto di espressione del gene 5 nell’array 4

Array1 Array2 Array3

…

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.

3.586gene3

2.453gene2

1.121gene1

array1

1gene3

1gene2

0gene1

array1

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.

1gene3

1gene2

0gene1

array1Esempio:

Il gruppo {gene2, gene3} e il gruppo {gene1, gene2, gene3} sono entrambi vincenti.

•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…

Array1 Array2 Array3

gene3

gene2

gene1

1

1

0

array1

0

1

1

array2

1

0

0

array3

…

Esempio:

101g3

011g2

010g1

Array3Array2Array1A questa matrice corrisponde il

microarray game <{g1,g2,g3},v> tale

che

v()=v({g1})=v({g2})=0

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

Un insieme di geni in una cellula che interagiscono tra loro, regolando il livello di espressione dei geni all’interno dell’insieme stesso.

Gene regulatory pathway (GRP)

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.

101g3

110g2

110g1

a3a2a1

Esempio

Questi due insieme sono partnership di geni nel gioco di microarray corrispondente

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).

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.

Motivazioni nell’adottare la definizione di partnership di geni come una buona rappresentazione di un GRP:

Assiomi per il valore Shapley sui microarray games

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.

1

0

0

a1

0

1

1

a2

g3

g2

g1

01g3

10g2

10g1

a2a11

2

3

’1

’2

’3

+ =(1+’1)/2

(2+ ’2)/2

(3+ ’3)/2

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à 3: Monotonia delle Partnership (PM)

Se si hanno due partnerships di geni S e T, con |T||S| e che siano disgiunte (ST=), equivalenti v(S)=v(T) ed esaustive (v(ST)=v(N))

i geni nella partnership meno numerosa S devono ricevere più rilevanza di quelli in T.

i ≥ k

For eachi1,2

k3,4,5

01g3

10g2

10g1

s2s1

01g5

01g4

1

2

3

4

5

Esempio

Proprietà 5: Fattibilità di partnership (PF)Il valore totale di rilevanza ricevuta da una partnership S dovrebbe essere non superiore a v(N)

Proprietà 4: Razionalità di partnership (PR)Il valore totale di rilevanza ricevuta da una partnership S dovrebbe essere non inferiore a v(S)

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.

Rilevanza

Esercizio:sample1 sample2 sample3 sample4

gene1 0 0 1 0gene2 1 0 0 1gene3 0 1 0 0gene4 1 0 0 0gene5 1 0 0 0gene6 0 1 1 0gene7 0 0 1 0gene8 1 0 0 1gene9 0 0 0 0gene10 1 0 1 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

CancerVolume 113, Issue 6, pages 1412-1422, 31 JUL 2008 DOI: 10.1002/cncr.23720http://onlinelibrary.wiley.com/doi/10.1002/cncr.23720/full#fig1

Teoria dei giochi &

network

• 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

Network di comunicazione

• Come possiamo rappresentare questa restrizione delle coalizioni di giocatori? attraverso un network

• 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

Situazione di comunicazione( communication situation )

Dato il gioco a priori v:come incorporare l’informazione sulla restrizione di comunicazione tra i giocatori?

Gioco a priori

Situazione di comunicazione (Myerson 1977)

Il gioco ristretto al grafo (N,vΓ) è definito da

per ogni S2N\{}.

Ricordiamo che: è l’insieme delle componenti connesse in

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.

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 CCΓs vale che:

iC Ψ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

Proprietà 2 Fairness (F) Per ogni situazione di comunicazione

(N,v,Γ) e per ogni {i,j}Evale 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.

Soluzioni per le situazioni di comunicazione (2)

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Γ.

Il valore 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, 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).

• 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?

Tornando ai geni…

• 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.

… network biologici

Rilevanza di geni in un network biolgico

• Cosa si intende con centralità in un network?

• Quali sono possibili misure di centralità di geni in un network biologico?

Centralità in un network

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!