Lezione 11

UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 10
Evoluzione Molecolare e Analisi Filogenetica
Introduzione
 Problema:
 studio della storia evolutiva di un insieme di specie
 Struttura usata per rappresentare l’evoluzione:
 albero evolutivo o filogenesi
 Struttura ad albero in cui le foglie sono etichettate dalle
specie esistenti, i nodi interni dalle specie progenitrici
 Problema:
 dato un insieme di specie costruire un albero evolutivo
 In genere struttura dell’albero e specie progenitrici
sono incognite
2
Albero evolutivo
AAAGGTACC
G  T mutation
AAATGTACC
A  G mutation
AAATGTACC
AAATGTGCC
A  T mutation
AAATGTGCC
TAATGTGCC
3
I passi
1. Allineamento
2. Modello di sostituzione
3. Costruzione dell’albero
4. Valutazione dell’albero
4
Allineamento
 Scelta delle procedure di allineamento
 Dipendenza dal computer nulla, parziale o completa
 Richiamo della filogenia assente, a priori o ricorsivo
 Stima dei parametri di allineamento a priori, dinamica o
ricorsiva
 Possibile allineamento rispetto a strutture superiori
 Ottimizzazione matematica statistica o non statistica
 Estrazione di un insieme di dati filogenetici
dall’allineamento
 trattamento degli indels
5
Modello di sostituzione
 Matrici di sostituzione tra basi
 Simmetriche (reversibilità nel tempo) o no
 Stazionarie o no
 Tassi di sostituzione tra siti eterogenei
 Esempio: terzo codone più variabile dei primi due
6
Costruzione dell’albero filogenetico
 Metodi basati sulla distanza
 L’istanza del problema è un insieme di specie e delle
distanze evolutive tra esse (Matrice delle distanze)
 L’obiettivo è costruire un albero che rispetti le distanze
date
7
Distanza genetica tra sequenze
omologhe
 Numero di sostituzioni per sito
 Sono sottostimate (sostituzioni convergenti,
retromutazioni)
ACTGAACGTAACGC
C->T->A
A->T->A
AATGGACGTAACGC
TCTGGACGTAACGC
8
Unweighted Pair Group Method with
Arithmetic mean (Sokal e Michener 1958)
 Funziona per velocità circa costanti nelle diverse linee
evolutive: relazione lineare tra distanza e tempo di
divergenza
 Usa un algorimo di clusterizzazione sequenziale
iterativo
 Collega le sequenze più vicine a un antenato comune
 Sostituisce le due sequenze col padre
 Itera la procedura fino ad avere un solo elemento
(radice)
9
UPGMA (Sokal, Michener, 1958)
 Initialize
 Ci = {si}, for all i.
0.1
0.1
0.1
 Repeat until one cluster left:
 Find two clusters Ci, Cj with
mini=1,..,n;j=1,…,n dij=(dpq)/|Ci||Cj|, pCi,
qCj
 Define node k with i,j as children, edge
weight dij
0.4
0.4
Problem
of UPGMA
 Form cluster k, remove i,j clusters.
10
UPGMA - Esempio
A
B
B
dAB
C
dAC
dBC
D
dAD
dBD
C
dCD
Sia dAB il valore più piccolo; A e B vengono raggruppate e
il punto di biforcazione posizionato alla distanza dAB/2
11
UPGMA - Esempio
AB
C
d(AB)C
D
d(AB)D
C
dCD
ove d(AB)C = (dAC+dBC) /2 e d(AB)D = (dAD+dBD) /2.
Sia ora d(AB)C il valore più piccolo; C è raggruppata con
AB con punto di biforcazione a distanza d(AB)C/2.
Infine si raggruppa con D e la radice è posta a distanza
d(ABC)D = [(dAD+dBD+dCD)/3] /2
12
UPGMA - Esempio
A
B
dAB/2
C
d(AB)C/2
D
d(ABC)D /2
13
Neighbor Joining (Saitou, Nei, 1987)
 Ricostruisce l’albero senza radice che minimizza la
somma delle lunghezze dei rami
 Neighbors: coppia di sequenze, singole o composite,
connesse attraverso un singolo nodo interno
D
A
E
B
C
14
Neighbor Joining (Saitou-Nei, 1987)
 Initialize:
 T={sequences}, L=T
 Choose i,jL such that dij-ri-rj minimized. Rest similar
to UPGMA with similar modification on edge weights
to k.
 Here, ri, rj are the average distances from i,j to other
nodes in L – to compensate long edges.
15
Neighbor joining - Esempio
Situazione iniziale:
16
Neighbor joining - Esempio
Tra le n(n-1)/2 diverse coppie si cerca quella che
minimizza la somma delle lunghezze dei rami nell’albero
seguente:
17
Neighbor joining - Esempio
Si itera la procedura sulla nuova stella con n-1 foglie
ottenuta sostituendo ai due neighbors trovati la loro
combinazione
18
Costruzione dell’albero filogenetico
 Metodi basati sulle sequenze
 Istanza del problema : insieme di sequenze biologiche
appartenenti a diverse specie
 Output: albero evolutivo (con i nodi interni etichettati
dalle sequenze progenitrici) di costo minimo
 Punteggio di un arco := punteggio dell’allineamento ottimale
delle sequenze associate ai nodi dell’arco
 Punteggio dell’albero := somma dei punteggi degli archi
 Caso particolare: la struttura dell’albero viene data.
Ricerca sequenze progenitrici. Anche questo caso è
difficile.
19
Maximum parsimony (MP - Eck,
Dayhoff 66)
 Rasoio di Occam: La miglior spiegazione dei dati è la
più semplice
 Si trova l’albero che spiega le differenze osservate col
minor numero di sostituzioni
 Metodo qualitativo; determina la topologia dell’albero,
non la lunghezza dei rami
 Molto lento. Usa branch and bound
20
MP
 Siti informativi: favoriscono alcuni alberi rispetto ad
altri
 In generale, contengono almeno due nucleotidi
ciascuno dei quali è presente in almeno due sequenze
 MP è molto usato per la sua semplicità; è inadeguato
per sequenze nucleotidiche, attendibile come analisi
preliminare per le proteine
 Genera molti alberi equivalenti
21
Maximum Likelihood (ML, Felsenstein
81)
 Cerca il modello evolutivo, albero compreso, che ha la
massima verosimiglianza rispetto alla produzione delle
sequenze osservate
22
Maximum Likelihood
 Modello di Jukes-Cantor (1969) : uguale probabilità di
sostituzione (1 parametro )
 Modello di Kimura (1980) (2 parametri): diversi tassi di
sostituzione ( e ) da purina (A,G) a purina o da pirimidina
(C,T,U) a pirimidina
 Processo molto lento, per la necessità di eseguire una ricerca
esaustiva su tutti gli alberi
 Risultati migliori di MP nelle simulazioni
23
ML - Esempio
t1
t5
1a
5 
2b
t2
0 
t3
t6
3c
6 g
t4
4d
L = gp P(t5) Pg(t6) Pa(t1) Pb(t2) Pgc(t3) Pgd(t4)
24
ML - Esempio
 Problema della determinazione di Pij(t)
 Necessità di considerare diverse topologie e diverse
lunghezze dei rami.
25
Metodo dei quartetti
 Per ogni quattro sequenze si costruisce un albero di 4
nodi (quartetto), ad esempio usando ML
 Si costruisce poi un grande albero formato dalla
(maggior parte di) questi piccoli alberi. Questo passo è
NP-difficile
 Un nuovo approccio: correzione dei dati
26
Quartetti e Correzione
Albero
originale
c
a
b
d
e
a
d
c
e
correzione
a
c
b
a
d
b
e
a
d
b
e
b
d
c
e
a
c
d
e
c
errore
27
Il Software HyperCleaning
 Per meno di 30 taxa, HyperCleaning è confrontabile
con fastDNAml (che usa il punteggio di maximum
likehood), e si comporta meglio di NJ.
 Per più di 30 taxa, i metodi ML e MP puri richiedono
giorni e producono risultati scadenti. HyperCleaning si
comporta bene, con punteggi migliori.
28
29
Valutazione degli alberi: bootstrap
(Efron 79)
 Data la matrice di allineamento A di N sequenze lunghe
L si generano n (es, n=100) allineamenti simulati :
 Per j da 1 a L, si estrae un numero casuale r tra 1 e L e si
pone la j-esima colonna di Ak uguale alla r-esima di A
 si costruiscono gli alberi filogenetici
 Si attribuisce a ogni nodo un coefficiente di
significatività pari alla percentuale di simulazioni che lo
supportano
30
Confronto tra filogenesi
 Tutti i metodi visti sono NP-hard
 E’ possibile costuire alberi approssimanti e
confrontarli per ottenere un albero migliore
31
Problemi di confronto
 L’istanza dei problemi di confronto è un insieme di
alberi evolutivi.
Esistono vari problemi di confronto
 MAST
 MIT
32
MIT
 Maximum Isomorphic Subtree
 L’obiettivo è individuare un sottoalbero S’ tali che gli
alberi ristretti a S’ siano tutti isomorfi.
 Due alberi sono isomorfi se qualunque coppia di foglie
ha uguale distanza in entrambi gli alberi.
 Nel caso gli alberi siano pesati si ha un nuovo
problema: MWT (Maximum Weighted Subtree)
33
MAST
 Maximum agreement subtree
 L’obiettivo del problema è individuare il massimo
sottoinsieme di specie S’ per cui gli alberi ristretti
all’insieme S’ sono omomorfi.
 Due alberi sono omomorfi se risultano isomorfi a meno
di nodi di grado 1.
34
Complessità dei problemi di confronto
 I problemi di confronto sono NP-hard già su tre alberi
 Inoltre non sono facilmente trattabili per
l’approssimazione
35
Software filogenetico
 PHYLIP
 PROTDIST
 PROTPARS
 DNADIST
 DNAML
 fastDNAml
 PAUP
36