1
Biophysik F1-Praktikum – Kursteil "Molekulare Evolution"
Thorsten BurmesterInstitut für Zoologie
Universität Mainz
2
Wie erhalte ich aus meinen (Sequenz-) Daten einen Stammbaum, und was sagt mir dieser?
Sequenz 1: KIADKNFTYRHHNQLVSequenz 2: KVAEKNMTFRRFNDIISequenz 3: KIADKDFTYRHW-QLV Sequenz 4: KVADKNFSYRHHNNVVSequenz 5: KLADKQFTFRHH-QLV Sequenz 5
Sequenz 3
Sequenz 2
Sequenz 4
Sequenz 1
Ziel des Kurses:
3
Programm
Grundlagen der Molekularen Evolution Datenbanken und Datenbankanalysen Sequenzalignment Stammbaumerstellung Statistische Auswertung
4
Warum molekulare Phylogenie?
Verständnis von phylogenetischen Zusammenhängen:
• Organismische Evolution (Systematik)
• Evolution von Proteinfamilien (Funktion!)
• forensische Medizin (Bsp. HIV)
• Epidemiologie
• Mathematische Probleme
5
Rekonstruktion von Verwandtschaftsverhältnissen
A. Morphologische DatenB. Sequenzdaten
Vorteil der Sequenzdaten:
- leichte Zugänglichkeit- Grosse Datenmenge- Zumeist frei von Gewichtungen- können aber dennoch zu falschen Ergebnissen führen!
Warum molekulare Phylogenie?
6
Voraussetzungen der molekularen Phylogenie
1. Evolution vollzieht sich durch Veränderungen.
2. Verwandte Spezies stammen von einem gemeinsamen Vorfahren ab.
3. Die Speziesbildung vollzog sich durch hierarchische Auftrennung.
4. Deren Verlauf läßt sich durch Stammbäume darstellen.
5. Es gibt nur einen historisch korrekten Stammbaum.
6. Organismen sind historisch. Sowohl die Morphologie als auch die DNA- und
Aminosäuresequenzen speichern die Informationen über die Vergangenheit.
7. Die Methoden der molekularen Evolution erlauben die Extraktion der in der
DNA bzw. den Proteinen gespeicherten Informationen.
7
Schwestergruppen
Was ist ein Stammbaum?
Darstellung der Verwandtschaftsverhältnisse
A
B
C
A – F auch "operational taxonomic units" (OTUs)
D
E
F
A
B
C
D
E
F
t t
8
Phylogenetische Grundbegriffe
A B C D E A B C D E
Dichotomie Polytomie
Ast(branch)
Knotenpunkt(node)
Außengru
ppe
(outg
roup)
9
Phylogenetische Grundbegriffe
Monophylie
A B C D E F (AB)(CDEF)(DEF)(EF)
monophyletische Taxa
10
Paraphylie=> nicht alle Nachkommen werden erfasst
Vögel
aufgrund von Plesiomorphien(ursprünglichen Merkmalen)
Phylogenetische Grundbegriffe
"Reptilien"
Schildkröten Krokodile
Eidechsen +Schlangen
11
"Geier"
Neuwelt-Geier
Storchen-vögel Raubvögel
Altwelt-Geier
Polyphylie=> verschiedenen Ursprungs
aufgrund von Homoplasien (Konvergenzen)
Phylogenetische Grundbegriffe
12
ungewurzeletes Phylogramm
Vogelspinne
Heuschrecke
Languste
Tausendfüsser
Regenwurm
Tintenfisch
Schnecke
=> keine Evolutions"richtung"
13
Stammbaum
Regenwurm
TintenfischSchnecke
Tausendfüsser
Vogelspinne
Languste
Heuschrecke
Mensch (Außengruppe)
Wurzel("Root")
Mit Außengruppe gewurzelt
= "outgroup"
t
14
Molekure Phylogenie
Vorgehensweise zur Stammbaumerstellung:A. Wie ist meine Sequenz zu anderen verwandt?• Auswahl ähnlicher Sequenzen aus Datenbanken• Sequenzalignment• Molekularphylogenetische Analyse• Statistische Überprüfung
B. Wie sind bestimmte Taxa miteinander verwandt?• Auswahl geeigneter Sequenzen• Sequenzierung (Datenbanken, Klonierung, PCR)• Sequenzalignment usw. wie oben
15
Datenbanksuche:
Welche Sequenz ist meiner Sequenz "ähnlich"?
=> Sequenzvergleich: "Alignment" (dt. Alignierung)DPEFKLSYFREDIAINSHHWHWHVIYPVGSNPS--DKKINRKGELFYYMHEQMLARYDAE
::: ::::::::: :: :::::: :: :: : :::::: ::: :: :::: :DPEYKLSYFREDIGINAHHWHWHIVYPATWNPTVMGKEKDRKGELFFYMHQQMCARYDSE
16
Datenbanksuche
z.B. BLAST (Basic Local Alignment Search Tool)=> vergleicht zwei Sequenzen miteinander
BLASTN: Vergleicht eine Nukleinsäuresequenz mit Nukleinsäuredatenbank
=> nahe verwandte SequenzenBLASTP: Vergleicht eine Aminosäuresequenz mit Proteindatenbank.
=> entfernt verwandte Sequenzen
17
Datenbanksuche
.BLASTX: Vergleicht eine Nukleinsäuresequenz translatiert in allen 6 Leserastern mit Proteindatenbank.
=> Für welches Protein kodiert meine Sequenz?
TBLASTN: Vergleicht eine Aminosäuresequenz mit Nukleinsäure- datenbank, die in allen 6 Leserastern translatiert wird.
=> findet z.B. nicht annotierte Proteine in DNA-Daten
TBLASTX: Vergleicht die Translationsprodukte aller drei Leseraster einer Nukleinsäuresequenz mit den Translationsprodukten aller 6
Leseraster einer Nukleinsäuredatenbank. => z.B. entfernte Verwandtschaft unbek. DNA-Sequenzen
18
BLAST (Basic Local Alignment Search Tool)
19
Multiples Sequenz-Alignments
Gegeben:
Gesucht:
SeqA N A F L S SeqB N A F SSeqC N A K Y L SSeqD N A Y L S
SeqA N A - F L S SeqB N A - F - SSeqC N A K Y L SSeqD N A - Y L S
20
Sequenzalignments
Algorithmus (z.B. ClustalX): 1. paarweiser Vergleichen aller Sequenzen
miteinander => Berechnung der Distanzen zw. Sequenzen
2. gruppiert Sequenzen nach Ähnlichkeit (Cluster-Bildung)
3. Erstellung paarweiser Alignments4. sukzessives Alignment nach Ähnlichkeit, dabei die ähnlichsten Sequenzpaare zuerst
Wie erhält man ein multiples Sequenzalignment?
21
CLUSTALX
ABCD
1) Sequenzvergleich
Alle Sequenzen werden miteinander verglichen (schnelles "quick and dirty" Alignment) => Berechnen der Distanzen
22
CLUSTALX
"guide tree"
ADBC
2) Ähnliche Sequenzen werden gruppiert
=> Cluster-Analyse = Erstellung eines hierarchischen Stammbaums ("guide tree").
-D
0.77-C
0.820.45-B
0.270.890.75-A
DCBA
23
ADBC
CLUSTALX
3) Alignment von nahe verwandten Sequenzen; die ähnlichsten zuerst.
BC
AD
24
BC
AD
AD
BC
ADBC
CLUSTALX
4) Sukzessives globales Alignment
Lücken = "gaps"
25
Alignment Parameter
Substitutionsmatrix (Wahrscheinlichkeit von nt bzw. AS-Austauschen)
"Gap creation" und "Gap length weights"
jeweils für paarweise und Multi-Alignments
26
StammbaumerstellungAnzahl der möglichen Stammbäume:
Number
of OTUs
Number of
rooted trees
Number of
unrooted trees
2 1 1
3 3 1
4 15 3
5 105 15
6 954 105
7 10395 954
8 135135 10395
9 2027025 135135
10 34459425 2027025
27
Stammbaumerstellung
1. Matrix-orientierte Methoden• UPGMA (Unweighted Pair-Group Method with Arithmetric Means)
• Neighbor-joining• Minimal Evolution (least squares)
2. Charakter-orientierte Methoden• Maximum Parsimony• Maximum Likelihood
28
Matrix-orientierte Methoden
Aus jedem Datensatz kann im Prinzip eine Distanzmatrix erstellt werden
Zwei Schritte:
1. Berechnen der paarweisen Abstände zwischen den einzelnen Sequenzen
2. Erstellen eines Stammbaums anhand dieser Abstandsdaten
29
Sequenzevolution
Ursprungssequenz
Sequenz A
Sequenz B
ZeitMutationen
Unterschied = Divergenz = Distanz
30
Berechnung einer Distanzmatrix
Sequenz 1 TATAAGCATGACTAGTAAGCSequenz 2 TATTAGCATGACTGGTAACCSequenz 3 TATTGGCATGACTAGCAGGC Sequenz 4 TGTTGCCACGATTAGCTACC Sequenz 5 CGTAGCTATGACCAACGGGC
Distanz = Durchschnittliche Änderung pro Position
hier: 20 Positionen; => Wieviele beobachtete Änderungen?
31
1 2 3 4 5Sequenz 1 0.00 0.15Sequenz 2 Sequenz 3 Sequenz 4 Sequenz 5
1 2 3 4 5Sequenz 1 0.00 0.15Sequenz 2 Sequenz 3 Sequenz 4 Sequenz 5
Distanzmatrix
1 2 3 4 5 Sequenz 1 0.00 0.15 0.20 0.45 0.50Sequenz 2 0.00 0.25 0.40 0.65Sequenz 3 0.00 0.35 0.40Sequenz 4 0.00 0.50Sequenz 5 0.00
1 2 3 4 5 Sequenz 1 0.00 0.15 0.20 0.45 0.50Sequenz 2 0.00 0.25 0.40 0.65Sequenz 3 0.00 0.35 0.40Sequenz 4 0.00 0.50Sequenz 5 0.00
Abstand zwischen Sequenz 1 und Sequenz 2, ausgedrückt in durchschnittlichen Änderungen pro Nukleotidposition (unkorrigierte Hamming-Distanz).
32
Abstand gegen Zeit!
t
%
beobachteter Abstand
tatsächlicher Abstand zweier Sequenzen= Anzahl der Mutationen
=> Abstand wird unterschätzt!
Sättigung
33
Warum?
13 Mutationen =>3 Unterschiede
34
Korrektur der Distanzen
t
%
beobachteter Abstand
tatsächlicher Abstand= Anzahl der Mutationen
Korrektur
35
Korrektur der Distanzen
Frage: Wie korrigieren wir?
Wir wollen die tatsächliche Anzahl der evolutiven Ereignisse rekonstruieren.
Wir brauchen also ein Evolutionsmodell, welches die Wahrscheinlichkeit von multiplen Austauschen, Rückmutationen etc. berücksichtigt.
36
DNA-Evolutionsmodelle
1969: Jukes & Cantor (JC) 1980: Kimura 2-Parameter (K2P) 1981: Felsenstein 81 (F81) 1985: Hasegawa, Koshino & Yano
(HKY85) 1990: General Reversible Model (REV) etc.
37
Evolutionsmodell Jukes & Cantor
pK
3
41ln
4
3
K ist der berechnete Abstand (Anzahl der tatsächlichen Substitutionen), p der beobachtete Abstand zwischen zwei Sequenzen.
Korrigierte Distanz nach Jukes & Cantor:
38
Abstandsberechnung - Proteine
Modelle für Proteinevolution meist empirisch.
Nach Kimura 1983: D = - ln(1 - p - 0.2 x p2) Beispiel: Beobachtete Distanz = 60% => p = 0.6 => D = - ln(1 – 0.6 – 0.2 x 0.62) = 1.11474
=> d.h., im Schnitt hat an jeder Position ~ 1,11 AS-Austausche stattgefunden
39
Aber: Modell ist zu einfach! Denn jeder Aminosäureaustausch
wird gleich bewertet. In der Natur aber nicht so
beobachtet. In der Praxis sind meist bessere
Modelle notwendig. Wir kennen diese Modelle: => PAM, BLOSUM-Matrizen
40
Aminosäureeigenschaften
CP
GGAVI
L
MF
Y
W HK
RE Q
DN
S
T
CSH
S+S
positiv
geladenpolar
aliphatisch
aromatisch
klein
Sehr klein
hydrophob
A R N D C Q E G H I L K M F P S T W Y V B Z
A 2 -2 0 0 -2 0 0 1 -1 -1 -2 -1 -1 -3 1 1 1 -6 -3 0 2 1 R -2 6 0 -1 -4 1 -1 -3 2 -2 -3 3 0 -4 0 0 -1 2 -4 -2 1 2 N 0 0 2 2 -4 1 1 0 2 -2 -3 1 -2 -3 0 1 0 -4 -2 -2 4 3 D 0 -1 2 4 -5 2 3 1 1 -2 -4 0 -3 -6 -1 0 0 -7 -4 -2 5 4 C -2 -4 -4 -5 12 -5 -5 -3 -3 -2 -6 -5 -5 -4 -3 0 -2 -8 0 -2 -3 -4 Q 0 1 1 2 -5 4 2 -1 3 -2 -2 1 -1 -5 0 -1 -1 -5 -4 -2 3 5 E 0 -1 1 3 -5 2 4 0 1 -2 -3 0 -2 -5 -1 0 0 -7 -4 -2 4 5 G 1 -3 0 1 -3 -1 0 5 -2 -3 -4 -2 -3 -5 0 1 0 -7 -5 -1 2 1 H -1 2 2 1 -3 3 1 -2 6 -2 -2 0 -2 -2 0 -1 -1 -3 0 -2 3 3 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 2 -2 2 1 -2 -1 0 -5 -1 4 -1 -1 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 -3 4 2 -3 -3 -2 -2 -1 2 -2 -1 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 0 -5 -1 0 0 -3 -4 -2 2 2 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 0 -2 -2 -1 -4 -2 2 -1 0 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 -5 -3 -3 0 7 -1 -3 -4 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 1 0 -6 -5 -1 1 1 S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 1 -2 -3 -1 2 1 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 -5 -3 0 2 1 W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 0 -6 -4 -4 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 -2 -2 -3 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 0 0 B 2 1 4 5 -3 3 4 2 3 -1 -2 2 -1 -3 1 2 2 -4 -2 0 6 5 Z 1 2 3 4 -4 5 5 1 3 -1 -1 2 0 -4 1 1 1 -4 -3 0 5 6
F
FC
PAM-Distanzmatrix
Y
79-4
42
PAM und BLOSUM Matricen
Hohe Sequenzähnlichkeit
Geringe Sequenzähnlichkeit
PAM 1
PAM 120
PAM 250
Hohe Sequenzähnlichkeit
Geringe Sequenzähnlichkeit
BLOSUM 80
BLOSUM 62
BLOSUM 30
43
Distanzmatrix
Sequenz 1 0.000 0.236 0.621 0.702 1.510Sequenz 2 0.000 0.599 0.672 1.482Sequenz 3 0.000 0.112 1.561Sequenz 4 0.000 1.425Sequenz 5 0.000
Sequenz 1 0.000 0.236 0.621 0.702 1.510Sequenz 2 0.000 0.599 0.672 1.482Sequenz 3 0.000 0.112 1.561Sequenz 4 0.000 1.425Sequenz 5 0.000
• Ausgedrückt i.d.R. als Mutationen pro Position• Abstand kann > 1 werden!
Berechnen des paarweisen Abstands
44
Stammbaumerstellung
Wie kommen wir von einer Distanzmatrix zu einem Stammbaum?
=> Algorithmus berechnet aus den Distanzen den "besten" Stammbaum.
Sequenzen selbst werden nicht mehr berücksichtigt.
45
UPGMA Unweighted Pair-Group Method with Arithmetric Means
Additive Methode. OTUs werden durch sequenzielles Clustern nach absteigender Ähnlichkeit gruppiert.
46
UPGMA Unweighted Pair-Group Method with Arithmetric Means
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A/B C D OTU A/B 0 11 19 OTU C 0 19OTU D 0
A/B C D OTU A/B 0 11 19 OTU C 0 19OTU D 0
3 A
3B
2.5
5.5C
3 A
3B
6
47
UPGMA
A/B/C D Sequenz A/B/C 0 19Sequenz D 0
A/B/C D Sequenz A/B/C 0 19Sequenz D 0
A
3B
2.5
5.5 C
D
4
9.5
3
• nimmt konstante Evolutionsraten an• Außengruppe wird "automatisch" bestimmt
48
UPGMA
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 11 19 OTU B 0 11 19OTU C 0 19OTU D 0
A B C D OTU A 0 6 11 19 OTU B 0 11 19OTU C 0 19OTU D 0
A
3B
2.5
5.5 C
D
4
9.5
3
Ausgangsmatrix
rekonstruierte Matrix
49
Neighbor-joining (NJ)
• Ähnlicher Algorithmus wie UPGMA • berücksichtigt unterschiedliche Evolutionsraten:
=> Astlängenberechnung• Sukzessives Gruppieren der OTUs• Minimierung der Astlängen
=> Stammbaum wird aufgelöst
=> keine konstante Evolutionsrate angenommen
50
Neighbor-joining (NJ)
1
2
3
4
5
6
7
8
X
a.1
3
4
5
6
72
8
X Y
b.
S = ( dji)/N; 1ijN
S = Summe aller Astlängen d = Distanzen zwischen allen OTUs N = Anzahl der OTUs
Ziel NJ => Minimierung von S
51
Neighbor-joining (NJ)
Beispiel:
A B C D
OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
A B C D
OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
10 1812 20
Abstand OTU A zu allen anderen ist aber kürzer als der von OTU B
=> Astlängen werden bei ungleichen Raten falsch berechnet. NJ korrigiert dies, indem es den Gesamtabstand des
betrachteten OTUs zu allen anderen Sequenzen berücksichtigt
B
A
D
C
52
Neighbor-joining (NJ)
Beispiel: A B C D OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
A B C D OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
1. Schritt: Berechnung der Summe der Abstände
SA = dAB + dAC + dAD
S
34 38 41 57
53
Neighbor-joining (NJ)
A B C D OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
A B C D OTU A 0 6 10 18OTU B 0 12 20 OTU C 0 19 OTU D 0
2. Schritt: Transformation der Matrix:
d'AB = dAB – (SA + SB)/2
= 6 – (34 + 38)/2 = –30 usw.
-30
S
34 38 41 57
54
Neighbor-joining (NJ)Transformation der Matrix:
d'AB = dAB – (SA + SB)/2
= 6 – (34 + 38)/2 = –30 usw.
A B C D S
OTU A 0 6 10 18 34OTU B -30 0 12 20 38 OTU C -27.5 -27.5 0 19 41OTU D -27.5 -29.5 -30 0 57
A B C D S
OTU A 0 6 10 18 34OTU B -30 0 12 20 38 OTU C -27.5 -27.5 0 19 41OTU D -27.5 -29.5 -30 0 57
=> Auswahl der Nachbarn (negativster Wert) hier: A+B oder C+D (führen zum gleichen Ergebnis)=> Werden durch Knotenpunkt verbunden
55
Neighbor-joining (NJ)3. Schritt: Berechnen des Abstands von A und B zu Knotenpunkt X:
dXA = dAB/2 + [SA/(N-2)* - SB/(N-2)]/2
<=> 6/2 + (17 - 19)/2 = 2
dXB = dAB/2 + [SB/(N-2) - SA/(N-2)]/2 <=>
<=> 6/2 + (19 - 17)/2 = 4
oder einfacher: dAB – dXA = 6 – 2 = 4
B
A
X4
2
C
D*N-2 = Anzahl der Knotenpunkte
A B C D S
OTU A 0 6 10 18 34OTU B -30 0 12 20 38 OTU C -27.5 -27.5 0 19 41OTU D -27.5 -29.5 -30 0 57
A B C D S
OTU A 0 6 10 18 34OTU B -30 0 12 20 38 OTU C -27.5 -27.5 0 19 41OTU D -27.5 -29.5 -30 0 57
56
Neighbor-joining (NJ)
Erstellen einer reduzierten Datenmatrix
dXC = (dAC – dAX + dBC – dBX)/2
<=> (10 – 2 + 12 –4)/2 = 8 usw.
X C D S
OTU X 0 8 16 24OTU C -17.5 0 19 27 OTU D -15.5 -12 0 35
X C D S
OTU X 0 8 16 24OTU C -17.5 0 19 27 OTU D -15.5 -12 0 35
usw...
57
Neighbor-joining (NJ)
A
B
2
4
C5.5
2.5
13.5
D
58
Neighbor-joining (NJ)
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
A B C D OTU A 0 6 10 18 OTU B 0 12 20OTU C 0 19OTU D 0
Ausgangsmatrix
rekonstruierte Matrix
A
B
2
4
C5.5
2.5
13.5
D
59
Neighbor-joining (NJ)Warum Transformation?
A B C D
OTU A 0 18 10 13 OTU B 0 22 25 OTU C 0 13 OTU D 0
A B C D
OTU A 0 18 10 13 OTU B 0 22 25 OTU C 0 13 OTU D 0
3
2
5
1
7
15
A
B
C
D
60
Neighbor-joining (NJ)UPGMA würde rekonstruieren:
A B C D
OTU A 0 18 10 13 OTU B 0 22 25 OTU C 0 13 OTU D 0
A B C D
OTU A 0 18 10 13 OTU B 0 22 25 OTU C 0 13 OTU D 0
5
1.5
6.5
4.33
10.83
5
A
C
D
B
=> "long branch attraction"
61
Neighbor-joining (NJ)NJ konstruiert?
A B C D S
OTU A 0 18 10 13 41OTU B -35 0 22 25 65 OTU C -33 -33 0 13 45OTU D -31.5 -31.5 -33.5 0 48
A B C D S
OTU A 0 18 10 13 41OTU B -35 0 22 25 65 OTU C -33 -33 0 13 45OTU D -31.5 -31.5 -33.5 0 48
3
2
5
1
7
15
A
B
C
D
62
A
3B
2.5
5.5 C
D
4
9.5
3
UPGMA
A
B
2
4
C5.5
2.5
13.5
D
Neighbor-joining
Matrix-orientierte Methoden
63
Charakter-orientierte Methoden
1. Maximum Parsimony (MP)2. Maximum Likelihood (ML)
• Arbeiten direkt mit dem Alignment• Extrahieren mehr Information
64
Charakter-orientierte Methoden
Charaktere• kontinuierliche oder diskontinuierliche Eigenschaften
• Nukleotide und Aminosäuren können als diskrete, diskontinuierliche Charaktere behandelt werden
• Der phylogenetische Stammbaum wird anhand des Musters der Änderungen der Charaktere berechnet
1,2,3,4.... = kontinuierliche Charaktere
A,T,G,C = diskontinuierliche Charaktere
65
Maximum Parsimony
• Annahme: Evolution ging stets den
kürzesten Weg• => Methode des "maximalen Geizes" • kürzester Stammbaum wird berechnet,
d.h., der die wenigsten evolutiven
Schritten benötigt.
66
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
Beispiel:
A
B
C
D
A
C
B
D
A
D
B
C
3 mögliche Stammbäume
((A,B)(C,D)) ((A,C)(B,D)) ((A,D)(B,C))
67
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
3 Positionen invariabel => nicht informativ
Welche Positionen sind informativ, bevorzugen also eine bestimmte Topologie?
68
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
6 Positionen sind variabel=> aber auch informativ?
69
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
3 Positionen sind zwar variabel, aber nicht informativ
70
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G * * *
Welche Positionen sind aber nun informativ?
=> nur 3 von 9 Positionen sind informativ, d.h., favorisieren eine best. Topologie.
10 11 - A - G C G C G *
=> Indels sind Charaktere!
71
Maximum Parsimony
Position 3:
((A,B),(C,D)) ((A,C),(B,D)) ((A,D),(B,C))
G
C
A
A
G
A
A
C
G
A
A
C
•• •
••
•A AAAAA
G
G
A
A
G
A
A
G
G
A
A
G
••
••
•G AAAAA
A
G
A
G
A
A
G
G
A
G
A
G•• ••
•A AAGAA
Position 5:
Position 9:
?
72
Maximum Parsimony
A
B
C
D
A
C
B
D
A
D
B
C
3 mögliche Stammbäume
10 Mutationen 15 Mutationen 14 Mutationen
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G * * *
73
Maximum Parsimony
Position Sequenz 1 2 3 4 5 6 7 8 9 A A A G A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
Aber: Ort der Mutation nicht (immer) eindeutig definiert => Parsimony kann keine Astlängen berechnen.
A
B
C
D
10 Mutationen
A
B
C
D
10 Mutationen
A
B
C
D
10 Mutationen
= = = .....
74
Proteinparsimony:
1. Modell (z.B. PAUP): Alle Substitutionen sind gleich wahrscheinlich (1 Schritt).
Beispiel Ile -> Trp Ile -> Met Ile -> Ala ...
2. Modell: liegt genetischen Code zugrunde, wobei "silent site mutations" ignoriert werden (PROTPARS-Modell in PHYLIP).
Beispiel: Ile -> Met: ATA/C/T -> ATG: ein Schritt Ile -> Ala: ATA/C/T -> GCN: zwei Schritte
Ile -> Trp: ATA/C/T -> TGG: drei Schritte
Maximum Parsimony
75
Maximum Parsimony
A
B C(1)Start: 3 bel. Taxa
(2a)
A
B D
C
A
BD C
A
B C
D(2b) (2c)
+ 4. Taxon (D) in jeder möglichen Position -> 3 Bäume
+ 5. Taxon (E) in jeder der fünf möglichen Positionen=> 15 Stammbäume etc.
E
E
EE
E
76
Maximum ParsimonyProblem: Anzahl der möglichen Stammbäume
Number
of OTUs
Number of
rooted trees
Number of
unrooted trees
2 1 1
3 3 1
4 15 3
5 105 15
6 954 105
7 10395 954
8 135135 10395
9 2027025 135135
10 34459425 2027025
=> bei > 10 Sequenzenausführliche Suche allerStammbäume de facto unmöglich
77
Maximum Parsimony
1. Lösung: "Branch and bound"-Methode verwirft Gruppen von
Bäumen, die nicht kürzer werden können als der bis dahin erhaltene kürzeste Stammbaum.
Man kann die maximale Stammbaumlänge (in Schritten) vorgeben.
Kann für Problemlösungen mit < ~ 20 Taxa verwendet werden.
78
Maximum Parsimony
2. Lösung: Heuristische Verfahren: "Random addition" "Branch Swapping": Nearest neighbor interchange (NNI) Subtree pruning and regrafting (SPR) Tree bisection and reconnection (TBR)
79
Maximum Parsimony
einfach; ohne konkretes Evolutionsmodell Errechnung ancestraler Positionen funktioniert gut mit konsistenen Datensätzen
Vorteile:
empfindlich gegen Homoplasien (Konvergenz) empfindlich gegen "Long Branch Attraction" Astlängen werden unterschätzt kein Evolutionsmodell möglich für die meisten molekularen Analysen nicht sehr gut geeignet
Nachteile:
80
Charakter-orientierte Methoden
1. Maximum Parsimony (MP)
2. Maximum Likelihood (ML)
81
Maximum Likelihood
L = P(data|tree)•Die "Likelihood" ist die Wahrscheinlichkeit
der beobachteten Daten (Sequenzen!), gegeben die Hypothese (Stammbaum).
•d.h, es wird der Stammbaum errechnet, der die beobachteten Daten (also die alignierten Sequenzen) am besten (unter der Annahme des Modells) erklärt.
82
Maximum Likelihood
Probability (P) = Wahrscheinlichkeit
Wahrscheinlichkeiten summieren sich stets auf 1 auf:Wie wahrscheinlich ist es, dass ich eine 6 würfele? Antwort: 1/6. Wie wahrscheinlich ist es, dass ich keine 6 würfele? Antwort 5/6. => 1/6 + 5/6 =1.
Maximum Likelihood (L) Wahrscheinlichkeit (P)
Für "Likelihood"-Werte summieren sich nicht auf 1 auf:=> Wie wahrscheinlich ist meine Hypothese unter dem gegebenen Randbedingungen?
83
Maximum Likelihood
Seq1 CGAGACSeq2 AGCGACSeq3 AGATTASeq4 GGATAG
1
2
3
4
Frage: Wie hoch ist die Wahrscheinlichkeit, daß der Stammbaum A für die Daten (Sequenzen) unter dem gegebenen Modell verantwortlich ist?
A
84
Maximum Likelihood
OTU 1 CGAGA COTU 2 AGCGA COTU 3 AGATT AOTU 4 GGATA A
j
ACGT
?
?
C C A A
ACGT 4 x 4 Möglichkeiten
Wurzel willkürlich!
Die Wahrscheinlichkeit für eine best. Position j ist die Summe der Einzelwahrscheinlichkeiten aller möglichen ancestralen Nukleotide unter dem gegebenen Modell.
85
ML – Beispiel (vereinfacht):
CCAA
Daten: Modell (nicht realistisch):
A T C G
A 1 0.1 0.1 0.1
T 1 0.1 0.1
C 1 0.1
G 1
OTU 1 OTU 2OTU 3OTU 4
86
ML - Beispiel:
C
C
A
A
Stammbaum A:
X YX,Y = A, T, G, oder C
ML: Summe der 4 x 4 Einzelwahrscheinlichkeiten
87
ML - Beispiel:
Stammbaum 1:
C
C
A
A
C T
C
C
A
A
C A
1 x 1 x 0.1 x 1 x 1 = 0.1 1 x 1 x 0.1 x 0.1 x 0.1 = 0.001
usw... Summe aus 16 möglichen Stammbäumen!
Stammbaum 2:
88
ML - Beispiel:
Stammbaum A:
C
C
A
A
Gesamt"wahrscheinlichkeit":
= 0.12427=> logL = -0.90563
C
A
C
A
Gesamt"wahrscheinlichkeit":
= 0.02302=> logL = -1.6379
Stammbaum B:
89
Wahrscheinlichkeit des Stammbaums A ist das Produkt aller Wahrscheinlichkeiten für jede Position. ML-Stammbaum = Stammbaum mit größter "Likelihood".
Maximum Likelihood
1 CGAGAC2 AGCGAC3 AGATTA4 GGATAG i . . . . z
1
2
3
4
A
90
Maximum Likelihood
Austauschparameter werden aus Evolutionsmodell berechnet
Typisches Evolutionsmodell:
•Substitationswahrscheinlichkeit unabhängig von der Historie der Position (Markov-Modell).
•Eine Substitutationswahrscheinlichkeit im Stammbaum unabhängig von Zeit oder Position (homogener Markov-Prozeß).
•Ratenreversibilität: P(A -> T) = P(T -> A).
91
Maximum Likelihood - Vorteile
Mathematisch gut definiert Funktioniert gut in
Simulationsexperimenten Erlaubt explizite Verbindung von
Evolutionsmodell und Daten (Sequenzen) "Realistische" Annahmen zur Evolution Verschiedene Modelle und Stammbäume
lassen sich testen
92
Maximum Likelihood - Nachteile
Maximum likelihood ist nur konsistent (ergibt einen "wahren" Stammbaum) wenn die Evolution nach den gegebenen Modell ablief: Wie gut stimmt mein Modell mit den Daten überein?
Computertechnisch nicht zu lösen wenn zu viele Taxa oder Parameter berücksichtigt werden müssen.
93
Maximum Likelihood Bei vielen Taxa sind
computertechnisch nicht alle möglichen Stammbäume berechenbar
Lösung: "Intelligente Algorithmen" - Quartet puzzling - Bayessche Methode + MCMCMC
94
Statistische Auswertung
ML-Methoden Parametrisches Bootstrapping (Datensimulation) Nicht-parametrisches
Bootstrapping=> häufigste Methode
95
Bootstrapping
Position Sequence 1 2 3 4 5 6 7 8 9 A A A A A G T G C A B A G C C G T G C G C A G A T A T C C A D A G A G A T C C G
Orginalsequenzen Position Sequence 1 2 2 4 5 5 7 8 8 A A A A A G G G C C B A G G C G G C C C C A G G T A A C C C D A G G G A A C C C
Pseudosample 1
z.B. 100 Wiederholungen Position Sequence 1 1 1 4 4 6 7 7 7 A A A A A A T G G G B A A A C C T G G G C A A A T T T C C C D A A A G G T C C C
Pseudosample 2
96
Bootstrapping
123456789 Freq-----------------.**...... 100.00...**.... 100.00.....**.. 100.00...****.. 100.00...****** 95.50.......** 84.33...****.* 11.83...*****. 3.83.*******. 2.50.**....*. 1.00.**.....* 1.00
Majority-rule consensus tree
Taxon 1
Taxon 3
Taxon 8
Taxon 9
Taxon 4
Taxon 6
Taxon 7
100
96
84
100
100
100
Taxon 2
Taxon 5