Fernstudium Molekulare Phylogenie

1

Fernstudium"Molekulare Phylogenie"

Bernhard LiebMichael Schaffeld

Institut für ZoologieUniversitä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

• Datenbanken

• Sequenzalignment

• Stammbaumerstellung

• Statistische Auswertung

4

Warum Phylogenie?

⇒Weshalb ist das Verständnis von phylogenetischen Zusammenhängen wichtig?

• Organismische Evolution (Systematik)

• Evolution von Proteinfamilien (Funktion)

• Medizin (Epidemiologie)

• Forensik (CSI Miami)

=> Stammbäume

5

Voraussetzungen der

Wieso können Phylogenien aus den heute existierenden Daten abgeleitet werden?

Phylogenie

6

AAGACTT

TAGCCCT AGCACTT

AAGGCCT AGGACTT

AGCGCTTAGCACAATAGACTTTAGCCCAAGGGCAT heute

AGGGCAT

A B C D EOTU

TAGCCCT AGCACTT

AAGGCCT AGGACTT

AGCGCTTAGCACAATAGACTTTAGCCCAAGGGCAT

AGGGCAT

Evolution vollzieht sich durchVeränderungen

7

Verwandte Spezies stammen von einem gemeinsamen Vorfahren ab.

Vorfahre

Nachkomme 1 Nachkomme 2

Gemeinsame Vorfahren

© Dan Graur

8

Vorfahre

Einige Organismen haben einen

Vorfahren, der erst vor kurzem gelebt

hat.

(~5 MYA)

© Dan Graur

9

Vorfahre

© Dan Graur

(~100 MYA)

Andere gemeinsame Vorfahren haben früher gelebt.

10

Vorfahre

© Dan Graur

(1.500 MYA)

Aber: Alle Organismen haben einen gemeinsamen Vorfahren!

11

AAGACTT

TAGCCCT

AAGGCCT TGGACTT

AGCGCTTAGCACAATAGACTTTAGCCCAAGGGCAT

heute

AGGGCAT

Hierarchie und Stammbaum

A B C D E

AGCACTT

Die Entstehung der Spezies erfolgte durch hierarchische Auftrennung, die durch einen Stammbaum darstellbar ist.

12

(1.500 MYA)

(100 MYA)

(5 MYA)

© Dan Graur

13

Ein korrekter Stammbaum

AGCGCTTAGCACAATAGACTTTAGCCCAAGGGCAT heute

A B C D E

14

Rekonstruktion

AGCGCTTAGCACAATAGACTTTAGCCCAAGGGCAT Daten

A B C D E

Rek

onst

rukt

ion

In Merkmalen (Morphologie, Sequenzen) sind dieInformationen über die Vergangenheit gespeichert

15

„Das große Ziel“

Aus den Daten (Sequenzen u.a.) einen Stammbaum erstellen,

der die tatsächlichenhistorischen

Verwandtschaftsverhältnisse widerspiegelt.

16

Warum molekulare Phylogenie?

Rekonstruktion von Verwandtschaftsverhältnissen

A. morphologische Daten (Fossilien, Merkmale, Ontogenie …)B. molekulare Daten (DNA- u. AS-Sequenzen, Gene …)

Die Methoden der molekularen Evolution erlauben die Extraktion der in der DNA bzw. den Proteinen gespeicherten Informationen.

Vorteil der Sequenzdaten:

- leichte Zugänglichkeit- grosse Datenmenge- können aber dennoch zu falschen Ergebnissen führen!

17

Molekulare PhylogenieVorgehensweise zur Stammbaumerstellung:

A. Evolution der Proteine Wo liegt der Ursprung eines Proteins oder einer Proteinfamilie?� Auswahl ähnlicher Sequenzen aus Datenbanken� Sequenzalignment� Molekularphylogenetische Analyse� Statistische Überprüfung

B. Evolution der Organsimen (Tree of Life)Verwandschaft bestimmter Taxa?� Auswahl geeigneter Sequenzen� Sequenzierung (Datenbanken, Klonierung, PCR)� Sequenzalignment usw. (wie oben)

18

Datenbanken

• NCBI – GenBank• DDBJ - DNA• EMBL-EBI• SWISS-PROT• PIR• UniProt• pdb

19

Datenbanksuche

BLAST (Basic Local Alignment Search Tool)=> vergleicht zwei Sequenzen miteinander

BLASTN: Vergleicht eine Nukleinsäuresequenz mitNukleinsäuredatenbank

=> nahe verwandte SequenzenBLASTP: Vergleicht eine Aminosäuresequenz mit

Proteindatenbank.=> entfernt verwandte Sequenzen

z.B. Ausgangspunkt: eigene ermittelte Sequenz (Query)

20

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 6 Leseraster einer Nukleinsäuresequenz mit den Translationsprodukten aller 6 Leseraster einer Nukleinsäuredatenbank.

=> z.B. entfernte Verwandtschaft unbekannte DNA-Sequenzen

21

BLAST(Basic Local Alignment Search Tool)

PRAXIS 1

22

Multiples Sequenz-Alignments

Gegeben:

Gesucht:

SeqA N A F L SSeqB N A F SSeqC N A K Y L SSeqD N A Y L S

SeqA N A - F L SSeqB N A - F - SSeqC N A K Y L SSeqD N A - Y L S

Indel:

Insertion/Deletion

23

ABCD

Alle Sequenzen werden paarweisemiteinander verglichen

CLUSTALX

-D

0.77-C

0.820.45-B

0.270.890.75-A

DCBA

Berechnung der Distanzen

guide tree

A

D

CB

24

AD

CB

Lücken = "gaps"

Alignment innerhalb der Cluster

B

C

A

D

CLUSTALX

Ähnliche Sequenzen werden zu einem Clustergruppiert

25

BC

AD

ADBC

Sukzessives globales Alignment

neue Lücken = "gaps"

CLUSTALX

alte Lücken = "gaps"

AD

CB

26

Alignment ParameterPRAXIS 2

27

Schwestergruppen

Was ist ein Stammbaum?

� Darstellung der Verwandtschaftsverhältnisse

ABC

A – F auch "operational taxonomic units" (OTUs)

DEF

AB

CD

EF

t t

Taxon/Taxa

28

Phylogenetische Grundbegriffe

A B C D E A B C D E

Dichotomie Polytomie

Ast(branch)

Knotenpunkt(node)

Wurzel(root)

Innengruppe(ingroup)

29

Mono-, Para- und Polyphylie

Monophyletische Taxa:

Alle Nachkommen einer gemeinsamen Stammform

Polyphyletische Taxa:

Keine gemeinsame Stammform (unterschiedliche Vorfahren)

Paraphyletische Taxa:

Nicht alle Nachkommen einer gemeinsamen Stammform

A B C D E F

30

Paraphylumaufgrund von homologen

(ursprünglichen) MerkmalenVögel

"Reptilien"

Schildkröten Krokodile

Eidechsen +

Schlangen

Phylogenetische Grundbegriffe

aber nicht alle Nachkommen werden erfasst

31

"Geier"

Neuwelt-Geier Raubvögel

Polyphylie=> verschiedenen Ursprungs

aufgrund von Homoplasien (Konvergenzen)

Altwelt-Geier

Storchen-vögel

Phylogenetische Grundbegriffe

32

Cladogramm und Phylogramm

B

A

C

D

E

F

Änderungen

A

BC

D

E

F

Cladogramm Phylogramm

A

B

C

D

E

F

Änderungen & Zeit

metrisch ultrametrisch

33

StammbaumOhne Außengruppe: Mit Außengruppe:

Evolutionsrichtung

Neunauge

Hai

Goldfisch

Flösselhecht

Zebrafisch

Forelle

Lungenfisch

Molch

Ochsenfrosch

Krallenfrosch

Mensch

Maus

Stahlen-flosser

Land-wirbeltiere

Flösselhecht

Goldfisch

Neunauge

Hai

Zebrafisch

Lungenfisch

Maus

Mensch

ForelleMolch

Ochsen-frosch

Krallenfrosch

Evolutionsrichtung?

34

Vorgehensweise

Stammbaumberechnung

Multiples Sequenz Alignment

Auswahl der Methode

Evolutionsmodell/Algorithmus

Ergebnisüberprüfung (output)

Sequenzen (Input)

35

Stammbaumerstellung

1. Distanz-orientierte Methoden• UPGMA (Unweighted Pair-Group Method with

Arithmetric Means)• Neighbor-joining• Minimal Evolution

=> Sequenzen werden in Distanzmatrix konvertiert

2. Charakter-orientierte Methoden• Parsimony• Maximum Likelihood

=> jede Position wird als informative Einheit betrachtet

Stammbaumberechnung

Multiples Alignment

Auswahl der Methode

Evolutionsmodell/Algorithmus

Ergebnisüberprüfung

Sequenzen

36

Distanz-orientierte Methoden

Zwei Schritte:

1.Berechnen der paarweisen Abstände zwischen den Sequenzen

2. Erstellen eines Stammbaums anhand dieser Abstandsdaten

Aus ‘jedem‘ Datensatz kann eine Distanzmatrix erstellt werden

Stammbaumberechnung

Multiples Alignment

Auswahl der Methode

Evolutionsmodell/Algorithmus

Ergebnisüberprüfung

Sequenzen

37

1 2 3 4 5Sequenz 1 0.00 Sequenz 2 Sequenz 3 Sequenz 4 Sequenz 5

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

Berechnung einer DistanzmatrixSequenz 1 TATAAGCATGACTAGTAAGCSequenz 2 TATTAGCATGACTGGTAACCSequenz 3 TATTGGCATGACTAGCAGGC Sequenz 4 TGTTGCCACGATTAGCTACC Sequenz 5 CGTAGCTATGACCAACGGGC

Distanz = durchschnittliche Änderung pro Position

0.15

hier: 3 von 20 Positionen verändert

38

Korrektur der Distanzen

beobachteter Abstand

t

%tatsächlicher Abstand= Anzahl der Mutationen

Korrektur

39

Korrektur der Distanzen

Frage: Wie korrigieren wir?

� Wir wollen die tatsächliche Anzahl der evolutiven Ereignisse rekonstruieren.

� Wir brauchen also ein Evolutionsmodell, welches Rückmutationen und die Austauschwahrscheinlichkeiten etc. berücksichtigt.

40

Korrekturmodelle (Evolutionsmodell)

Modelle

für Proteinevolution sind meist

empirisch

41

Transmembran-Proteine

Evolutionsmodelle

Globuläre Proteine

K

R N

K

42

Stammbaumberechnung

Alignment

Distanzmatrix

Evolutionsmodell z.B. JTT; PAM; BLOSUM ...

Stammbaum

Algorithmusz.B UPGMA; NJ…

Protdist

neighbor

UPGMA-TreeNJ-Tree

DatenClustalX

43

Stammbaumberechnung

PRAXIS 3

output

Distanzmatrix und Newick

44

12Ente 0.000000 0.027538 0.131789 0.189059 0.254695 0.305737 0.366709 0.437865 0.342427 0.680479 0.664999 0.809168Gans 0.027538 0.000000 0.133790 0.182028 0.254414 0.305450 0.366525 0.423258 0.355341 0.689492 0.689962 0.811354Huhn 0.131789 0.133790 0.000000 0.214235 0.279128 0.343764 0.395035 0.450144 0.371808 0.687246 0.709803 0.789037Taube 0.189059 0.182028 0.214235 0.000000 0.376477 0.426717 0.437753 0.430975 0.385513 0.685211 0.706543 0.853846Krokodil 0.254695 0.254414 0.279128 0.376477 0.000000 0.127816 0.366086 0.462063 0.403623 0.715770 0.751314 0.759451Alligator 0.305737 0.305450 0.343764 0.426717 0.127816 0.000000 0.437020 0.495107 0.437141 0.741703 0.755032 0.781956Schildkrot 0.366709 0.366525 0.395035 0.437753 0.366086 0.437020 0.000000 0.441266 0.407947 0.716215 0.761426 0.758189Wal 0.437865 0.423258 0.450144 0.430975 0.462063 0.495107 0.441266 0.000000 0.159417 0.764462 0.688008 0.809193Mensch 0.342427 0.355341 0.371808 0.385513 0.403623 0.437141 0.407947 0.159417 0.000000 0.710450 0.635149 0.705371Zebrafisch 0.680479 0.689492 0.687246 0.685211 0.715770 0.741703 0.716215 0.764462 0.710450 0.000000 0.367123 1.012071Lachs 0.664999 0.689962 0.709803 0.706543 0.751314 0.755032 0.761426 0.688008 0.635149 0.367123 0.000000 0.907433Salamander 0.809168 0.811354 0.789037 0.853846 0.759451 0.781956 0.758189 0.809193 0.705371 1.012071 0.907433 0.000000

(Gans:0.01404,(Taube:0.13426,(Huhn:0.07823,((Krokodil:0.04150,Alligator:0.08631):0.10799,(Schildkrot:0.20098,((Wal:0.11272,Mensch:0.04670):0.11592,((Zebrafisch:0.19023,Lachs:0.17689):0.25250,Salamander:0.52369):0.05289):0.02137):0.03693):0.06954):0.00251):0.03752,Ente:0.01350);

45

Ente

Gans

Taube

Huhn

Krokodil

Alligator

Schildkrot

Wal

Mensch

Salamander

Zebrafisch

Lachs100

100

100

65

52

79

95

36

95

?‚Long branch attraction?‘

Der Baum

46

UPGMA - NJ

A

B

C

D

E

F

B

A

C

D

E

FUPGMA

Unweighted Pair-Group Method with Arithmetric Means

NJNeighbor Joining

•Aussengruppe festgelegt

•konstante Evolutionsrate

•Aussengruppe wählbar

•unterschiedliche Evolutionsraten

47

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 19OTU C 0 19OTU D 0

3 A

3B

6

A/B

C

5.5

5.5

2.5

=3

d AD + d BD2

=5,5

d AC + d BC2

UPGMA Unweighted Pair-Group Method with Arithmetric Means

48

A/B/C D Sequenz A/B/C 0 19Sequenz D 0

A

3 B

2.5

5.5 C

D

4

9.5

3

• nimmt konstante Evolutionsraten an• Außengruppe wird „automatisch“ bestimmt

UPGMA Unweighted Pair-Group Method with Arithmetric Means

49

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

3 B

2.5

5.5 C

D

4

9.5

3

Ausgangsmatrix

rekonstruierte Matrix

UPGMA setzt absolute molekulare Uhr voraus, aber in Realität müssen Evolutionsraten berücksichtigt werden

UPGMA Unweighted Pair-Group Method with Arithmetric Means

50

Problem UPGMA

A B C D

OTU A 0 18(21,7) 10 13OTU B 0 22(21,7) 25(21,7)OTU C 0 13OTU D 0

3

2

5

1

7

15

A

B

C

D

5

1.5

6.5

4.33

10.83

5

A

C

D

B

51

Neighbor-joining NJ

Ziel NJ => Minimierung der Summe aller Astlängen

B C

D

E

A

bc

de

a

S0 = (∑ dji)/N-1i≤j

S0=Summe aller Astlängend =Distanzen zwischen allen OTUsN =Anzahl der OTUs

S0=a+b+c+d+e

„Star-tree“

B C

D

E

A

bc

d

e

af

„modified Star-tree“

Paare werden kombiniert

A B C D E

OTU A 0 22 39 39 41OTU B 0 41 41 43OTU C 0 18 20OTU D 10OTU E 0

SAB=67,7

S0=78,5

SBC=81SCD=76

SDE=70

Aber: Welche Paare werden kombiniert?

52

Grouping -> BaumlängenAstlängen -> FMNeues taxon -> neue Matrix

B

A

b

a

C

D

E

c

d

e

f

„modified Star-tree“

„Star tree“ -> BaumlängeGrouping -> BaumlängenAstlängen -> FM

Neues taxon (AB) -> neue Matrix

Grouping -> BaumlängenAstlängen -> FMNeues taxon -> neue Matrix

Neues taxon (XY) -> neue Matrix

Neighbor-joining NJ

C

D

E

c

d

e

f

53

B C

D

E

A

b=12c

d=4

e=6

a=10f=20

„final tree“

g=5

c=9

A B C D EOTU A 0 22 39 39 41OTU B 0 41 41 43OTU C 0 18 20OTU D 0 10OTU E 0

Neighbor-joining NJ

54

• Ähnlicher Algorithmus wie UPGMA• Sukzessives Gruppieren der Taxa ohne Verlust eines

Astlängenunterschiedes• Minimierung der Gesamt-Astlängen des Baums

=> Stammbaum wird aufgelöst=> berücksichtigt unterschiedliche Evolutionsraten

(Rekonstruierte Distanzmatrix=Ausgangsmatrix)

Neighbor-joining NJ

55

Was bisher geschah...

Alignment

Distanzmatrix

Evolutionsmodell JTT, PAM, BLOSUM ...

Stammbaum

Algorithmus

z.B UPGMA; NJ…

DatenClustalX, Dialign…

UPGMANJFM

LS ME

56

Statistische Auswertung

….oder….

Wie gut passt mein Stammbaum zu den Daten?

häufigste Methode ist „Bootstrapping“…

57

Ziehen MITZurücklegen

Bootstrapping

58

D

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

OrginalsequenzenPosition

Sequence 1 2 2 4 5 5 7 8 8A A A A A G G G C CB A G G C G G C C CC A G G T A A C C CD A G G G A A C C C

Pseudosample 1

z.B. 100 WiederholungenPosition

Sequence 1 1 1 4 4 6 7 7 7A A A A A A T G G GB A A A C C T G G GC A A A T T T C C CD A A A G G T C C C

Pseudosample 2

A

D

BC

A

B

C

…100 Stammbäume

Bootstrapping

59

123456789 Freq-----------------.**...... 100.00...**.... 100.00.....**.. 100.00...****.. 100.00...****** 96.00.......** 84.00...****.* 13.00...*****. 5.00.*******. 3.00.**....*. 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

Bootstrapping

60

Stammbaumberechnung

Protdist

ClustalX

UPGMANJ

neighbor

Alignment

Distanzmatrix

Daten

„Evolutionsmodell“

Seqboot x100

consense

100

100

1 NJ UPGMA

Bootstrapping

61

I ATAAII AAAAIII AAAA

I ATAAII AAAAIII AAAA

I AAAAII AAAAIII AAAA

IIIIII

IIIIII

IIIIII

99x

1x

62

Bootstrapping

63

Stammbaumerstellung

1. Matrix-orientierte Methoden

2. Charakter-orientierte Methoden

64

Charakter-orientierte Methoden

1. Maximum Parsimony (MP)2. Maximum Likelihood (ML)

• Arbeiten direkt mit dem Alignment indem Nukleotide

bzw. Aminosäuren als diskrete Charaktere behandelt

werden

• Der phylogenetische Stammbaum wird anhand des

Musters der Änderungen der Charaktere berechnet

• Extrahieren mehr Information als Matrix-orientierte

Methoden

65

Maximum Parsimony„Maximaler Geiz"

Annahme:• Evolution ging stets den kürzesten Weg und somit wird der Stammbaum berechnet, der die wenigsten evolutiven Schritte benötigt.

Methode:• Alle Möglichkeiten analysieren

66

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 9A 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

Maximum Parsimony

67

Maximum ParsimonyPosition

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

2 Mutationen

=G

C

A

A

AG2 Mutationen

C

C

A

A

AG

Sequenz A

Sequenz B

Sequenz C

Sequenz D

Sequenz A

Sequenz B

Sequenz C

Sequenz D

Ort der Mutation nicht immer eindeutig definiert => Parsimony kann keine Astlängen berechnen.

68

Position Sequenz 1 2 3 4 5 6 7 8 9A 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

Gesamt-Alignment:

A

B

C

D10 Mutationen

A

B

C

D10 Mutationen

A

B

C

D10 Mutationen

= = = .....

Maximum Parsimony

69

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 SchrittIle -> Ala: ATA/C/T -> GCN: zwei Schritte Ile -> Trp: ATA/C/T -> TGG: drei Schritte

Maximum Parsimony

70

� gesamter Datensatz

Vorteile:

� empfindlich gegenüber stark unter-schiedlichen Evolutionsraten

� Evolutionsmodelle eingeschränkt möglich� hoher Rechenaufwand bei >20 Taxa

Nachteile:

Maximum Parsimony

71

Stammbaumberechnung

Alignment

Evolutionsmodell „kürzester Weg“

MaximumParsimony

Stammbaum

Protpars

DatenClustalX

72

Stammbaumberechnung

PRAXIS 5

73

Maximum Likelihood

Wahrscheinlichkeit der beobachteten Daten im Lichte der

Hypothese

L = P(data|hypothesis)

74

Likelihood

Daten: KKZKZKKZZZ

• Ereignisse sind unabhängig

• Alle ‚Kopfwürfe‘ besitzen gleiche UNBEKANNTE Kopfwahrscheinlichkeit p

Hypothese

=> Likelihood L(D|H) = pp(1-p)p(1-p)pp(1-p)(1-p)(1-p)

Für jede vorgegebene Kopfwahrschein-lichkeit p ergibt sich eine bestimmte Likelihood

=> Plot der selben Daten (KKZKZKKZZZ) gegen verschiedene Werte von p (Hypothese)

=> Mit welcher Kopfwahrscheinlichkeit p bekomme ich am ehesten diese Daten?

L = P(Daten | Hypothese )

0,0 0,2 0,4 0,6 0,8 1,0[p]

Like

lihoo

d

75

Maximum LikelihoodL = P(data|hypothesis)

• Wahrscheinlichkeit die beobachteten Daten(Sequenzen!) unter der angenommenen Hypothese(Stammbaum/Evolutionsmodell) zu erhalten.

• d.h, es wird der Stammbaum errechnet, der die beobachteten Daten (also die alignierten Sequenzen) am besten (unter der Annahme des Modells) erklärt.

Evolutions-

modell

Ein Baum wird generiert und man prüft dann ob die gegebenen Daten den Baum generieren können

76

ML - Prinzip

X,Y = A, T, G, oder C

A T C G

A 1,0 0,1 0,2 0,4

T 1,0 0,3 0,6

C 1,0 0,1

G 1,0

Sequence 1 CGAGAASequence 2 AGCGAASequence 3 AGATTTSequence 4 GGATAT

1x1x1x0,1x0,1=0,01

Sequence 1 CGAGAASequence 2 AGCGAASequence 3 AGATTTSequence 4 GGATAT

CGAGAAAGCGAAAGATTTGGATAT

Likelihood einer vorgegebenen Topologie ist das Produkt aller

Wahrscheinlichkeiten jederPosition

Berechnen aller Möglichkeiten für eine Topologie und eine Position

77

ML - Beispiel:

Stammbaum A:

1

2

3

4

Gesamt"wahrscheinlichkeit":

= 0,12427=> logL = -0,90563

1

3

2

4

Gesamt"wahrscheinlichkeit":

= 0,02302=> logL = -1,6379

Stammbaum B:

78

Maximum Likelihood

� Der Wert für die eingesetzten Wahrscheinlichkeiten p entspricht den vorgegebenen Stammbäumen.

� Die Hypothese „alle Kopfwürfe besitzen die gleiche Wahrscheinlickeit“ entspricht dem Evolutionsmodell

79

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

80

� 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.

Maximum Likelihood Nachteile

81

Maximum Likelihood

� Bei vielen Taxa sind computertechnisch nicht alle möglichen Stammbäume berechenbar

� Lösung: "Intelligente Algorithmen"- Quartet puzzling- Bayessche Methode + MCMCMC

82

Maximum Parsimony

Exhaustive = Alle Stammbäume werden untersucht, der beste Stammbaum wird erhalten (garantiert).

Exhaustive search:Erschöpfung garantiert

83

Maximum Parsimony:Exhaustive Search

A

B C(1)Start: 3 beliebige Taxa

(2a)

A

B DC

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

"Branch addition“

84

Problem: Anzahl der möglichen Stammbäume

=> bei > ~10 Sequenzenausführliche Suche allerStammbäume de factounmöglich

Maximum Parsimony:Exhaustive Search

Number

of OTUs

Number of

rooted trees

Number of

unrooted trees

2 1 13 3 1

4 15 35 105 15

6 954 1057 10 395 9548 135 135 10 395

9 2 027 025 135 13510 34 459 425 2 027 025

85

Maximum Parsimony

1. Lösung "Branch and bound":• Stammbaum wird mit schneller Methode (z.B. NJ) berechnet, die Anzahl der notwendigen Schritte (L) wird berechnet.

• => verwirft Gruppen von Bäumen, die nicht kürzer werden können als L.

• Kann für Problemlösungen mit < ~ 20 Taxa verwendet werden.

86

MaximumParsimony

„branchand bound“

„abzweigen und beenden“

87

Maximum Parsimony2. Lösung:

Heuristische Verfahren:� „stepwise addition“ drei Taxa Baum – schrittweise

Addition auf allen nächsten Ebenen (großes Problem: lokale Maxima)

� „star decomposition“: „star tree“ schrittweiser Abbau von Taxa bzw. Zusammenführung und Evaluation (großes Problem: lokale Maxima)

Kombination mit anderen Algorithmen� „branch swapping“ (Zweige vertauschen):

Nearest neighbor interchange (NNI)Subtree pruning and regrafting (SPR)Tree bisection and reconnection (TBR)

88

Problem: Lokale Maxima „stepwise addition"

„star decomposition“

Maximum Parsimony

? !

„Bauminsel“

go go go !!!

No go !!! Back up!!!

Down? Don‘t go !

Lokales Maximum

91

Durch zwischenzeitliche Einführung einer veränderten MatrixWird man aus einem lokalen maximum herauskatapultiert…

Programme wie:NONA, TNT, PRAP…

Weitere „Parsimony“-Verfahren:

• Wagner (binäre Charaktere),• Dollo (gewichtet) und• Fitch (unordered multistate characters, DNA)

Parsimony Ratchet

92

ML, MP versus NJ und UPGMA

� Stammbaum vorgegeben� Analyse aller Möglichkeiten diesen Stammbaum zu

erhalten� MP: kürzester – ML: zutreffenster

ML, MP

NJ, UPGMA� Sukkzessive Rekonstruktion des Stammbaumes� NJ: „echte“ Evolutionsraten� UPGMA: „gemittelte“ Evolutionsraten

Vorgehensweise UPGMA und NJ

Sukzessives Hinzufügen neuer OTUs zum Stammbaum

93

A

B

CA

B

C

D

A

B

Vorgehensweise MP und ML

Maximum Parsimony

94

D

A

D

BC

A

B

C

…

Maximum Likelihood

Welcher Stammbaum erfordert die wenigsten

Mutationen, um den Datensatz zu erhalten?

Welcher Stammbaum liefert die höchste

Wahrscheinlichkeit den Datensatz zu erhalten?

Alle möglichen Stammbäume

95

Stammbaumberechnung

Protdist

ClustalX

MPMLUPGMANJ

neighbor

Alignment

Distanzmatrix

Daten

„Evolutionsmodelle“

protparsproML

96

Stammbaumberechnung

Protdist

ClustalX

MPML

MP

UPGMANJ

neighbor

Alignment

Distanzmatrix

„Evolutionsmodelle“

Seqboot x100

consense

100

100

1 NJ UPGMA

100

1ML

protparsproML

97

Was ‚können‘ oder ‚kennen wir !?

Alignment

Distanz matrix

Evolutions-modelle

Neigbor JoiningMax.Parsimony

Max. Likelihood UPGMA

CharakterMatrix

Stammbaum

98

☺ �Kritik,

AnregungenVorschläge

Verbesserungen…

…. oder was auch immer,bitte

anBernd

oder

Michael

lieb@uni-mainz.de

schaffeld@uni-mainz.de

Merke ☺

� Alles außer UPGMA ist radial � „rooting“

� Nur UPGMA gibt Außengruppe vor

� Alles außer MP zeigt Abstände

� MP � Cladogramm-Darstellung

� UPGMA, NJ, ML � Phylogramm-Darstellung

� Bootstrapping zeigt Info des Datensatzes

99

DATEN

alignment

ClustalX

Matrix

protdist

seqboot

100 aln

100 Matrizen

Matrix orientierte Methoden:

UPGMA / NJ

Tree

Evolutionsmodell:

JTT

Neighbor

(UPGMA / NJ)

Tree100 Trees

consense

bootstrap Tree

Bootstrap-

Werte

≥ 100 Trees

protpars

Evolutionsmodell:

parsimony (Geiz)

bootstrap Tree

Bootstrap-

Werte

Charakter orientierte Methoden:

MP

HbA.seq

HbA.phy

HbA_JTT.dst

HbA_UPGMA.tre (.out)

HbA_NJ.tre (.out)

HbA_seqboot.txt

HbA_seqboot_ protdist.txt

HbA_seqboot_ protdist_UPGMA.tre

HbA_seqboot_ protdist_NJ.tre

HbA_seqboot_ protdist_UPGMA_con.tre

HbA_seqboot_ protdist_NJ_con.tre

HbA_MP.tre (.out)sbmp.tre (.out)

HbA_seqboot_ MP_con.tre

Programm

File name

Datenform