Andrea G. B. Tettamanzi, 2003 Filogenetica Andrea G. B. Tettamanzi.
-
Upload
giustina-sorrentino -
Category
Documents
-
view
226 -
download
0
Transcript of Andrea G. B. Tettamanzi, 2003 Filogenetica Andrea G. B. Tettamanzi.
Andrea G. B. Tettamanzi, 2003
FilogeneticaFilogenetica
Andrea G. B. Tettamanzi
Andrea G. B. Tettamanzi, 2003
Scopi
Data una famiglia di sequenze,
• trovare l’albero di mutazione più parsimonioso
• ricostruire l’albero filogenetico
• valutare la significatività di un dato albero filogenetico
Andrea G. B. Tettamanzi, 2003
Memorizzazione efficiente di sequenze
1. AGGATGAATGGGCGAACAGC2. TGCTCGCGGGTAGAAGAAC3. TAGATGAATGGTAGAACAAC4. TGCAGCGTGATAGAACAAC5. TGGAGAAATGATAGAACAAC6. TGCACGCGGCATAGAACGAC7. TGGATAGATGATACCACAAT
m. TGGATGAATGATAGAACAAC (majority rule)
Andrea G. B. Tettamanzi, 2003
1. AGGATGAATGGGCGAACAGC2. TGCTCGCGGG TAGAAGAAC3. TAGATGAATGGTAGAACAAC4. TGCAG CGTGATAGAACAAC5. TGGAGAAATGATAGAACAAC6. TGCACGCGGCATAGAACGAC7. TGGATAGATGATACCACAAT
m. TGGATGAATGATAGAACAAC (majority rule)
Memorizzazione efficiente di sequenze
Andrea G. B. Tettamanzi, 2003
1. A=========GGC=====G=2. ==CTC=CGG=.=====G===3. =A========G=========4. ==C=G.CG============5. ====GA==============6. ==C=C=CGGC=======G==7. =====AG======CC====T
m. TGGATGAATGATAGAACAAC (majority rule)
Memorizzazione efficiente di sequenze
Andrea G. B. Tettamanzi, 2003
1. A=========GGC=====G=2. ==CTC=CGG=.=====G===3. =A========G=========4. ==C=G.CG============5. ====GA==============6. ==C=C=CGGC=======G==7. =====AG======CC====T
m. TGGATGAATGATAGAACAAC {1, 3, 5, 7, m’}m’. ==C=C=CGG=========== {2, 4, 6}
Memorizzazione efficiente di sequenze
Andrea G. B. Tettamanzi, 2003
m. TGGATGAATGATAGAACAAC1. A=========GGC=====G=3. =A========G=========5. ====GA==============7. =====AG======CC====T
m’. ==C=C=CGG===========2. ===T======.=====G===4. ====G.==T===========6. =========C=======G==
Memorizzazione efficiente di sequenze
m
g
m’
a
7
2 4 6
315
Andrea G. B. Tettamanzi, 2003
Spazio delle sequenze
},,,{ TGCAS alfabeto:
insieme delle sequenze },,1,:{* 1 niSsssS in
diventa uno spazio quando è dotato di operazioni, distanza
),(),(),(
),(),(
0),(
tudusdtsd
stdtsd
tsd
Andrea G. B. Tettamanzi, 2003
Similarità di sequenze
(Ovvero, distanza genetica)• Efficiente• Plausibile biologicamente
Mutazione puntuale distanza di Hamming
Cancellazione/inserimento metriche di Hamming con salti
Rimescolamento, inversione, ecc. ...
Considerando diversi tipi di mutazione con probabilità differenti distanze di Hamming pesate = edit distance
Andrea G. B. Tettamanzi, 2003
Edit Distances
Edit Operations:(a, a) Match(a, b) Replace(a, _) Delete(_, a) Insert
Rw EOp:
Levenshtein Distance (after В. Левенштейн):
1)(_,_),(
,1),(
0),(
awaw
babaw
aaw
operation weight or cost
Cost of an alignment:sum of the costs of all edit operationsthat lead from s to t.
Optimal alignment
Edit distance: cost of the optimal alignment
Andrea G. B. Tettamanzi, 2003
Costruzione di alberi filogenetici
0
0
0
0
21
221
112
jiij
NN
N
N
dd
dd
dd
dd
D
21 N
Andrea G. B. Tettamanzi, 2003
Algoritmi di “linkage”
ijjidji
,minarg),( 1
2
},{ ji
i j
3 ),(},,{ jkikkji ddfd
funzione di combinazione
Andrea G. B. Tettamanzi, 2003
Assunzione di fondo
• La distanza genetica tra due sequenze è direttamente proporzionale al tempo che le separa dalla loro sequenza progenitrice comune
},{ ji
i jijd
ijTijij Td
Andrea G. B. Tettamanzi, 2003
Minimum linkage
},min{},,{ jkikkji ddd
},{ ji
i jijd
kkjid },,{
},,,,{ kji
Andrea G. B. Tettamanzi, 2003
Maximum linkage
},max{},,{ jkikkji ddd
},{ ji
i jijd
kkjid },,{
},,,,{ kji
Andrea G. B. Tettamanzi, 2003
Average linkage
2},,{jkik
kji
ddd
},{ ji
i j kkjid },,{
},,,,{ kji
Andrea G. B. Tettamanzi, 2003
Average linkage: esempio
1 2 3 4 5 6 7 8- 2 4 4 6 8 10 11 1
- 4 4 7 7 10 11 2- 2 6 6 11 12 3
- 7 8 12 10 4- 3 7 7 5
- 7 7 6- 2 7
- 8
Andrea G. B. Tettamanzi, 2003
{1,2} {3,4} 5 6 7 8- 4 6.5 7.5 10 11 {1,2}
- 6.5 7 11.5 11 {3,4}- 3 7 7 5
- 7 7 6- 2 7
- 8
1 2 3 4 5 6 7 8- 2 4 4 6 8 10 11 1
- 4 4 7 7 10 11 2- 2 6 6 11 12 3
- 7 8 12 10 4- 3 7 7 5
- 7 7 6- 2 7
- 8
{1,2} 3 4 5 6 7 8- 4 4 6.5 7.5 10 11 {1,2}
- 2 6 6 11 12 3- 7 8 12 10 4
- 3 7 7 5- 7 7 6
- 2 7- 8
{1,2} 3 4 5 6 7 8- 4 4 6.5 7.5 10 11 {1,2}
- 2 6 6 11 12 3- 7 8 12 10 4
- 3 7 7 5- 7 7 6
- 2 7- 8
{1,2} 3 4 5 6 7 8- 4 4 6.5 7.5 10 11 {1,2}
- 2 6 6 11 12 3- 7 8 12 10 4
- 3 7 7 5- 7 7 6
- 2 7- 8
{1,2} {3,4} {5,6} {7,8}- 4 7 10.5 {1,2}
- 6.75 11.25 {3,4}- 7 {5,6}
- {7,8}
{1,2,3,4} {5,6} {7,8}- 6.875 10.875 {1,2,3,4}
- 7 {5,6}- {7,8}
{1-6} {7,8}- 8.9375 {1-6}
- {7,8}
{1,2} {3,4} 5 6 {7,8}- 4 6.5 7.5 10.5 {1,2}
- 6.5 7 11.25 {3,4}- 3 7 5
- 7 6- {7,8}
Andrea G. B. Tettamanzi, 2003
1 2 3 4 5 6 7 8
Andrea G. B. Tettamanzi, 2003
Algoritmi di Linkage: discussione
• Nessuno dei tre algoritmi garantisce di ottenere il “vero” albero filogenetico delle sequenze prese in esame
• Se tutti e tre gli algoritmi producono lo stesso albero, è molto plausibile che quello sia il “vero” albero filogenetico
• Se un certo raggruppamento/sottoalbero (ingl. clade, da gr. κλάδος, “gruppo”) compare in tutti e tre gli alberi, è molto plausibile che si tratti di un’unità valida filogeneticamente.
Andrea G. B. Tettamanzi, 2003
Trasformata di Farris (1)
Tutti e tre gli algoritmi di linkage forniscono sempre il risultatocorretto se
},{ ji
i j
jjiijiij mmd },,{},,{
ijim },,{ jjim },,{
Idea: usiamo una mappa reale Rnf },,1{:
ik
ij
dkfifki
djfifji
)()(::
)()(:,Esempio: idif 1)(
Andrea G. B. Tettamanzi, 2003
Trasformata di Farris (2)
ijfij djfifS )()(
2
1similarità
0i
i
j
)(if)( jf
ijd
ji
jiSCd
fijf
ij0
distanzaaggiustata
soddisfa la diseguaglianza ultrametrica:
fjkfik
fij ddd ,max
Andrea G. B. Tettamanzi, 2003
Algoritmo di linkage additivo
fissare arbitrariamente una sequenza k1
2 ijjkikji
dddji ,maxarg),(
3 ijjkiklji dddd 2
1},,{
N.B.: il risultato è un albero senza radice
Andrea G. B. Tettamanzi, 2003
Neighbor-Joining Method
• N. Saitou e M. Nei. Molecular Biology and Evolution, 4:406-425, 1987
0
0
0
0
21
221
112
jiij
NN
N
N
dd
dd
dd
dd
D
1
2
i
j Nla lunghezza degli archi deve essere“una buona approssimazione” delledistanze
Andrea G. B. Tettamanzi, 2003
Neighbor-Joining Method
• Basato sulla ricerca di unità tassonomiche operative (UTO)– che minimizzino la lunghezza totale dei rami dell’albero
– e questo ad ogni passo dell’algoritmo di raggruppamento
• Scopo: ottenere un albero additivo senza radice che approssimi la matrice delle distanze tra le sequenze
• Si procede in N – 2 cicli, ripetendo i passi seguenti:– raggruppare le due UTO più prossime, creando un arco interno tra
quella coppia e le altre UTO, seguendo un criterio di minimizzazione della lunghezza dell’abero ottenuto;
– calcolare la valutazione intermedia
– ricalcolare la matrice delle distanze raggruppando secondo l’average linkage.
Andrea G. B. Tettamanzi, 2003
NJ: Albero iniziale “a stella”
x
i
j
1
2
3
N
...
ji
ijdNL
1
1)0(
Andrea G. B. Tettamanzi, 2003
NJ: Selezione delle OTU più prossime
lunghezza dell’albero per una topologia in cui i e j sonoraggruppati insiemeijl
N
jihkhk
khij
N
jikk
jkikij dN
dddN
l
,,,1 2
1
2
1
)2(2
1
i
j
{i, j} ijjilji
,minarg),( x
k
h
Andrea G. B. Tettamanzi, 2003
NJ: Lunghezze degli archi
jZiZijjii dddL 2
1},{,
iZjZijjij dddL 2
1},{,
ad ogni iterazione, si calcolano solo le lunghezze di questidue nuovi archi.
jikikiZ d
Nd
,2
1
jikjkjZ d
Nd
,2
1
Andrea G. B. Tettamanzi, 2003
NJ: Ricalcolo della matrice delle distanze
2},,{jkik
kji
ddd
NN )1()1( NN
Andrea G. B. Tettamanzi, 2003
PHYLIP
http://cmgm.stanford.edu/phylip/index.html
Phylogeny Inference Package
Una collezione di metodi e algoritmi per la filogenetica molecolarefree, public domain e open-source.
Andrea G. B. Tettamanzi, 2003
Massima Verosimigianza
• Assume un tasso di mutazione costante• Tra tutti i possibili alberi, sceglie quello che soddisfa il criterio di
massima verosimigianza (probabilità massima).• Approccio perfezionato da Felsenstein (1973) e Thompson
(1975).• Casi particolari sono l’algoritmo di Fitch e Margoliash (1967),
minimi errori standard, e di Cavali-Sforza ed Edwards (1967), minimi quadrati.
• Anche se non esiste allo stato attuale una dimostrazione, si pensa che questo approccio alla costruzione di alberi filogenetici sia NP-difficile (è simile alla costruzione di alberi di Steiner).
Andrea G. B. Tettamanzi, 2003
Algoritmi Evolutivi
Numero di alberi possibili di n sequenze:
1
1
32n
i
i
Approcci alla costruzione di alberi filogenetici basata sul criteriodi massima verosimiglianza con algoritmi genetici sono stati propostida Lewis (1998) e Matsuda (1996)
Andrea G. B. Tettamanzi, 2003
Split Decomposition
Invece di tentare a tutti i costidi ricostruire un albero, è possibileprodurre un grafo più generaleche riassume tutti gli alberifilogenetici plausibili sulla base deidati.
SplitsTree
http://www.mathematik.uni-bielefeld.de/~huson/phylogenetics/splitstree.html
Andrea G. B. Tettamanzi, 2003
Phylogenetic Split (Fissione Filogenetica)
ANAAN \,,2,1,,,2,1
è un d-split se e solo se AlkAji ,,,
iljkjlikklij dddddd ,max
Indice di isolamento di uno split AAS ,
klijiljkjlik
AlkAji
S dddddd
,maxmin2
1
,,
misura quanto una fissione è supportata dai dati, e idealmentecoincide con la lunghezza del ramo che unisce i due sottoalberi
Andrea G. B. Tettamanzi, 2003
Split Metric
altrimenti0
,1),(
AjAijiS
split-d
),(S
SSij jid soddisfa ijij dd
distanza residua: 00 ijijij ddddefinisce una metrica che non ammette ulteriori fissioni con indicedi isolamento positivo: è il rumore non scomponibile per fissioni.
jiij
jiij
d d
d
,
, percentuale scomponibile per fissioni dellamatrice delle distanze
Andrea G. B. Tettamanzi, 2003
Split Decomposition: Algoritmo
• Ricorsivamente: posto che tutti i d-split relativi al sottoinsieme {1,…, i – 1} siano già stati determinti;
• per ogni split S = (A, B) di questo sottoinsieme, verificare se
BiA },{ }{, iBA o
siano ammissibili come d-split dell’insieme allargato a i.
• La procedura termina quando i = N.• Si può dimostrare che la complessità di questo algoritmo è
)( 6NO
Andrea G. B. Tettamanzi, 2003
Metodi Basati sui Caratteri
• Tutti i metodi visti fin qui utilizzano una matrice di distanze tra sequenze
• Metodi basati sulle distanze guardano all’evoluzione “da lontano”, ignorando informazioni di dettaglio
• Metodi basati sui caratteri partono dal dettaglio• Cercano di ripercorrere le traiettorie seguite dall’evoluzione• Ricostruzione “filologica” delle sequenze dei progenitori comuni• Siccome i metodi basati sulle distanze e sui caratteri sono
fondamentalmente differenti, una loro concordanza nelle conclusioni è considerata una forte prova a favore di un albero filogenetico
Andrea G. B. Tettamanzi, 2003
Parsimonia
• Premesse di fondo:– Le mutazioni sono eventi estremamente rari
– Più eventi improbabili un modello deve assumere, meno è probabile che il modello sia corretto
• Allineamento multiplo di sequenze• Concetto di “sito informativo”: per essere informativa, una
posizione deve:– contenere almeno due nucleotidi diversi
– ciascuno di questi nucleotidi deve comparire almeno due volte
• Parsimonia “pesata”
Andrea G. B. Tettamanzi, 2003
Esempio
1 2 3 4 5* 6*
1. G G G G G G
2. G G G A G T
3. G G A T A G
4. G A T C A T
1
2
3
4
1
3
2
4
1
4
2
3
Andrea G. B. Tettamanzi, 2003
Ricostruzione
TG G AA
G
G
A
G~A
GG A TA
G
G~A
A
G~A~T
GG T AA
G
G~T
A
G~T~A
IF S T THENR = S T
ELSER = S T
TS
R
Andrea G. B. Tettamanzi, 2003
Strategie di Ricerca
• La ricerca esaustiva su tutti gli alberi non è proponibile• Metodo branch and bound (Hardy e Penny 1982):
– Costruzione incrementale dell’albero
– Limite superiore della lunghezza di un albero parsimonioso
– Non si esplorano strade che portano ad alberi peggiori
– Garanzia di trovare l’ottimo, ma miglioramento solo di scala temporale, non di complessità, che resta esponenziale
• Metodi euristici, approssimati– Essenzialmente basati su hillclimbing o simulated annealing
– L’ottimo globale non è garantito
Andrea G. B. Tettamanzi, 2003
Bootstrapping
• Serve a misurare il grado di confidenza nell’albero ricostruito• Creazione di insiemi di sequenze artificiali, ottenuti estraendo a
caso le colonne delle sequenze reali con reimbussolamento• Costruzione per ciascun insieme artificiale, di un albero• Se gli alberi ricostruiti sono sempre uguali o molto simili =>
buona confidenza• Risultati da trattare con molta attenzione:
– Necessità di eseguire moltissimi test, altrimenti rumore;
– Tende a sottostimare la confidenza a livelli alti, e a sovrastimarla a livelli bassi
– “Fallacy of multiple tests” = semplici fluttuazioni statistiche sembrano avere significatività statistica