Biologia computazionale

(1)

Biologia

computaziona le

A.A. 2010-2011 semestre II

UNIVERSITÀ

DEGLI STUDI DI MILANO

Docente: Giorgio Valentini Istruttore: Matteo Re

5 Evoluzione e filogenesi - 2

C.d.l. Biotecnologie Industriali e Ambientali

(2)

Metodi basati su:

• Distanza

• Massima parsimonia (minima evoluzione)

• Massima verosimiglianza

Abbiamo già discusso un medoto basato su distanze:

UPGMA

(3)

Abbiamo già discusso un medoto basato su distanze:

UPGMA

Classi di metodi disponibili

Bio CS

Abbiamo

bisogno di

altri metodi?

(4)

Cosa non va in UPGMA?

(rivediamo l’esempio…)

A B C D

A 0 6 6 7

B 0 4 5

C 0 3

D 0 A B C D

Quest’albero … implica che la distanza tra B e C ha lo stesso valore della distanza tra B e D?

Ma la matrice delle distanze non conteneva valori diversi?

?

(5)

problemi con UPGMA…

Bio CS

• UPGMA calcola la media delle due distanze e pone sia C che D alla medesima distanza (1.5) da B …

• Cosa succede se le velocità evolutive dopo la divergenza sono diverse?

A B C D

A B C D

A 0 7 6 7

B 0 4 5

C 0 3

D 0

4

.5

1 2

2.5

NB: è un effetto dell’ipotesi dell’orologio molecolare!

(6)

TAXA MOLTO SIMILI

• Velocità evolutive differenti (non contemplate dall’ipotesi dell’orologio molecolare) possono causare problemi a UPGMA

• Specialmente nel caso di taxa molto simili (distanze molto piccole)!

A B C

A 0 4 3

B 0 3

C 0

A B C

1

2 1

1

Questo albero

Produce questa matrice

..che produce quest’albero

B C

A

… e i due alberi sono DIVERSI !

(7)

Cronogrammi

Bio CS

Alberi ultrametrici ( cronogrammi)

Le distanze (nei cronogrammi) devono obbedire a 4 regole:

Non-negatività: d(a,b) ≥ 0

Distinguibilità: d(a,b) = 0 if and only if a = b Simmetria: d(a,b) = d(b,a)

Disug. triangolare: d(a,c) ≤ d(a,b) + d(b,c) Inoltre devono anche soddisfare la:

Condizione dei tre punti: d(a,b) ≤ max( d(a,c), d(b,c) )

1 1 1 1 1 2 3

1

1 3

a b c

1 0.4 2

1

a c b

(8)

Alberi ultrametrici ( cronogrammi)

Le distanze (nei cronogrammi) devono obbedire a 4 regole:

Non-negatività: d(a,b) ≥ 0

Distinguibilità: d(a,b) = 0 if and only if a = b Simmetria: d(a,b) = d(b,a)

Disug. triangolare: d(a,c) ≤ d(a,b) + d(b,c) Inoltre devono anche soddisfare la:

Condizione dei tre punti: d(a,b) ≤ max( d(a,c), d(b,c) )

1 1 1 1 1 2 3

1

1 3

a b c

1 0.4 2

1

a c b

(9)

Motivi dei problemi di UPGMA

Bio CS

• UPGMA è molto sensibile alla presenza di velocità evolutive differenti (assume che esse siano uguali su tutti i rami).

• Il clustering funziona SOLO SE i dati sono ultrametrici

• Le distanze sono ultrametriche SE soddisfano la ‘condizione dei tre punti'.

A B C

Per ogni combinazione di tre taxa, le due distanze maggiori devono essere uguali.

Condizione dei tre punti:

A B C

(10)

A B C D E B 5

C 4 7

D 7 10 7

E 6 9 6 5

F 8 11 8 9 8

Velocità evolutive non costanti

TOPOLOGIA ERRATA

(11)

Esempio di errore di UPGMA

Bio CS

A B C D E B 5

C 4 7

D 7 10 7

E 6 9 6 5

F 8 11 8 9 8

Velocità evolutive non costanti

TOPOLOGIA ERRATA

Esiste un metodo chiamato Neighbor Joining che avrebbe ricostruito la topologia dell’albero in modo

corretto.

(12)

A B

C D a

b

x c

d

A e B sono neighbors (“vicini”) poichè sono connessi da un singolo nodo interno.

Anche C e D sono vicini, ma A e D non lo sono.

Neighbor Joining e costruzione di alberi additivi

(filogrammi, lunghezza rami proporzionale a distanze

genetiche

)

(13)

Alberi additivi

Bio CS

Condizione dei 4 punti A

B

C D

d

_AC

+ d

_BD

= d

_AD

+ d

_BC

= a + b + c + d + 2x = d

_AB

+ d

_CD

+ 2x a

b

x c

d

_AB

+ d

_CD

< d

_AC

+ d

_BD

d

_AB

+ d

_CD

< d

_AD

+ d

_BC

Se l’albero è additivo, allora deve essere rispettata la:

vicini non-vicini

Fondamentalmente dice che la distanza tra i vicini è minore di quella tra i non-vicini.

Condizione dei 4 punti

(14)

A

B

C

D

Partiamo da una struttura a stella (nessuna struttura gerarchica)

Lunghezza dell’albero Distanze pair-wise

Numero di taxa

NJ: costruzione dell’albero più corto

(15)

Neighbor Joining (NJ)

Bio CS

(Saitou and Nei, 1987)







  

 





N i

N j i

ij N

i iY

X X

N D D

D L

L

3 3

12 2

1

1 )

3 (

1

Possiamo utilizzare queste formule per calcolare la lunghezza del nuovo albero:

 

 



     

   



N i

iY X

X N

k

k k

XY

D D N L L L

L N

3 2

1 3

2

1

) ( 2 )( ) 2

) ( 2 (

2

1

(16)

Ad ogni passo tutte le coppie di vicini vengono esaminate e viene scelta quella che produce l’albero più corto (criterio di minima evoluzione).

(17)

Neighbor Joining (NJ)

Bio CS

Come nel caso di UPGMA ad ogni ciclo viene aggiunto un ramo interno … ma adesso è sempre il ramo più corto possibile !

(18)

Come nel caso di UPGMA ad ogni ciclo viene aggiunto un ramo interno … ma adesso è sempre il ramo più corto possibile !

Albero non radicato

(19)

Massima parsimonia

Bio CS

Massima parsimonia

• Definizione:

parsimònia s. f. [dal lat. parsimonia, der. di parcĕre «risparmiare» (supino parsum)]. – La qualità di chi è parco; moderazione, giusta misura nell’uso del denaro o di altri beni, per un senso di doverosa economia o per abituale frugalità di vita: avere, usare p.; …

Principio, o legge, della p.: uno dei modi con cui viene denominato il principio (altrimenti detto legge di economia, o principio del minimo sforzo, o del minimo mezzo, o del minimo lavoro) così enunciato da G. Galilei nel «Dialogo sopra i due massimi sistemi» (Giornata seconda): la natura ... non opera con l’intervento di molte cose quel che si può fare col mez(z)o di poche, volendo significare che ogni fenomeno naturale si realizza sempre con il minimo dispendio sia di materia sia di energia.

http://www.treccani.it/vocabolario/parsimonia/

(20)

E’ possibile applicare il concetto di parsimonia alla costruzione di alberi filogenetici?

In fondo gli alberi filogenetici sono IPOTESI evolutive (come gli allineamenti utilizzati per definire le distanze tra i membri di un set di sequenze…). Quindi tra tutte le possibili ipotesi (alberi) vorremmo scegliere quella che spiega le sequenze con il minor numero di eventi evolutivi (da qui il termine parsimonia).

Tra tutte le possibili ipotesi in grado di spiegare i dati

(sequenze) vogliamo scegliere la più SEMPLICE

RASOIO DI

OCCAM

(21)

Bio CS

Massima parsimonia:

• Osserviamo ogni colonna di un allineamento multiplo e costruiamo un albero che la “descriva”

• Costruiamo un albero consenso

atgccgca-actgccgcaggagatcaggactttcatgaatatcatcatgcgtggga-ttcag acctccatacgtgccccaggagatctggactttcacc---tggatcatgcgaccgtacctac t-atgg-t-cgtgccgcaggagatcaggactttca-gt--g-aatcatctgg-cgc--c-aa t--tcgt-ac-tgccccaggagatctggactttcaaa---ca-atcatgcgcc-g-tc-tat aattccgtacgtgccgcaggagatcaggactttcag-t--a-tatcatctgtc-ggc--tag

(22)

Massima parsimonia:

• Cosa intendiamo quando ci riferiamo ad un albero in grado di “descrivere” (spiegare) una colonna del multiallineamento?

Ipotesi di lavoro: Costruiamo tutti i possibili alberi per una colonna del multiallineamento e poi scegliamo il migliore PROBLEMI:

• Come costruiamo tutti i possibili alberi per una data colonna?

• Come riconosciamo l’albero migliore?

(23)

Bio CS

Massima parsimonia:

Ad ogni nodo interno dell’albero possiamo mettere A oppure G. Alle foglie, invece, dobbiamo rispettare le proporzioni osservate (3A, 1G).

AGCT AACT AACT AACT

Topologie possibili : 1

A A A G

? (A or G)

Al posto dei TAXA abbiamo i nucleotidi (osservati)

(24)

Massima parsimonia:

Consideriamo il nucleotide più frequente (A) come ancestor …

AGCT AACT AACT AACT

Alberi possibili : 1

A A A G

A or G 0 0

A

A or G 0 if A

1 if G 0 if A

0 if A 1 if A

Al posto dei TAXA abbiamo nt

scelta: A

(25)

Bio CS

Massima parsimonia:

Scegliamo i nucleotidi ai nodi interni in modo da spiegare i taxa (nt osservati) minimizzando il numero totale di sostituzioni!

AGCT AACT AACT AACT

Alberi possibili : 1

A A A G

A

1 if A Totale

sostituzioni : 1 (non male…)

(26)

Come determinare tutti i possibili alberi?

• Quando gli organismi sono 2 esiste un unico albero possibile:

A B

(27)

Bio CS

Come determinare tutti i possibili alberi?

• Se gli organismi fossero 3

• Il terzo potrebbe posizionarsi …

A B

(28)

Come determinare tutti i possibili alberi?

 E se gli organismi fossero 4 ?

 Per ognuno dei tre possibli alberi precedenti potremmo aggiungere il quarto organismo ad ognuno dei loro 4 rami (o potremmo usarlo come una nuova radice)

 Il numero di possibili alberi con 4 organismi è quindi:

 3*5=15

A B

Se partissimo da quest’albero con 3 organismi

(29)

Bio CS

Numero dei possibili alberi:

 N_i : n. di alberi dati i taxa

 B_i : n. di rami in un albero dati i taxa

 B_i=B_i-1+2, e anche i * 2-2

 N_i=N_i-1*(B_i-1+1)

 + 1 a causa della potenziale nuova radice

 N2= 1

 B2=2

Taxa Rami Alberi

2 2 1

3 4 3

4 6 15

5 8 105

6 10 945

7 12 10,395

8 14 135,135

9 16 2,027,025

10 18 34,459,425

11 20 654,729,075

(30)

Numero dei possibili alberi:

 B_i=B_i-1+2, e anche i x 2-2

 N_i=N_i-1*(B_i-1+1)

 N2= 1

 B2=2

2 2 1

3 4 3

4 6 15

5 8 105

6 10 945

7 12 10,395

8 14 135,135

9 16 2,027,025

10 18 34,459,425

11 20 654,729,075

A cosa assomiglia questo tasso di

crescita?

A cosa assomiglia questo tasso di

crescita?

(31)

Bio CS

Numero dei possibili alberi:

 B_i=B_i-1+2, e anche i x 2-2

 N_i=N_i-1*(B_i-1+1)

 N2= 1

 B2=2

2 2 1

3 4 3

4 6 15

5 8 105

6 10 945

7 12 10,395

8 14 135,135

9 16 2,027,025

10 18 34,459,425

11 20 654,729,075

E’ definito da una relazione di ricorrenza, quindi …

Giusto… come al solito, esponenziale

E’ definito da una relazione di ricorrenza, quindi …

Giusto… come al solito,

esponenziale

(32)

Possiamo “risparmiare” qualche albero rinunciando alla radice:

• Alberi radicati e non radicati

• Ovunque sia la radice “appiattitela”

(33)

Bio CS

Regole per alberi non radicati:

• Sono anch’essi biforcati

• Non è possibile che 3 rami partano da uno stesso nodo

A

B C

D

(34)

Possibili alberi non radicati per 4 taxa:

• Tre alberi possibili

A

B C

D

A

D C

B A

C B

D

Esistono altre

combinazioni?

(35)

Bio CS

Possibili alberi non radicati per 5 taxa:

• Per ognuno dei tre alberi (da 4 taxa) possiamo

aggiungere un ramo ad ognuno dei 5 rami disponibili

• 3*5=15 alberi

A

B C

D

(36)

“Radicare” un albero:

• Outgroup

• Includere un organismo che sappiamo a priori essere più distante evolutivamente da ogni taxa rispetto ad ogni

distanza tra i taxa appartenenti all’albero da radicare

A

B C

D se outgroup si posiziona qui …

outgroup A B C D

(37)

Bio CS

Numero di alberi non radicati:

 Ni : num. alberi dati i taxa

 Bi : num. rami in un albero dati i taxa

 B_i=B_i-1+2, e anche i * 2-3

 N_i=N_i-1*(B_i-1)

 non serve il +1 per l’eventuale nuova radice … qui non ci sono radici

 N₂= 1

 B₂=2

3 3 1

4 5 3

5 7 15

6 9 105

7 11 945

8 13 10,395

9 15 135,135

10 17 2,027,025

11 19 34,459,425

12 21 654,729,075

(38)

Comparazione (alberi non radicati vs radicati):

• Riduzione

consistente del numero di alberi

• … e nonstante questo abbiamo

guadagnato un solo taxa (in termini di

relazione tra num.

alberi e num. taxa)

Taxa Alb. non radicati Alb. radicati

3 1 3

4 3 15

5 15 105

6 105 945

7 945 10,395

8 10,395 135,135

9 135,135 2,027,025

10 2,027,025 34,459,425

11 34,459,425 654,729,075 12 654,729,075 13,749,310,575

(39)

Bio CS

Come possiamo ridurre la complessità del problema?

 Non possiamo utilizzare la programmazione dinamica …

 Il problema non è composto da sottoproblemi ripetitivi

 Ogni sottoproblema è un albero … e ogni albero è unico …

La complessità è ancora

esponenziale…

La complessità è ancora

esponenziale…

EURISTICHE

(40)

tutti gli alberi

• Ignorare larghi subset di possibili soluzioni

• Utilizzare euristiche o metodi di predizione

Ignorare questa combinazione di rami

(41)

Costruzione di alberi filogenetici:

euristica Branch and Bound

Bio CS

Poniamo un limite

superiore ragionevole alla lunghezza

complessiva dell’albero utilizzando un algoritmo veloce (ad es. UPGMA) Poi esploriamo le

possibili soluzioni

purchè non superino la lunghezza stimata inizialmente

B & B dipende molto dalla qualità dei dati … e non garantisce di trovare la soluzione ottimale

(42)

euristica Branch and Bound

Branch and Bound ci fa “perdere” taxa nella soluzione finale? NO

Ci fa perdere alcune “topologie” tra le possibili

soluzioni? SI (è proprio questo il suo obiettivo … ma tra di esse potrebbe esserci la soluzione ottimale)

A

B C

X D X X

Non preoccupiamoci di questi possibili modi di ramificare … vanno oltre la soglia di

lunghezza

(43)

Torniamo all’algoritmo di Massima parsimonia

Bio CS

 In alcune colonne i simboli sono tutti uguali

 Non forniscono nessuna informazione

 Tutti gli alberi hanno costo minimo

 In alcune colonne i simboli sono tutti diversi

 Anche queste sono inutili

 Colonne informative devono contenere

almeno due simboli diversi ed almeno uno di essi deve essere ripetuto almeno due volte

AGCT AACT AACT ACCT

A A A A

A 0 0

A 0 A

0

0 0

(44)

l’albero consenso

• Ogni colonna genera un albero

• Se le topologie coincidono l’algoritmo finisce qui

• Se esistono topologie differenti

utilizziamo un criterio di “maggioranza”

• Se il campione (numero di sequenze) è troppo piccolo eseguiamo un

bootstrapping :

• Estraiamo casualmente sequenze dal multiallineamento

• Generiamo più alberi

• Etichettiamo i rami con la percentuale di occorrenze in cui compaiono in un albero

• Queste informazioni vengono utilizzate come misura di “ripetibilità” (più un ramo è frequente e più lo consideriamo