Phylogenetik - ls11- · Kladogramm Phylogramm Ultrametrischer Baum (cladogram) (phylogram) (ultrametric tree) Alle Darstellungsformen zeigen die gleichen evolutionären Beziehungen

Prof. Dr. Sven Rahmann, Lehrstuhl 11Bioinformatik für Hochdurchsatztechnologien1 Prof. Dr. Sven Rahmann, Lehrstuhl 11Bioinformatik für Hochdurchsatztechnologien

Phylogenetik

Webseite zur Vorlesunghttp://bioinfo.wikidot.com/

SprechstundeMo 16-17 in OH14, R214Sven.Rahmann -at- tu-dortmund.de

VorlesungEinführung in die Angewandte BioinformatikProf. Dr. Sven Rahmann

http://bioinfo.wikidot.com/

Prof. Dr. Sven Rahmann, Lehrstuhl 11Bioinformatik für Hochdurchsatztechnologien2

Phylogenetik

Phylum = Stamm

Phylogenetik:befasst sich mit der Rekonstruktion von evolutionären Stammbäumen (= phylogenetische Bäume, Phylogenien)aus unterscheidbaren Merkmalen,heutzutage insbesondere aus DNA- / Proteinsequenzen,- sowohl von Spezies [species trees]- als auch von einzelnen Gen- / Protein-Familien [gene trees]

Tree Of LifeEin langfristiges Ziel: Stammbaum aller existierenden (und ausgestorbenen) ArtenTree Of Life Web Project: http://www.tolweb.org

http://www.tolweb.org/


Tree Of Life Web Project

Tree Of LifeEin langfristiges Ziel: Stammbaum aller existierenden (und ausgestorbenen) Arten

Tree Of Life Web Project:http://www.tolweb.org

Kontroverse über Verzweigungennahe der Wurzel

http://www.tolweb.org/


Grundlagen: GraphenEin Graph besteht aus:- Knoten (vertices V, nodes) und- Kanten (edges E), die zwischen den Knoten verlaufen.

Graphen können gerichtet oder ungerichtet sein(Kanten haben eine Richtung oder nicht).

Der Grad eines Knoten ist die Anzahl seiner Nachbarn.


Grundlagen: Ungewurzelte BäumeAls (ungewurzelter) Baum (unrooted tree) T = (V,E) wird ein Graph bezeichnet, der - zusammenhängend

(:= jeder Knoten wird von jedem anderen erreicht)- kreisfrei (:= es gibt nur einen Weg zwischen je zwei Knoten)ist.

In einem Baum unterscheidet man zwischen - inneren Knoten (inner nodes N), und- Blättern = äußeren Knoten (leaves L). Kante

Innerer Knoten

BlattEin Baum heißt Binärbaum,wenn alle inneren Knoten Grad 3 und Blätter Grad 1 haben.

Ungewurzelte binäre Bäume erfüllen|E| = 2|L| - 3 und |N| = |L| - 2.


Grundlagen: Gewurzelte BäumeEin ungewurzelter Baum kann gewurzelt werden,indem man eine Kante auswählt,in deren Mitte einen Knoten (die Wurzel) einfügt,und den Baum daran äufhängt.Die Wurzel hat Grad 2.Die Kanten werden von der Wurzel weg gerichtet.

In der Informatik wird die Wurzel eines Baums stets oben,die Blätter werden unten gezeichnet.Kanten verlaufen von oben nach unten.


Anzahl an Binärbäumen

3 Blätter: 1 ungewurzelter Baum

3 Blätter: 3 gewurzelte Bäumemit veschiedenen „Nachbarschaftsverhältnissen“

Ungewurzelte Binärbäume:3 Blätter: 1 Baum mit 3 Kanten4 Blätter: 3 verschiedene Bäume, je 5 Kanten5 Blätter: 3*5 = 15 Bäume, je 7 Kanten6 Blätter: 15*7 = 105 Bäume ...

A B

C

A BC

A CB

B CA

Gewurzelte Binärbäume: Man kann die Wurzel wie ein weiteres Blatt bei ungewurzelten Bäumen behandeln:

3 Blätter: 3 Bäume (siehe rechts, 5 Kanten)4 Blätter: 3*5 = 155 Blätter: 15*7 = 105

Beobachtung:Anzahl der binären Bäume wächst super-exponentiell in der Anzahl der Blätter n(schneller als cn für jede Konstante c)


Die drei Quartette

A C

B D

A B

C D

A B

D C

AB || CD AC || BD AD || BC


Aufgaben der Phylogenetik

Eine wichtige Aufgabe der Phylogenetik ist die Bestimmung der Verwandtschaftsverhältnisse zwischen Arten (Spezies)und der Ereignisse, die bei verschiedenen Arten seit der Speziation stattfanden.

Humans

Bonobos

Gorillas

Orangutans

Chimpanzees

MYA015-30

Klassische Sichtweise,basierend auf äußeren Merkmalen

MYA

Humans

Bonobos

Gorillas

014

Moderne Sichtweise,basierend auf DNA-Vergleich


Evolutionäre Verwandtschaft zwischen GenenErinnerung:Ein multiples Alignment ist nur zwischen Sequenzen sinnvoll,die global ähnlich sind, d.h. zwischen denen eine evolutionäre Verwandtschaft besteht.Diese wird durch einen phylogenetischen Baum ausgedrückt.

Beispiel: Serpin-Familie in der pfam-Datenbank

Dies ist ein Gen-Baum (gene tree),kein Arten-Baum (species tree):

An den Blättern (rechts) stehen einzelne Gene/Proteine/Sequenzen,keine Spezies.

Evolutionäre Ereignisse (innere Knoten):- Genduplikation- Speziation


Grad der Auflösung des Verzweigungsmusters

“Stern”-Baum, nicht aufgelöst Teilweise aufgelöst Vollständig aufgelöst

A A A

B

B B

C

C

C

E

E

E

D

D D

Polytomie, Multifurkation Bifurkation


Darstellungsarten in der Phylogenetik

Taxon A

Taxon B

Taxon C

Taxon D

11

1

6

3

5

Maß für den genetischenUnterschied(z.B. PAM-Einheiten)

Taxon A

Taxon B

Taxon C

Taxon D

Realzeit:gleicher Abstandaller Blätter zur Wurzel

Taxon A

Taxon B

Taxon C

Taxon D

Achse hat keine Bedeutung

Kladogramm Phylogramm Ultrametrischer Baum(cladogram) (phylogram) (ultrametric tree)

Alle Darstellungsformen zeigen die gleichen evolutionären Beziehungen(Baumtopologien, Verzweigungen, zwischen den Taxa).Taxa im selben Unterbaum bilden eine monophyletische Gruppe (clade).Darstellung durch geschachtelte Klammern: (((B,C),A),D)


Gewurzelt oder ungewurzelt?Das Problem der Molekularen Uhr

Phylogenetische Bäume werden (heutzutage vor allem) aus Biosequenzen gewonnen.Um über die Verwandtschafts-Verhältnisse zu entscheiden, benötigt man• Algorithmen zum Sequenzvergleich,• ein mathematisches Modell der Evolutionsprozesse auf Sequenzen.Hieraus lassen sich Distanzen zwischen Sequenzen berechnen.

Beispiel:139 beobachtete Unterschiede auf zwei Sequenzen der Länge 854.Wie vielen PAM-Einheiten entspricht das?Dies kann als einfaches Distanzmaß genommen werden.

Problem:Distanz ist nicht Realzeit!Evolutionsgeschwindigkeit variiert zeitlich, genspezifisch, Gattungs-spezifisch, ...Hieraus berechnete Bäume repräsentieren keine realen zeitlichen Abstände.Auch die Wurzel kann nicht zuverlässig positioniert werden.Man berechnet ungewurzelte Phylogramme.

In Ausnahmefällen treten diese Probleme nicht auf.Man sagt dann: Es gilt die Hypothese der „molekularen Uhr“.Man erhält einen gewurzelten ultrametrischen Baum.


Wurzeln eines ungewurzelten BaumsZwei Methoden:

(1) Mit Hilfe einer „outgroup“:Spezies die bekanntermaßen außerhalbder betrachteten Gruppe liegt(erfordert Vorwissen, relativ zuverlässig)

(2) Als Mittelpunktder am weitesten voneinanderentfernten Taxa(einfach, relativ unsicher)

A

B

C

D

10

2

3

5

2

outgroup

Größter Abstand:d (A,D) = 10 + 3 + 5 = 18Mittelpunkt bei 18 / 2 = 9


Ähnlichkeit ist nicht Verwandtschaft

A

B

C

D

11

1

6

3

5

C ist ähnlicher zu A (d = 3) als zu B (d = 7),aber C und B sind am nächsten verwandt.

Das heißt, C und B hatten einenspäteren gemeinsamen Vorfahren als C oder B mit A.

Ähnlichkeit / Distanz: beobachtbar, messbar

Verwandtschaft: historische Tatsache, kann heute nicht mehr beobachtet werden


Gründe für beobachtete Ähnlichkeiten

(1) Evolutionäre Verwandtschaft- gemeinsame Stamm-Merkmale (C)- gemeinsame abgeleitete Merkmale (G)

(2) parallele unabhängige Entwicklung von Merkmalen (Homoplasie)

CCGG

C

CGG

CG

G C

CGGT

parallele Mutation zu G

Rückmutationzu C

konvergente Mutationzu G

(3) geringe Evolutionsraten (hoher negativer selektiver Druck)


Phylogenetische Methoden

ALGORITHMUS BASIERT AUFClusteringverfahreneinem Optimalitätskriterium

ART

DER

DAT

EN

Mer

kmal

eD

ista

nzen

PARSIMONY (Sparsamkeit)

MAXIMUM LIKELIHOOD

UPGMA

NEIGHBOR-JOINING

MINIMUM EVOLUTION

LEAST SQUARES(kleinste Quadrate)

Es gibt unterschiedliche Methoden zum Erstellen phylogenetischer Bäume.Sie unterscheiden sich vor allem in zwei Dingen:- Auf welcher Art von Daten arbeiten sie (Distanze oder Merkmale)?- Welche Prinzipien liegen dem Algorithmus zu Grunde?


Distanz- vs. Merkmals-basierte MethodenMerkmals-basierte MethodenMerkmale sind Objekte, die einen von mehreren Zuständen annehmen können,z.B. jeweils eine Spalte in einem multiplen Alignment von DNA-Sequenzen.In jedem Taxon liegt eine bestimmte Merkmalsausprägung vor.Die Merkmale (Alignments) werden direkt zur Baumkonstruktion verwendet.

Taxa MerkmaleSpecies A ATGGCTATTCTTATAGTACGSpecies B ATCGCTAGTCTTATATTACASpecies C TTCACTAGACCTGTGGTCCASpecies D TTGACCAGACCTGTGGTCCGSpecies E TTGACCAGTTCTCTAGTTCG

Distanz-basierte MethodenDie Merkmale werden durch ein mathematisches Modellin paarweise Distanzen zwischen den Taxa umgerechnet.Nur die Distanz-Werte werden zur Baumkonstruktion verwendet.

A B C D E Species A ---- 0.20 0.50 0.45 0.40 Species B 0.23 ---- 0.40 0.55 0.50 Species C 0.87 0.59 ---- 0.15 0.40 Species D 0.73 1.12 0.17 ---- 0.25 Species E 0.59 0.89 0.61 0.31 ----

Zwei berechnete Distanzmatrizenrechts: Anteil Unterschiede, links: PAM-Schätzung / 100


Optimierungs- vs. Clustering-Methoden

Auf einem Optimalitätskriterium basierende MethodenEs wird ein Kriterium (eine Eigenschaft des zu berechnenden Baumes)definiert, das es zu optimieren gilt.Beispiele dafür:- Möglichst wenig Mutationen insgesamt im Baum- Möglichst wenig Diskrepanz zwischen gegebenen Distanzen und den Distanzen, die die Baumtopologie impliziertDie Aufgabe eines Algorithmus' ist nun, den Baum zu finden, der dieses Kriterium optimiert.Man muss wieder zwischen exakten Algorithmen und Heuristiken unterscheiden.Man kann die Ausgaben verschiedener Algorithmen miteinander vergleichen.

Clustering-MethodenEs werden Regeln definiert, nach denen Taxa zu (2er-)Bäumen zusammenzufassen sind,diese Bäume wiederum zu grösseren Bäumen, etc.Diese Methoden liefern immer einen einzigen Baum zurück;dieser kann nicht gegenüber Alternativen bewertet werden.Es gibt kein Optimalitätskriterium.

Achtung: Keines der Prinzipien verspricht den biologisch korrekten Baum!


Ausgewählte Methoden im ÜberblickALGORITHMUS BASIERT AUF

Clusteringverfahreneinem Optimalitätskriterium

ART

DER

DAT

EN

Mer

kmal

eD

ista

nzen


MAXIMUM LIKELIHOOD

UPGMA

NEIGHBOR-JOINING

MINIMUM EVOLUTION


Merkmalsbasierte Methoden:+ können auf molekulare oder auf morphologische Merkmale angewendet werden+ liefern Schätzungen der Ahnen-Sequenzen+ können die evolutionären Ereignisketten bestimmen– führen auf NP-schwere Probleme, auch Heuristiken sehr rechenaufwändig


Sehr einfaches Beispiel

A G G GA

??

?

?

Gegeben sind 5 Sequenzen: A, A, G, G, G

Zwei mögliche Baumtopologien:Welche Sequenzen stehen an den inneren Knoten?Bei Maximum-Likelihood spielt die Länge der Kanten dabei eine Rolle.

G G G AA

??

?

?


Parsimony (Sparsamkeit)

Gesucht / Ausgabe:Baumtopologie, Ahnen-Sequenzen in den inneren Knoten & Wurzel

Optimalitätskriterium:Der “sparsamste” Baum (“most parsimonious” tree) ist derjenige, derüber alle Kanten summiert am wenigsten Änderungen benötigt.

Vorteile• Einfach, intuitiv, motiviert durch Occam's Razor: „die einfachste, kürzeste Erklärung ist die beste“.

Nachteile:• Unterschätzt die wahre Anzahl von evolutionären Ereignissen bei entfernt verwandten Sequenzen (z.B. wegen Homoplasien)• liefert falsche Ergebnisse bei weit entfernten Sequenzen und stark unterschiedlichen Raten


Maximum Likelihood (maximale Plausibilität)

Gesucht / Ausgabe:Baumtopologie, Kantenlängen (in PAM-Einheiten o.ä.)

Optimalitätskriterium:Sind ein statistisches Evolutionsmodell und eine Baumtopologie & Kantenlängen gegeben,kann man die Wahrscheinlichkeit ausrechnen, dass genau die beobachteten Sequenzen zusammen auftreten.Gesucht ist der Baum & Kantenlängen, der diese Wahrscheinlichkeit maximiert.

Vorteile• Modellbasiert: Alle Annahmen werden explizit gemacht• Mehrfach- und Rücksubstitutionen sind im Modell berücksichtigt• Konsistente Schätzung evolutionärer Distanzen (Kantenlängen)

Nachteile:• Ergebnisse sehr modell-abhängig; falsches Modell führt zu beliebigen Ergebnissen• schwierig zu verstehen




ART

DER

DAT

EN

Mer

kmal

eD

ista

nzen


MAXIMUM LIKELIHOOD

UPGMA

NEIGHBOR-JOINING

MINIMUM EVOLUTIONLEAST SQUARES(kleinste Quadrate)

Programme fitch, kitsch

Distanzbasierte Optimierungs-Methoden:+ Distanzen können auf unterschiedliche Arten gewonnen werden+ flexibler Einsatz, auch außerhalb der Phylogenetik– Merkmale gehen nur indirekt ein; Ergebnisse von Distanzberechnung abhängig– Keine Aussage über Ahnen-Merkmale möglich


Minimum Evolution / Least Squares

Gesucht / Ausgabe:Baumtopologie, Kantenlängen

Optimalitätskriterium:Zu jeder Baumtopologie werden die Kantenlängen so bestimmt,dass die die gegebenen Distanzen von Blatt zu Blatt möglichst gut approximieren(im Sinne kleinster Quadrate). Optimal ist die Baumtopologie- mit kleinstem quadratischen Fehler (bei least squares)- mit kleinster Gesamtlänge (bei minimum evolution)

Vorteile• optimalitäts-basiert („Lösungen“ können vergleichend evaluiert werden)• schneller als merkmals-basierte Methoden

Nachteile:• langsamer als Clustering-Methoden NJ und UPGMA




ART

DER

DAT

EN

Mer

kmal

eD

ista

nzen


MAXIMUM LIKELIHOOD

UPGMA

NEIGHBOR-JOINING

MINIMUM EVOLUTION


Clustering-Methoden:+ Distanzen können auf unterschiedliche Arten gewonnen werden+ die schnellsten Baumrekonstruktionsmethoden+ universell einsetzbar (auch außerhalb der Phylogenetik)+ wenn die Distanzen es zulassen (ultrametrisch oder additiv sind), liefern die Algorithmen den richtigen Baum, sonst einen „gut passenden“




ART

DER

DAT

EN

Mer

kmal

eD

ista

nzen


MAXIMUM LIKELIHOOD

UPGMA

NEIGHBOR-JOINING

MINIMUM EVOLUTION


Clustering-Methoden:– liefern immer genau einen Baum, auch bei unsinnigen Distanz-Daten– verschiedene Lösungen können nicht anhand eines Kriteriums verglichen werden– Problem, dass eine unsinnige Lösung berechnet wurde, wird möglicherweise gar nicht erkannt


UPGMA: Unweighted Pair Group Method using Averaging


Verfahren:Solange mehr als ein Objekt vorhanden ist: Finde das Paar (x,y) von Objekten mit kleinster Distanz Erzetze sie durch ein einziges Objekt {x,y} Berechne Distanzen von {x,y} zu den anderen Objekten a, ..., mittels Durchschnittbildung zwischen d(x,a) und d(y,a)Der Baum ergibt sich aus der Hierarchie der zusammengefassten Objekte.

Vorteile• einfach zu verstehen, einfach durchzuführen• liefert korrektes Resultat bei ultrametrischen Distanzen, d.h. wenn es einen ultrametrischen Baum gibt, der die gegebenen Distanzen als Distanzen zwischen den Blätten aufweist, wird dieser (schnell) gefunden.

Nachteile:• Ergebnisse schlecht interpretierbar bei nicht ultrametrischen Eingabe-Distanzen


NJ: Neighbor Joining


Verfahren:Ähnlich wie bei UPGMA, aber die Wahl des zu aggregierenden Objektpaarsist sorgfältiger: Es werden alle Distanzen berücksichtigt, nicht nur die kleinste.Der Baum ergibt sich aus der Hierarchie der zusammengefassten Objekte.

Vorteile• liefert korrektes Resultat bei additiven Distanzen, d.h. wenn es einen (ungewurzelten) Baum gibt, der die gegebenen Distanzen als Distanzen zwischen den Blätten aufweist, wird dieser (schnell) gefunden.• erlaubt viele Varianten mit unterschiedlichen Eigenschaften

Nachteile:• Ergebnisse schlecht interpretierbar bei nicht additiven Eingabe-Distanzen


Welche Methode soll ich benutzen?Persönliche Empfehlung:

Distanzbasierte Methoden sind schnell und funktionieren meist gut,wenn das richtige Distanz-Modell verwendet wurde.Es empfiehlt sich, eine NJ-Variante zu benutzen, nicht UPGMA.

Probabilistische Methoden (ML, Bayes'sche Methoden)sind langsam (auch diese Problemformulierung ist NP-schwer),aber können – bei richtiger Wahl des Evolutionsmodells – bessere Ergebnisse liefern.Sie berechnen außerdem Alternativen und relative Konfidenzwerte.

Parsimony-Methoden unterschätzen den wahren evolutionären Abstand,denn sie suchen nach der sparsamsten Erklärung für Unterschiede.Nur in Ordnung bei sehr nah verwandten Sequenzen.Man bekommt keine Zeitschätzungen.Parsimony ist NP-schwer und benötigt viel Zeit für exakte Lösungen.


Software-Sammlung PhylogenetikUmfangreiche Sammlung phylogenetischer Software:http://evolution.genetics.washington.edu/phylip/software.html

Phylip:das am häufigsten benutzte Paket zum Erstellen von Phylogenien,enthält zahlreiche Einzelprogramme für verschiedene AufgabenProjekt-Homepage: http://evolution.genetics.washington.edu/phylip.html Web-Interface zu einer Teilmenge von Phylip + mehr: http://mobyle.pasteur.fr

http://evolution.genetics.washington.edu/phylip/software.html

http://evolution.genetics.washington.edu/phylip.html

http://mobyle.pasteur.fr/


Ende


Vertiefungsthemen

• Details zu den einzelnen Algorithmen• Distanzberechnung im Jukes-Cantor und Kimura-Modell• Robustheit geschätzter Bäume: Bootstrap

Documents

Phylogenetik - ls11- · Kladogramm Phylogramm Ultrametrischer Baum (cladogram) (phylogram) (ultrametric tree) Alle Darstellungsformen zeigen die gleichen evolutionären Beziehungen