UNIVERSITÀ
Docente: Giorgio Valentini
Istruttore: Matteo Re
C.d.l.
DEGLI
STUDI DI MILANO
Biotecnologie Industriali e Ambientali
Biologia
computazionale
A.A. 2010-2011 semestre II
5
Evoluzione e filogenesi - 2
Bio
Costruzione di alberi filogenetici:
Classi di metodi disponibili
Metodi basati su:
• Distanza
• Massima parsimonia (minima
evoluzione)
• Massima verosimiglianza
Abbiamo già discusso un
medoto basato su distanze:
UPGMA
CS
Bio
Costruzione di alberi filogenetici:
Classi di metodi disponibili
Abbiamo già discusso un
medoto basato su distanze:
UPGMA
Abbiamo
bisogno di altri
metodi?
CS
Costruzione di alberi filogenetici:
problemi con UPGMA…
Bio
CS
Cosa non va in UPGMA?
(rivediamo l’esempio…)
A
B
C
D
A
B
C
D
0
6
6
7
0
4
5
0
3
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?
Costruzione di alberi filogenetici:
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
0
7
6
7
0
4
5
0
3
0
.5
.5
4
2.5
1
A
B
2
C
D
NB: è un effetto dell’ipotesi dell’orologio molecolare!
Costruzione di alberi filogenetici:
problemi con UPGMA…
Bio
CS
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)!
Produce questa matrice
Questo albero
A
B
1
1
2
A
1
B
C
A
B
C
0
4
3
0
3
..che produce
quest’albero
0
A
C
… e i due alberi sono DIVERSI !
C
B
Bio
Costruzione di alberi filogenetici:
Cronogrammi
Alberi ultrametrici
( cronogrammi)
CS
1
3
1
1
1
1 1
3
2
1
a b
c
Le distanze (nei cronogrammi) devono obbedire a 4 regole:
Non-negatività:
Distinguibilità:
Simmetria:
Disug. triangolare:
d(a,b) ≥ 0
d(a,b) = 0 if and only if a = b
d(a,b) = d(b,a)
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
0.4
a c b
2
Bio
Costruzione di alberi filogenetici:
Cronogrammi
Alberi ultrametrici
( cronogrammi)
CS
1
3
1
1
1
1 1
3
2
1
a b
c
Le distanze (nei cronogrammi) devono obbedire a 4 regole:
Non-negatività:
Distinguibilità:
Simmetria:
Disug. triangolare:
d(a,b) ≥ 0
d(a,b) = 0 if and only if a = b
d(a,b) = d(b,a)
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
0.4
a c b
2
Costruzione di alberi filogenetici:
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'.
Condizione dei tre punti:
A
B
C
A
B
C
Per ogni combinazione di tre taxa, le due distanze
maggiori devono essere uguali.
Bio
Costruzione di alberi filogenetici:
Esempio di errore di UPGMA
Velocità evolutive non costanti
A
B
CS
B
C
D
E
5
C 4
7
D 7
10
7
E
6
9
6
5
F
8
11
8
9
8
TOPOLOGIA
ERRATA
Bio
Costruzione di alberi filogenetici:
Esempio di errore di UPGMA
Velocità evolutive non costanti
A
B
Esiste un metodo chiamato
Neighbor Joining che
avrebbe ricostruito la
topologia dell’albero in modo
corretto.
CS
B
C
D
E
5
C 4
7
D 7
10
7
E
6
9
6
5
F
8
11
8
9
8
TOPOLOGIA
ERRATA
Bio
Costruzione di alberi filogenetici:
NeighborJoining (NJ)
CS
Neighbor Joining e costruzione di alberi additivi
(filogrammi, lunghezza rami proporzionale a distanze
genetiche)
A
a
B
b
x
c
C
d
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.
Bio
Costruzione di alberi filogenetici:
Alberi additivi
CS
Se l’albero è additivo, allora deve essere rispettata la:
Condizione dei 4 punti
A
c C
a
x
b
d D
B
dAC + dBD = dAD + dBC = a + b + c + d + 2x = dAB + dCD + 2x
dAB + dCD < dAC + dBD
Condizione dei 4
punti
dAB + dCD < dAD + dBC
vicini
non-vicini
Fondamentalmente dice che la distanza tra i vicini è minore di quella tra i non-vicini.
Bio
Costruzione di alberi filogenetici:
Neighbor Joining (NJ)
CS
NJ: costruzione dell’albero più corto
Partiamo da una struttura a stella (nessuna struttura gerarchica)
C
A
D
B
Distanze pair-wise
Lunghezza dell’albero
Numero di taxa
Bio
Costruzione di alberi filogenetici:
Neighbor Joining (NJ)
CS
Possiamo utilizzare queste formule per calcolare la lunghezza del nuovo albero:
LXY
N
 N

1

  ( D1k  D2 k )  ( N  2)( L1 X  L2 X )  2 LiY 
2( N  2)  k  3
i 3

L1 X  L2 X  D12

N
i 3
DiY
N
N
1

Dij


( N  3)  1 i 3 i  j
(Saitou and Nei, 1987)
Bio
Costruzione di alberi filogenetici:
Neighbor Joining (NJ)
CS
Ad ogni passo tutte le coppie di vicini vengono esaminate e viene
scelta quella che produce l’albero più corto (criterio di minima
evoluzione).
(Saitou and Nei, 1987)
Bio
Costruzione di alberi filogenetici:
Neighbor Joining (NJ)
CS
Come nel caso di UPGMA ad ogni ciclo viene aggiunto un ramo
interno … ma adesso è sempre il ramo più corto possibile !
(Saitou and Nei, 1987)
Bio
Costruzione di alberi filogenetici:
Neighbor Joining (NJ)
CS
Come nel caso di UPGMA ad ogni ciclo viene aggiunto un ramo
interno … ma adesso è sempre il ramo più corto possibile !
Albero non radicato
(Saitou and Nei, 1987)
Costruzione di alberi filogenetici:
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/
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
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?
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Massima parsimonia:
• Come costruiamo tutti i possibili alberi per una data colonna?
• Come riconosciamo l’albero migliore?
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
? (A or G)
? (A or G)
A
A
? (A or G)
A
G
Al posto dei TAXA abbiamo i nucleotidi (osservati)
Topologie
possibili : 1
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Massima parsimonia:
• Come costruiamo tutti i possibili alberi per una data colonna?
• Come riconosciamo l’albero migliore?
Consideriamo il nucleotide più frequente (A) come ancestor …
AGCT
AACT
AACT
AACT
scelta: A
0 if A
1 if G
A
0 if A
A or G
A or G
0
0
0 if A
A
A
A
Al posto dei TAXA abbiamo nt
1 if A
G
Alberi possibili : 1
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Massima parsimonia:
• Come costruiamo tutti i possibili alberi per una data colonna?
• Come riconosciamo l’albero migliore?
Scegliamo i nucleotidi ai nodi interni in modo da spiegare i taxa (nt
osservati) minimizzando il numero totale di sostituzioni!
A
AGCT
AACT
AACT
AACT
Alberi possibili : 1
A
A
1 if A
A
A
A
G
Totale
sostituzioni : 1
(non male…)
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Come determinare tutti i possibili alberi?
• Quando gli organismi sono 2 esiste un unico albero
possibile:
A
B
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
Come determinare tutti i possibili alberi?
• Se gli organismi fossero 3
• Il terzo potrebbe posizionarsi …
A
B
CS
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
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
Se partissimo da quest’albero
con 3 organismi
A
B
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Numero dei possibili alberi:




Ni : n. di alberi dati i taxa
Bi : n. di rami in un albero dati i taxa
Bi=Bi-1+2, e anche i * 2-2
Ni=Ni-1*(Bi-1+1)
 + 1 a causa della potenziale nuova
radice
 N 2= 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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Numero dei possibili alberi:




Ni : n. di alberi dati i taxa
Bi : n. di rami in un albero dati i taxa
Bi=Bi-1+2, e anche i x 2-2
Ni=Ni-1*(Bi-1+1)
 + 1 a causa della potenziale nuova
radice
 N 2= 1
 B2=2
A cosa assomiglia
questo tasso di
crescita?
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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Numero dei possibili alberi:




Ni : n. di alberi dati i taxa
Bi : n. di rami in un albero dati i taxa
Bi=Bi-1+2, e anche i x 2-2
Ni=Ni-1*(Bi-1+1)
 + 1 a causa della potenziale nuova
radice
 N 2= 1
 B2=2
Taxa
Rami
Alberi
2
2
1
3
4
3
E’ definito da una relazione
4
6
5
di ricorrenza, quindi
…8
15
105
6
10
945
7
12
10,395
Giusto… come al 8solito,14
9
16
esponenziale
135,135
2,027,025
10
18
34,459,425
11
20
654,729,075
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
Possiamo “risparmiare” qualche albero
rinunciando alla radice:
• Alberi radicati e non radicati
• Ovunque sia la radice “appiattitela”
CS
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Regole per alberi non radicati:
• Sono anch’essi biforcati
• Non è possibile che 3 rami partano da uno stesso nodo
A
D
B
C
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Possibili alberi non radicati per 4 taxa:
• Tre alberi possibili
A
D
A
D
B
C
C
B
A
B
D
C
Esistono altre
combinazioni?
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
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
D
B
C
Costruzione di alberi filogenetici:
Massima parsimonia
Bio
CS
“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
se outgroup si
posiziona qui …
A
D
B
C
outgroup
A
B C
D
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Numero di alberi non radicati:




Ni : num. alberi dati i taxa
Bi : num. rami in un albero dati i taxa
Bi=Bi-1+2, e anche i * 2-3
Ni=Ni-1*(Bi-1)
 non serve il +1 per l’eventuale
nuova radice … qui non ci sono
radici
 N 2= 1
 B2=2
Taxa
Rami
Alberi
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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
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
Bio
Costruzione di alberi filogenetici:
Massima parsimonia
CS
Come possiamo ridurre la complessità del problema?
La complessità è
ancora
esponenziale…
 Non possiamo utilizzare la
programmazione dinamica …
 Il problema non è composto da
sottoproblemi ripetitivi
 Ogni sottoproblema è un albero …
e ogni albero è unico …
EURISTICHE
Bio
Costruzione di alberi filogenetici:
Euristiche che evitano l’enumerazione di
tutti gli alberi
• Ignorare larghi subset di possibili
soluzioni
• Utilizzare euristiche o metodi di
predizione
CS
Ignorare questa
combinazione di
rami
Bio
Costruzione di alberi filogenetici:
euristica Branch and Bound
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
Bio
Costruzione di alberi filogenetici:
euristica Branch and Bound
CS
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
X
X
X
D
C
Non preoccupiamoci di questi possibili
modi di ramificare … vanno oltre la
soglia di lunghezza
Bio
CS
Torniamo all’algoritmo di
Massima parsimonia
 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
AGCT
AACT
AACT
ACCT
 Colonne informative devono contenere
almeno due simboli diversi ed almeno uno
di essi deve essere ripetuto almeno due volte
A
A
0
0
0
0
A
A
A
0
A
0
A
Bio
Massima Parsimonia:
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
supportato dai dati)
CS
Bio
Metodi per costruire alberi filogenetici
CS
Metodi basati su:
• Distanza
• Massima parsimonia
• Massima verosimiglianza
Questi li abbiamo visti…
Il seguito nella prossima puntata …