Systems Biology - unimi.ithomes.di.unimi.it/besozzi/sysbio/lezioni/LargeScaleModelingX2.pdf ·...

09/10/2014

1

Systems Biology

Metodi computazionali per l’analisi di reti biologiche

a larga scala

Daniela Besozzi - Systems Biology (AA 2014-2015) - LM BMB - Università degli Studi di Milano

BIOTECNOLOGIE MOLECOLARI E BIOINFORMATICA

Reminder: tipologie di modelli

Stelling Curr Op Microb 7, 2004

09/10/2014

2

Reminder: caratteristiche principali


Modello Variabile Tempo

Reti (teoria dei grafi)

discreta -qualitativo

statico-

Reti booleane discreta discretoqualitativo dinamico

deterministico

Modelli constraint-

basedcontinua -

quantitativo «steady state»

deterministico

Equazioni differenziali

ordinariecontinua continuo

quantitativo dinamico

deterministico

Reazioni mass-action(«Gillespie»)

discreta continuoquantitativo

dinamicostocastico

Metodi computazionali basati su reti

• Analisi topologica della struttura di una rete

– Teoria dei grafi

– Classificazione di reti sulla base della loro struttura (statica)

• Analisi dinamica di una rete

– Teoria dei grafi + funzioni logiche booleane

– Random Boolean Networks

Lezione tenuta da Chiara Damiani


09/10/2014

3

Metodi computazionali basati su reti

• Una rete è un insieme di componenti molecolari che interagiscono per compiere una specifica funzione all’interno della cellula

– reti di regolazione genica/trascrizionale

– interazioni proteina-proteina

– reti metaboliche

– (percorsi di trasduzione del segnale)


Interazioni proteina-proteina in lievito


09/10/2014

4

Non solo reti biologiche…

Six degrees ofKevin Bacon

Erdös number

Barabási et al. Scientific American, May 2003

small-world effect


Reti: rappresentazione generale

Network Science Book Project


09/10/2014

5

Reti e grafi

• Il formalismo matematico più usato per descrivere e studiare le reti è la teoria dei grafi– elementi della rete nodi

– interazioni fisiche/funzionali fra gli elementi archi

• Un modello computazionale di una rete permette di studiare:– le caratteristiche relative alla topologia della rete

(interazioni fra gli elementi e funzioni di regolazione reciproca)

– alcuni aspetti dinamici della rete (presenza di fenomeni periodici, attrattori, ecc.)


Definizione di grafo

• Un grafo G=<V, E> è definito da una coppia di insiemi:

– V è l’insieme dei nodi o vertici: V={v1, v2, …, vn}

– E VV è l’insieme degli archi: E={e1, e2, …, em} dove eh=(vi,vj) è determinato da una coppia di nodi vi, vjV, per ogni h=1, …, m

• Esempio:

– V={a, b, c, d}

– E={(a,a),(a,b),(b,c)}

a b

c d


09/10/2014

6

Grafi diretti

• Un grafo si dice diretto (o orientato) se ogni suo arco è definito da una coppia ordinata di nodi: se e=(v1,v2) ed e’=(v2,v1), allora ee’

• Notazione: v1 v2 per grafi diretti

v1 v2 per grafi non diretti

• Esempio: V={a, b, c, d}, E={(a,c),(a,b),(b,d),(c,a)}

a b

c d


Sottografi

• Un sottografo S di un grafo G=<V,E> è definito dalla coppia <V’,E’> in cui V’ V e E’ E

a b

c d

Ga b

c d

b

d

S2 a b

c d

S1

S3

NO!


09/10/2014

7

Adiacenza e grado

• In un grafo diretto o non diretto, due nodi v1 e v2 si dicono adiacenti se esiste un arco e=(v1, v2) che li collega

• Il grado di un nodo è il numero di nodi ad esso adiacenti

– Se il grafo è diretto:

• indegree di v = numero di nodi per i quali esiste un arco che termina («entra») in v

• outdegree di v = numero di nodi per i quali esiste un arco che ha origine («parte») da v


Grado in grafi diretti

• Esempio:

– indegree(a)=indegree(b)=indegree(d)=1

– outdegree(a)=2

– outdegree(d)=0

a b

c d


09/10/2014

8

Reti, nodi, archi e grado medio



Degree distribution

• La degree distribution indica la probabilità che un certo nodo abbia esattamente grado k:

P(k) = N(k)/N

– N(k) = numero di nodi che hanno grado k, con k=1,2,…

– N = numero totale di nodi della rete

a b

c d

P(1)=1/4=0.25

P(2)=2/4=0.5

P(3)=1/4=0.25

P(k)=0/4=0 per ogni k4

Nota: P(1) + P(2) + P(3) + P(4) + … =1


09/10/2014

9

Degree distribution



Degree distribution


k=0 nodi isolati k=92 nodi altamente connessi


09/10/2014

10

Clustering coefficient

• Il coefficiente di clustering indica quanto i nodi adiacenti ad un certo nodo sono a loro volta collegati fra di loro

– presenza di clique = sottografo in cui ogni nodo è collegato a tutti gli altri nodi

• Definizione: Cv = 2Nv/(kv (kv-1))

– Nv = numero di archi esistenti fra tutti i nodi adiacenti al nodo v

– kv (kv-1)/2 = numero totale di archi possibili fra tutti i nodi adiacenti a v, dove kv è il grado di v



• Esempio 1:

Cv = 2Nv/(kv (kv-1))

a b

c d

nodo d:

• nodi adiacenti = b

• Nd=0

• kd=1

Cb=2/6=0.33Ca=2/2=1

nodo a:

• nodi adiacenti = b,c

• Na=1 (arco (b,c))

• ka=2

Cd=0

nodo b:

• nodi adiacenti = a,c,d

• Nb=1 (arco (a,c))

• kb=3

Cc=2/2=1

nodo c:

• nodi adiacenti = a,b

• Nc=1 (arco (a,b))

• kc=2


09/10/2014

11


nodo e:

nodi adiacenti = a,b,c,d ke=4

Ne=6Ce=12/12=1

a b

e

c d

a b

e

c d

a b

e

c d

Ne=3Ce=6/12=0.5

Ne=0Ce=0

• Esempio 2:


Average clustering coefficient

• Il coefficiente di clustering medio <C> caratterizza la tendenza dei nodi di un grafo a formare gruppi

– alti valori di <C> indicano un alto livello di coesione e ridondanza

• Una misura importante della rete è definita dalla funzione C(k) = coefficiente di clustering medio di tutti i nodi che hanno grado k

– indica la presenza di modularità nella rete = sottoreti funzionalmente separabili con alta connessione interna e bassa connessione con altre parti della rete (topologia gerarchica)


09/10/2014

12

Altre misure di rete: centralità

• Degree centrality

– Misura il numero delle connessioni di un nodo

• Betweenness centrality

– Misura il numero di shortest path che passano attraverso un nodo (o la probabilità di un nodo di fare da «ponte» tra altri due nodi)

• Closeness centrality

– Misura quanto un nodo è «vicino» agli altri nodi

• Fornisce un’indicazione sulla «velocità» di trasmissione dell’informazione nella rete


Cammini e cicli

• Un cammino in un grafo è definito da una sequenza (v1, v2,…, vn) di nodi tali che (vi, vi+1) è un arco, per ogni i=1, …, n-1

• Un ciclo è un cammino in cui l’ultimo nodo coincide con il primo, cioè v1= vn

a b

c d

Esempio:

(a,b,d,c), (b,c) sono esempi di cammini

(a,b,c,a), (a,c,a) sono esempi di cicli


09/10/2014

13

Lunghezza dei cammini

• La lunghezza di un cammino fra due nodi vi e vj è definita dal numero di archi del cammino

– possono esistere diversi cammini fra vi e vj shortestpath = cammino fra vi e vj che ha lunghezza minima

– N.B. lo shortest path non è necessariamente unico

Esistono due shortest path fra i nodi 1 e 7


Lunghezza dei cammini

– lunghezza media dei cammini = media della lunghezza degli shortest path fra tutte le coppie di nodi del grafo

– diametro del grafo = la distanza maggiore calcolata fra ogni coppia di nodi (o la distanza fra i nodi più lontani)

a b

c d

Cammini fra a e c:

(a,c), (a,b,c), (a,b,d,c), (a,b,d,b,c), …

(a,c) shortest path fra a e c

Diametro del grafo: 3


09/10/2014

14

Grafi pesati

• Un grafo pesato è definito dalla coppia <V, E> più una funzione w:E R che associa ad ogni arco un numero reale:

– il valore w(e) è detto peso/costo/distanza

– il peso di un cammino è la somma dei pesi degli archi che costituiscono il cammino

a b

c d1

51215

3,1

Esempio:

peso del cammino (a,b,d,c)=3,1+15+1=19,1


Grafi connessi

• Un grafo (non diretto) è connesso se ogni suo nodo è raggiungibile da ogni altro nodo

a b

c d

a b

c d

grafo connesso

grafo non connesso costituito da 2 componenti connesse


09/10/2014

15

Grafi bipartiti

• Un grafo è bipartito se:

– l’insieme dei nodi è unione di due insiemi disgiunti, cioè V=V1V2 con V1V2=

– ogni arco ha un nodo in V1 e un nodo in V2

a b

e

c d

grafo bipartito

V1={a,c,e}

V2={b,d}

grafo non bipartito

V1={a,c,e}

V2={b,d}

a b

e

c dDaniela Besozzi - Systems Biology (AA 2014-2015) - LM BMB - Università degli Studi di Milano

Grafi bipartiti in Biologia

• Esempio: human diseaseome

– 2 tipi di nodi: geni (cerchio), malattie (rettangolo)

– arco = una malattia è connessa ad un gene se una mutazione di quel gene è nota causare quella malattia

09/10/2014

16


Nacher et al. Nature Sci Rep 3, 2013


• Esempio: rete metabolica

– 3 tipi di nodi

• reagenti (cerchio), reazioni (ovale), enzimi (quadrato)

– 2 tipi di archi

• catalisi (linea tratteggiata), mass flow (linea piena)

– archi pesati

• stechiometria

Albert J Cell Science 118, 2005


09/10/2014

17

I diversi tipi di rete

• Le strutture di rete si possono distinguere e classificare sulla base di misure globali del grafo (ad es. degree distribution P(k), averageclustering coefficient C(k), ecc.)

– Random network

– Scale-free network

– Hierarchical network


Bar

abás

iet

al. N

at

Rev

Gen

5, 2

00

4

09/10/2014

18

Diverse reti, diversi valori delle misure

Mitchell, Artificial Intelligence 170, 2006


Random networks

• Modello di Erdös-Rényi (1960)– rete costruita collegando in modo casuale

un numero N di nodi

– rete “statisticamente omogenea”: la maggioranza dei nodi ha grado vicino al grado medio della rete <k>

– <C>=<k>/N (piccolo per reti grandi)

– distribuzione poissoniana dei gradi P(k): nodi con grado molto alto o molto basso sono rari

– rete non caratterizzata da modularità (C(k) costante)

– rete caratterizzata dalla proprietà “small-world”


09/10/2014

19

Small-world

• Proprietà condivisa da molte reti complesse: nonostante la dimensione della rete, ogni coppia di nodi è collegata da un numero ridotto di archi (“six degrees of separation”, S. Milgram, 1967)

– lunghezza media dei cammini log(N)

• Assicura una trasmissione veloce delle informazioni attraverso la rete

• Ultra small-world:

– lunghezza media dei cammini loglog(N)

– proprietà di reti scale-free


Scale-free networks

• Modello di Barabási-Albert (1999)

– rete non omogenea (a “invarianza di scala”)

• pochissimi nodi con moltissime connessioni (hub = nodo con grado molto più grande di <k>)

• moltissimi nodi con poche connessioni

– power-law degree distribution P(k)=k-

• se 2<<3 ultra small-world

– rete non caratterizzata da modularità (C(k) costante)


09/10/2014

20

Random vs. scale-free network

• Poissonian vs. power-law degree distribution





09/10/2014

21

Scale-free networks: esempio 1

• Yeast protein network:

Barabási et al. Nat Rev Gen 5, 2004

Presenza di hub

Colore del nodo corrisponde a effetto fenotipico dopo la rimozione della proteina:rosso=letaleverde=non letalearancione=crescita lentagiallo=sconosciuto



• C. elegans protein network:

Colore del nodo corrisponde a classe filogenetica:rosso=ancientblu=wormgiallo=multicellular



09/10/2014

22


• Reti metaboliche:

– a) A. fulgidus (archea)

– b) E. coli (batteri)

– c) C. elegans (eucarioti)

Jeong et al. Nature 407, 2000


Esempi non biologici di reti scale-free

© Mario Freese© The Opte Project

World Wide Web Connessioni tra aeroporti


09/10/2014

23

Preferential attachment (rich-gets-reacher)

• La crescita della rete è guidata dall’attacco di nuovi nodi

– topologia forgiata da processi (evolutivi) dinamici

• I nuovi nodi tendono a collegarsi ai nodi della rete che hanno grado più alto (es. World Wide Web)


Preferential attachment (rich-gets-reacher)

• Nelle reti di interazione proteina-proteina, questo fenomeno è probabilmente dovuto alla duplicazione dei geni

Barabási et al. Nat Rev Gen 5, 2004


09/10/2014

24

La robustezza (strutturale) delle reti

• Definiamo errore la rimozione casuale di uno o più nodi:

– avviene stocasticamente

– stessa probabilità d’errore per tutti i nodi

• Definiamo attacco la rimozione specifica di uno (o più) tra i nodi maggiormente connessi (hub)

– avviene in maniera deterministica

– esiste una conoscenza preventiva della topologia della rete



• Robustezza (topologica) della rete

Bar

abás

iet

al. S

cien

tifi

cA

mer

ica

n, M

ay 2

00

3

09/10/2014

25


• Fragilità degli hub



09/10/2014

26

Hierarchical networks

• Topologia che integra invarianza di scala, modularità e presenza di cluster locali

– esempio: cluster centrale (azzurro) altamente connesso, replicato 3 volte (verde), il tutto replicato 3 volte (rosso)

– power-law degree distribution P(k)=k-

con =2.26

– <C> 0.6

– rete caratterizzata da modularità: C(k) 1/k


Hierarchical networks


09/10/2014

27

Modularità

• Modulo = sottografo funzionalmente separabile che corrisponde ad una specifica funzione biologica

– alta intra-connessione di nodi, bassa inter-connessione con il resto della rete

• Motif = piccolo sottografo con struttura ben definita che ricorre con frequenza significativa nella struttura globale della rete (rispetto ad una rete casuale con stessa dimensione)

L’identificazione di moduli/motif è un problema computazionalmente costoso (e spesso non ben definito)


Network motifs

Transcriptional feed-forward loop(R=transcriptional regulation, X=correlated expression)

Co-regolazione trascrizionale(R=transcriptional regulation, P= protein interaction, H= sequence homology)

Alb

ert

J C

ellS

cien

ce 1

18

, 20

05


09/10/2014

28

Network motifs

Co-regolazione di complesso proteico(R=transcriptional regulation, P=protein interaction, X=correlated expression, H=

sequence homology)

Clique di interazione/coespressione proteica(P= protein interaction, X=correlated expression)

Alb

ert

J C

ellS

cien

ce 1

18

, 20

05


Aspetti critici delle reti a larga scala

• Bias:– geni o proteine coinvolti in patologie sono più studiati di

altri

• Incompletezza (di nodi e archi):– falsi positivi/negativi

• Assenza di informazioni quantitative relative allo stato della cellula o ad aspetti temporali:– non tutti gli archi sono presenti o attivi nello stesso

istante o nello stesso sito (in vivo)• “party hubs” = interagiscono simultaneamente con la

maggioranza dei vicini

• “date hubs”= interagiscono con i vicini in tempi e luoghi differenti


09/10/2014

29

Aspetti critici delle reti a larga scala

• Le reti biologiche a larga scala rappresentano una struttura «potenziale» della realtà cellulare

• La «dinamica» della rete (per reti di geni, descritte con Random Boolean Network) non implica:

– la descrizione della variazione delle quantità molecolari nel tempo

– considerazioni sulle cinetiche delle «interazioni»


Software per analisi di reti

• Cytoscape: http://www.cytoscape.org/

Saito et al. Nature Methods 9, 2012

http://www.cytoscape.org/

09/10/2014

30

Qualche esempio


Più informazioni in una rete statica!

09/10/2014

31

Ideker et al. Molecular Systems Biology 8, 2012

Reti e livelli in ambito medico

Barabasi Molecular Systems Biology 8, 2012

09/10/2014

32

Una rete a larga scala in ambito ecologico

09/10/2014

33

Riferimenti bibliografici• Network Science Book Project:

http://barabasilab.neu.edu/networksciencebook/• A.L. Barabási, Z.N. Oltvai, Network biology: understanding the cell’s

functional organization, Nature Reviews Genetics 5:101-113, 2004• T. Aittokallio, B. Schwikowski, Graph-based methods for analysing networks

in cell biology, Briefings in Bioinformatics 7(3):243-255, 2006• A.L. Barabási, E. Bonabeau, Scale-free networks, Scientific American

288(5):50-59, 2003• R. Albert, Scale-free networks in cell biology, Journal of Cell Science

118:4947-4956, 2005• T. Ideker, R. Sharan, Protein networks in disease, Genome Research 18:644-

652, 2008• A.-L. Barabási, Link. La nuova scienza delle reti, Einaudi, 2004• S. Kauffman, The origins of order, Oxford University Press, 1993• C. Gershenson, Introduction to Random Boolean Networks, 2004

(arXiv:nlin/0408006v3)• S. Bornholdt, Boolean network models of cellular regulation: prospects and

limitations, J. R. Soc. Interface 5, Suppl. 1, S85-S94, 2008


http://barabasilab.neu.edu/networksciencebook/

http://arxiv.org/abs/nlin/0408006v3

Systems Biology - unimi.ithomes.di.unimi.it/besozzi/sysbio/lezioni/LargeScaleModelingX2.pdf ·...

Documents

Transcript of Systems Biology - unimi.ithomes.di.unimi.it/besozzi/sysbio/lezioni/LargeScaleModelingX2.pdf ·...