Embed Size (px)
Citation preview
Evolutionary Treesand
Perfect Phylogeny
Zentrum für Bioinformatikder Universität des Saarlandes
WS 2001/2002
Evolutionary Trees
Nach der vorherrschende Meinung über die Evolution des Lebens sind alle Lebensformen aufunserem Planeten aus einem „primitiven“ gemeinsamen Vorfahren hervorgegangen. Ferner glaubt man, dass sich neue Spezies durch Aufsplittung einer Population in zwei oder mehrereneue Populationen (Spezies) gebildet haben. Es kann zwar nicht ausgeschlossen werden, dass sich neue Spezies durch die „Verschmelzung“ von zwei „älteren“ Spezies gebildet haben, jedoch ist die Wahrscheinlichkeit solcher Evolutionsereignisse sehr viel kleiner als die Wahrscheinlich-keit von Aufsplittungen.
In erster Näherung kann die Geschichte des Lebens (die Evolution) durch einen gerichteten Baum beschrieben und dargestellt werden. Die noch lebenden Spezies werden durch die Blätter des Baumes repräsentiert. Die Knoten des Baumes repräsentieren die ausgestorbenen„gemeinsamen“ Vorfahren der noch lebenden, in den Blättern gespeicherten Spezies.
Evolutionary Trees
Es existieren eine Reihe von Theorien aus dem Gebietder biologischen Systematik (Klassifikation) und derEvolutionsbiologie, nach welchen Kriterien und wieEvolutionsbäume (phylogenetische Bäume) konstruiertwerden sollten.
Als Folge der intensiven Diskussionen über diese Thematik existieren heute viele unterschiedliche Typen von phylogenetischen Bäumen.
Wir stellen im folgenden einige Arten von Bäumenvor, die aus der Sicht der mathematischen und der algorithmischen Theorie interessant sind. Über diebiologischen Relevanz der verschiedenen Klassifi-kationen wird auch in Zukunft noch heftig diskutiertwerden.
Ultrametric Trees
Definition:
Sei D eine symmetrische n x n Matrix von reellen Zahlen.
05883
50885
88038
88308
35880
a b c d e
abcde
Ein ultrametrischer Baum T ist ein Baummit den folgenden Eigenschaften:
(1) T hat n Blätter, jedes dieser Blätter ist mit einer Zeile aus D beschriftet.
a
b
e
dc
(2) Jeder interne Knoten von T ist mit einem Wert von D beschriftet und hat mindestens 2 Kinder.
35
8
3
(3) Auf jedem Pfad von einem Blatt zur Wurzel wachsen die Werte in den Knoten.
(4) Für jedes Paar (i,j) von Blättern gilt: Der kleinste gemeinsame Vorfahr von i und j im Baum T ist mit dem Wert D(i,j) der Matrix beschriftet.
Definition:
Ein min-ultrametrischer Baum hat mit Ausnahme von Eigenschaft (3) die gleichen Eigenschaftenwie ein ultrametrischer Baum. Eigenschaft (3) wird ersetzt durch die Forderung, dass die Werteauf allen Pfaden von Blättern zur Wurzel kleiner werden.
Ultrametric Trees
Man beachte, dass nicht jede Matrix einen (min-)ultrametrischen Baum besitzt.
05883
50885
88038
88308
35880
a b c d e
abcde a
b
e
dc3
5
8
3
Ein ultra-metrischer Baum hat höchstens n-1 interne Knoten. Besitzt die Matrix D also mehr als n-1verschiedene Einträge (Werte), so kann es zu D keinen ultrametrischen Baum geben.
Welche Art von evolutionären Daten beschreibt ein ultrametrischer Baum?
Die internen Knoten repräsentieren Aufspaltungen einer Spezies in zwei oder mehrere neueSpezies. Der kleinste gemeinsame Vorfahr zweier in den Blättern gespeicherter Spezies i und j ist mit einem Wert D(i,j) beschriftet. Dieser Wert gibt an, wie lange sich die beiden Spezies i und j schon divergent entwickelt haben (time since divergence).
Ultrametric Trees
Für jedes Tripel i, j, k betrachten wir den Teilbaum von T, der durch die drei Blätter i, j, k und ihre gemeinsamen Vorfahren definiert wird.
Definition:Eine symmetrische Matrix D von reellen Zahlen definiert genau dann eine ultrametrische Distanz,wenn für jedes Tripel von Indizes i, j ,k gilt: Das Maximum der drei Zahlen (Abstände) D(i,j), D(j,k), D(k,i) ist nicht eindeutig, d.h., mindestens zwei der Distanzen haben den gleichen Wert.
Satz:
Eine symmetrische Matrix D besitzt genau dann einen ultrametrischen Baum, wenn D eine ultra-metrische Distanz definiert (man sagt auch, dass D eine ultrametrische Matrix ist).
Beweis:
„=>“: Wir nehmen an, dass D einen ultrametrischen Baum T besitzt.
Die Wurzel dieses Teilbaums ist mit dem nicht eindeutigen Maximumder drei Werte D(i,j), D(i,k) und D(j,k) beschriftet.
„<=„: Wir nehmen an, dass D eine ultrametrische Matrix ist und zeigen nun konstruktiv, dassD einen ultrametrischen Baum besitzt. Wir betrachten das Blatt i dieses Baumes und nehmen an, dass in der i-ten Zeile von D genau d verschiedene Werte eingetragen sind. Der Pfad von izur Wurzel von T muß genau d innere Knoten besitzen, wobei jeder dieser Knoten mit einem der d Werte (in aufsteigender Folge) beschriftet ist. Ferner muß jedes Blatt j, das einen AbstandD(i,j) zu i besitzt, in dem entsprechenden Teilbaum des inneren Knoten mit diesem Wert auf-treten.
Ultrametric Trees
a b c d e f g h
abcdefgh
0 4 3 4 5 4 3 40 4 2 5 1 4 3 0 5 5 4 1 4
a
3
4
5
c, g
b, d, f, h
e
Der Pfad von Knoten i (in unserem Beispiel a) unterteilt die restlichen n-1 Blätter in d Klassen.
Für jede dieser Klassen rufen wir rekursiv dieses Konstruktionsverfahren auf, wobei wir nur dieTeilmatrix der entsprechenden Elemente in der Klasse betrachten, und hängen den entsprechen-den Teilbaum an den entsprechenden Knoten des Pfades von i.
a
3
4
5
g
e
bf
d
h
c
1
1
2
3
Warum funktioniert dieser rekursive Ansatz korrekt?
Sei v ein innerer Knoten mit Wert w auf dem Pfad von i.Sei j ein Blatt, das zur Klasse von Knoten v gehört:
Sei l ein anderes Blatt.
Ultrametric Trees
a
3
4
5
g
e
bf
d
h
c
1
1
2
3
Warum funktioniert dieser rekursive Ansatz korrekt?
Sei v ein innerer Knoten mit Wert w auf dem Pfad von i.Sei j ein Blatt, das zur Klasse von Knoten v gehört:
Sei l ein anderes Blatt. Wir unterscheiden drei Fälle:
(1) l gehört zur gleichen Klasse wie j:
D(i,j) = D(i,l)
Hieraus folgt, dass alle inneren Knoten eines ultrametrischenTeilbaumes der Klasse von v Werte kleiner gleich dem Wert von v besitzen.
(2) l gehört zu einer Klasse zwischen dem Blatt i und dem inneren Knoten v:
D(j,l) D(i,j)
D(i,j) > D(i,l) D(j,l) = D(i,j)
(3) l gehört zu einer Klasse zwischen dem inneren Knoten v und der Wurzel:
D(i,j) < D(i,l) D(j,l) = D(i,l)
Satz:
Falls D eine ultrametrische Matrix ist, dann ist der ultrametrische Baum eindeutig bestimmt.
Beweis: Folgt direkt aus der obigen Konstruktion.
Ultrametric Trees
Satz
Falls D eine ultrametrische Matrix ist, dann kann der ultrametrische Baum T von D in ZeitO(n2) konstruiert werden.
Wie erhält man ultrametrische Daten?
(1) The Molecular Clock Theory: Emile Zuckerkandl und Linus Pauling haben zu Anfang der 60ziger die sogenannte „Molecular Clock Theory“ Jahre vorgeschlagen. Diese Theorie besagt, dass die Zahl der zulässige Mutationen in den Genen pro Zeiteinheit ungefähr konstant ist. Zulässig heißt hier, dass diese mutierten Gene bzw. die codierten Proteine funktionstüchtig sind. Diese Theorie ist heftig umstritten, da man zum Beispiel von ver- schiedenen Molekülklassen nachgewiesen hat, dass sie unterschiedlich häufig mutiert wurden. Man nimmt oft an, dass die Zahl der Mutationen pro Zeiteinheit von bestimmten Proteinklassen in erster Näherung konstant ist und bestimmt für alle Paare in einer solchen Klasse die Zahl der Mutationen, die die Proteine ineinander überführen.
(2) Experimentelle Daten: Man betrachte eine Klasse von Genen (DNA). Man mische die DNA-Moleküle von zwei Genen, denaturiere die Moleküle, so dass Einzelstränge ent- stehen, mische die Einzelstränge und erlaube den Einzelsträngen wieder zu hybridisieren. Die Separierungstemperatur der gemischt hybridisierten Stränge ist umso größer, je ähn- licher die Gene sind.
Bäume mit additiven Distanzen
Definition:
Sei D eine symmetrische n x n Matrix, wobei die Zahlen entlang der Diagonalen gleich 0 sindund sonst größer als 0. Sei T ein Baum mit wenigsten n Knoten und mit gewichteten Kanten,wobei n Knoten mit den Zeilen von D beschriftet sind. Der Baum T wird als additiver Baumfür die Matrix D bezeichnet, wenn für jedes Paar von beschrifteten Knoten (i,j) gilt: Der Summe der Gewichte des Pfades von Knoten i nach Knoten j hat Gewicht D(i,j).
0689
6067
8603
9730
a b c d
abcd
a
b
c
d
2
4
3
1
2
Additives-Baum-Problem:
Gegeben eine symmetrische Matrix D mit Nullen auf der Diagonalen und echt positiven Ein-trägen sonst, berechne einen additiven Baum für D oder beweise, dass es keinen solchen Baumgibt.
Kompaktes Additives-Baum-Problem:
Gegeben eine symmetrische Matrix D mit Nullen auf der Diagonalen und echt positiven Ein-trägen sonst, berechne einen additiven Baum für D, der aus genau n beschrifteten Knoten be-steht, oder beweise, dass es keinen solchen Baum gibt.
Bäume mit additiven Distanzen
Definition:
Für eine gegebene symmetrische n x n Matrix D bezeichnen wir mit G(D) den vollständigenGraphen mit n Knoten {1, ..., n} und gewichteten Kanten, wobei die Kante zwischen i und j das Gewicht D(i,j) besitzt.
Satz:
Wenn es einen kompakten additiven Baum T zu D gibt, dann ist T gleich dem minimalen auf-spannenden Baum von G(D).
Beweis:
Sei T der kompakte additive Baum von D und sei e = (x,y) eine beliebige Kante, die nicht zu Tgehört. Da der Pfad von x nach y in T das Gesamtgewicht D(x,y) hat und alle Werte auf dem Pfad echt positiv sind, muß D(x,y) größer sein als jedes Kantengewicht auf dem Pfad. Wir zeigennun, dass die Kante e = (x,y) unter diesen Bedingungen nicht zu einem minimalen aufspannendenBaum gehören kann. Wir nehmen an, dass e zu einem minimalen aufspannenden Baum T‘ gehört.
T‘
x ye
Löschen wir e aus T‘, so zerfällt der Baum in zwei Teil-bäume, ein Teilbaum der x enthält und einer der y enthält.Es muß eine Kante e‘ in T existieren, die auf dem Pfad vonx nach y liegt und die beiden Teilbäume verbindet.
Fügen wir diese Kante zu T‘\{e} hinzu, so erhalten wireinen Baum T‘‘ mit dem folgenden Gewicht:
D(T‘‘) = D(T‘) – D(x,y) + D(x‘,y‘) < D(T‘) e‘
x‘
y‘
Bäume mit additiven Distanzen
Algorithmus: Gegeben eine symmetrische n x n Matrix D.
Satz:
Wenn es einen kompakten additiven Baum T zu D gibt, dann ist T gleich dem minimalen auf-spannenden Baum von G(D).
Beweis:
Sei T der kompakte additive Baum von D und sei e = (x,y) eine beliebige Kante, die nicht zu Tgehört. Da der Pfad von x nach y in T das Gesamtgewicht D(x,y) hat und alle Werte auf dem Pfad echt positiv sind, muß D(x,y) größer sein als jedes Kantengewicht auf dem Pfad. Wir zeigennun, dass die Kante e = (x,y) unter diesen Bedingungen nicht zu einem minimalen aufspannendenBaum gehören kann. Wir nehmen an, dass e zu einem minimalen aufspannenden Baum T‘ gehört.
T‘
x ye
Löschen wir e aus T‘, so zerfällt der Baum in zwei Teil-bäume, ein Teilbaum der x enthält und einer der y enthält.Es muß eine Kante e‘ in T existieren, die auf dem Pfad vonx nach y liegt und die beiden Teilbäume verbindet.
Fügen wir diese Kante zu T‘\{e} hinzu, so erhalten wireinen Baum T‘‘ mit dem folgenden Gewicht:
D(T‘‘) = D(T‘) – D(x,y) + D(x‘,y‘) < D(T‘) e‘
x‘
y‘
(1) Berechne den minimalen aufspannenden Baum T von G(D).
(2) Teste, ob der minimale aufspannende Baum T von G(D) additiv bezüglich D ist.
Bäume mit additiven Distanzen
Ziel:Wir zeigen im folgenden, wie man das additive Baum-Problem in Zeit O(n2) zu einem ultra-metrischen Problem reduzieren kann. Hierzu generieren wir eine Matrix D‘, die genau danneine ultrametrische Matrix ist, wenn die vorgegebene Matrix D additiv ist.
Idee:Wir nehmen an, dass D additiv ist und dass ein additiver Baum T von D bekannt ist. Wir nehmenferner o.B.d.A. an, dass alle Beschriftungen an den Blättern des Baumes angebracht sind. Wirwerden nun die Knoten von T so mit Zahlen beschriften, dass wir einen ultrametrischen Baum T‘erhalten. Sei v die Zeile von D, die den größten Eintrag mv enthält. Wir machen v zur Wurzel vonT‘.
a b
c d
2 1
3
4 2
a
b
c d
2
1
3
4 2
Für jedes Blatt i addieren wir mv – D(v,i) zu der Distanz der Kante, die zum Blatt i führt.
+ 6
+ 20+
(1) Die Distanz von v zu irgendeinem Blatt ist mv.(2) Jeder innere Knoten hat den gleichen Abstand zu allen Blättern in seinem Unterbaum.
Nun markieren wir alle inneren Knoten mit dem Abstand des Knotens zu allen Blättern in seinem Unterbaum.
9
7
4 Diese Zahlen liefern die Einträge für dieultrametrische Matrix D‘.
Bäume mit additiven Distanzen
v = root
w = lca(i,j)
i j
d(v,w)
T
d(i,w) d(j,w)
v = root
w = lca(i,j)
i j
d(v,w)
T‘
d(i,w) d(j,w)
+ mv – D(j,v)+ mv – D(i,v)
2 D‘(i,j) = d(i,w) + mv – D(i,v) + d(j,w) + mv – D(j,v)
Reduktion: (D, T) T‘ D‘ Wir benötigen eine direkte Reduktion von D D‘
2 D‘(i,j) = d(i,w) + d(j,w) + 2 mv – D(i,v) – D(j,v)
2 D‘(i,j) = D(i,j) + 2 mv – D(i,v) – D(j,v)
D‘(i,j) = mv + (D(i,j) – D(i,v) – D(j,v))/2
Satz:Falls D eine additive Matrix ist, dann ist D‘ eine ultrametrische Matrix, wobei
D‘(i,j) = mv + (D(i,j) – D(i,v) – D(j,v))/2
Bäume mit additiven Distanzen
Beachte! Der vorhergehende Satz erlaubt uns folgenden Test: Gegeben eine Matrix D.Generiere aus D die Matrix D‘ und teste, ob D‘ eine ultrametrische Matrix ist.Falls D‘ keine ultrametrische Matrix ist, dann ist D nicht additiv.
Wie sieht es mit der Umkehrung dieser Aussage aus?
Satz: Falls die Matrix D‘ eine ultrametrische Matrix ist, dann ist D eine additive Matrix.
Beweis:
Sei T‘‘ ein ultrametrischer Baum für die Matrix D‘. Wir ordnen den Kanten von T‘‘Gewichte zu, so dass jeder Pfad von einem Blatt i zu einem Vorfahren w genau die Distanzhat, die w als Beschriftung in T‘‘ hat. Jeder Kante (p,q) erhält die Differenz der Beschriftungender Knoten als Gewicht.
92
73
4 4
Die resultierende Pfaddistanz für ein Paar von Blättern (i,j) entspricht jedoch genau der zweifachen Distanz D‘(i,j) in der ultrametrischen Matrix D‘. Ferner gilt:
2 D‘(i,j) = 2 mv + D(i,j) – D(i,v) – D(j,v)
Wir subtrahieren nun für jedes Blatt i bzw. j von jeder Blattkante
mv – D(i,v) bzw. (mv – D(j,v))
Hieraus folgt für jedes Paar von Blättern, dass die Pfaddistanzim transformierten Baum gleich D(i,j) ist.
06
69
a b c d abcd 669
087
803
730
D
04
79
a b c d abcd 479
079
709
990
D‘
0
1
2
9
7
4
a
b
dc
Bäume mit additiven Distanzen
Algorithmus zur Berechnung eines additiven Baumes zu einer vorgegebenen additiven Matrix D.
(1) Generiere aus D die Matrix D‘ und berechne den ultrametrischen Baum T‘‘.(2) Ordne den Kanten die Differenz der Beschriftungen der Knoten als Gewicht zu.(3) Für jedes Blatt i subtrahiere mv – D(i,v) von dem Wert der Blattkante.
Satz: Ein additiver Baum für eine additive Matrix D kann in Zeit O(n2) konstruiert werden.
Perfect Phylogeny
In diesem Abschnitt betrachten wir einen anderen Ansatz, die Geschichte der Evolution zu rekonstruieren. Die Eingabe besteht hierbei nicht aus einer Distanzmatrix, sondern aus einerMatrix mit Zeichen bzw. Informationen über die untersuchten Spezies.
Definition einer Eigenschaftsmatrix
Sei M eine (binäre) n x m Matrix, wobei die Zeilen bestimmte Eigenschaften der Spezies kodieren.Falls die Spezies p (p-te Zeile) die Eigenschaft i (i-te Spalte) besitzt, ist M[p,i] = 1, andernfalls 0.
Wie erhält man die Daten (Eigenschaften)?
• Besitzt oder besitzt kein Rückgrat.• Hat Federn oder nicht.• Es können auch bestimmte metabolische oder regulatorische Eigenschaften verwendet werden.• Welche Art von Base an einer bestimmten Position im Genom vorhanden ist ( 1 bei A und G (Purin), 0 bei C und T (Pyrimidin)). Hierbei extrahiert man die Informationen aus einem multiplen Alignment.• Die Existenz und Größe von Lücken in multiplen Alignments. Mit Hilfe solcher Eigenschaften hat man zum Beispiel versucht, die Frage der Verwandtschaft von Pilzen, Pflanzen und Tieren zu klären (die Verwandtschaft zwischen Pilzen und Tieren scheint enger zu sein als zu Pflanzen).
Perfect Phylogeny
Definition
Sei M eine (binäre) n x m Eigenschaftsmatrix.
• Jede der n Spezies beschriftet genau ein Blatt von T.
• Jede der m Eigenschaften beschriftet genau eine Kante des Baumes T.
• Für jede Spezies p im Baum T gilt: Die Eigenschaften der Kanten auf dem Pfad von der Wurzel von T bis zum Blatt p sind genau die Eigenschaften, die p besitzt (mit Wert 1).
Ein phylogenetischer Baum für M ist ein Baum T mitgenau n Blättern, der die folgenden Eigenschaften besitzt:
00010
01100
10011
00100
00011
1 2 3 4 5
abcde
c
b
a
ed
2 3
1
5
4
10010
01100
10011
10100
00011
1 2 3 4 5
abcde
Zu dieser Matrix existiert kein phylogenetischer Baum !
Biologische Interpretation:
Die Wurzel repräsentiert einen gemein-samen Vorfahren, der keine der Eigen-schaften besitzt.
Jede der Eigenschaften taucht einmalauf und verschwindet dann nie wieder.
Perfect Phylogeny
Perfect Phylogeny Problem:
Gegeben eine (binäre) n x m Eigenschaftsmatrix M. Überprüfe, ob es einen phylogenetischen BaumT für M gibt, und konstruiere den Baum, falls er existiert.
Zunächst sortieren wir die Spalten der Matrix M, so dass sie bezüglich ihrer binären Zahlenwertefallend sortiert sind (die größte Spalte zuerst).
00010
01100
10011
00100
00011
2 1 3 5 4
abcde 00001
10100
01011
00100
00011
1 2 3 4 5
abcde
Ab jetzt nehmen wir o.B.d.A. an, dass die Spalten der Matrix M bereits sortiert sind.
Ferner nehmen wir o.B.d.A. an, dass die Eigenschaften entsprechend der Sortierung derSpalten von 1 bis m durchnummeriert sind.
Definition:Für jede Spalte k bezeichen wir mit Ok die Menge der Spezies, die die Eigenschaft k besitzen(eine Eins in Spalte k haben).
Perfect Phylogeny
k < j
Lemma:
1) Ok Oj
2) Identische Spalten bilden einen Block in der Matrix M.
Satz:
Die Matrix M hat genau dann einen phylogenetischen Baum T, wenn für jedes Paar i,j von Spalten gilt:Entweder sind Oi und Oj disjunkt oder eine Menge enthält die andere.
Beweis:
Wir nehmen zunächst an, dass ein Baum T zu M existiert und betrachten zwei beliebige Spalten i,j.
Sei ei bzw. ej die Kante des Baumes T, wo Eigenschaft i bzw. j den Wert 1 annehmen.
• ei = ej Oi = Oj
• ei liegt auf dem Pfad von der Wurzel zu ej Oi Oj
• ej liegt auf dem Pfad von der Wurzel zu ei Oj Oi
• Die Pfade zu den beiden Kanten verzweigen, bevor ei und ej erreicht werden.
Oj Oi =
Wir beweisen nun die andere Richtung und betrachten zwei Spezies p und q. Sei k die größteEigenschaft, die beide Spezies besitzen. Sei i<k eine weitere Eigenschaft, die p besitzt:
Oi Ok Oi Ok Auch q besitzt die Eigenschaft i.
Fortsetzung des Beweises auf der nächsten Seite.
Perfect Phylogeny
Die Strings zweier Spezies p und q sind biszu einer bestimmten Eigenschaft k identisch und danach haben sie keine gemeinsamen Eigenschaften(Symbole) mehr.
Wir bauen nun einen „Keyword-Tree“ (siehe Suffix-Tree). Hierbei ordnen wir jeder Spezies p einenString S(p) zu. Der String besteht aus den Nummern der Eigenschaften, die p besitzt, in der Reihen-folge, in der sie in M auftreten. Am Ende der Strings fügt man ein besonderes Endsymbol $ an.
Beispiel:
00001
10100
01011
00100
00011
1 2 3 4 5
abcde
12$
3$124$
35$1$ c
b
a
ed
1 3
24$
5$$$
$
Aus der Überlegung am Ende der vorherigen Seite folgt:
Hieraus folgt, dass M eine perfekte Phylogenie repräsentiert, deren Baum T durchEntfernen der $-Symbole aus dem obigen Keyword-Tree gewonnen wird.
Der obige Algorithmus hat eine Laufzeit von O(nm2) (Phylogeny-Test: Tests aller Paare von Spalten).
Perfect Phylogeny
Ein O(nm) Algorithmus zur Lösung des Perfect Phylogeny Problems:
(1) Sortiere die binären Zahlen in den Spalten von M mittels Radixsort.
(2) Konstruiere zu jeder Zeile der Matrix den entsprechenden Eigenschafts-String.
(3) Bilde den Keyword-Tree T für diese n Strings mit Länge kleiner gleich m.
(4) Teste, ob T (ohne Endsymbole) eine perfekte Phylogeny für M ist.
Der Test in Schritt 4 ist trivial, da die erste und dritte Forderung in der Definition einer perfekten Phylogeny durch die Konstruktion garantiert werden. Die zweite Forderung, dass jede der Eigen-schaften genau eine Kante beschriftet, wird durch eine Begehung aller Kanten plus eine Überprüf-und auf doppelte Beschriftungen getestet.
Baum-Kompatibilität
Man kann mit völlig unterschiedlichen Daten evolutionäre Bäume bauen. Es stellt sich dann natür-lich die Frage, ob die verschiedenen Bäume zueinander kompatibel sind oder nicht, d.h., ob die Bäume eine konsistente evolutionäre Geschichte beschreiben oder nicht.
Definition:
Ein phylogenetischer Baum T‘ ist eine Verfeinerung von T, falls man T aus T‘ durch eine Reihe vonKantenkontraktionen erhält.
a b c de
f g
T‘
a b
cde
f g
T
Definition:
Zwei Bäume T1 und T2 sind kompatibel, wenn es einen phylogenetischen Baum T3 gibt, der sowohleine Verfeinerung von T1 als auch von T2 ist.Baum-Kompatibilitätsproblem:
Gegeben zwei Bäume T1 und T2. Teste, ob die Bäume kompatibel sind, und falls dies der Fall ist,so berechne die Verfeinerung T3 von T1 und T2.
Baum-Kompatibilität
Sei M1 eine binäre Matrix, die eine Zeile für jede Spezies p und eine Spalte für jeden inneren Knoten jvon T1 enthält. M1[p,j] ist genau dann gleich 1, wenn das Blatt p im Teilbaum von Knoten j liegt, und 0 sonst
Wir nehmen an, dass T1 und T2 zwei phylogenetische Bäume für eine Menge von n Spezies sindund dass beide Bäume binäre Bäume sind. Nur die Wurzel der Bäume darf den Grad 1 haben.
Sei M2 eine binäre Matrix, die eine Zeile für jede Spezies p und eine Spalte für jeden inneren Knoten ivon T2 enthält. M2[p,i] ist genau dann gleich 1, wenn das Blatt p im Teilbaum von Knoten i liegt, und 0 sonst
Satz:
T1 und T2 sind genau dann kompatibel, wenn es einen phylogenetischen Baum für M3 gibt.Darüberhinaus ist ein phylogenetischer Baum T3 von M3 eine Verfeinerung von T1 und T2.
Sei M3 die Matrix, die man durch die Vereinigung von M1 und M2 erhält, d.h., man kombinieredie Spalten der beiden Matrizen.
Wir zeigen im folgenden, dass man das „Perfect Phylogeny Problem“ als ein ultrametrisches Problem lösen kann.
Wiederholung: Ultrametric Trees
Definition:
Sei D eine symmetrische n x n Matrix von reellen Zahlen.
05883
50885
88038
88308
35880
a b c d e
abcde
Ein ultrametrischer Baum T ist ein Baummit den folgenden Eigenschaften:
(1) T hat n Blätter, jedes dieser Blätter ist mit einer Zeile aus D beschriftet.
a
b
e
dc
(2) Jeder innere Knoten von T ist mit einem Wert von D beschriftet und hat mindestens 2 Kinder.
35
8
3
(3) Auf jedem Pfad von einem Blatt zur Wurzel wachsen die Werte in den Knoten.
(4) Für jedes Paar (i,j) von Blättern gilt: Der kleinste gemeinsame Vorfahr von i und j im Baum T ist mit dem Wert D(i,j) der Matrix beschriftet.
Definition:
Ein min-ultrametrischer Baum hat mit Ausnahme von Eigenschaft (3) die gleichen Eigenschaftenwie ein ultrametrischer Baum. Eigenschaft (3) wird ersetzt durch die Forderung, dass die Werteauf allen Pfaden von Blättern zur Wurzel kleiner werden.
Perfect Phylogeny als ein ultrametrisches Problem
Definition:
Gegeben eine n x m Eigenschaftsmatrix M. Wir definieren eine n x n Matrix DM wie folgt:Für jedes Paar p,q von Spezies setzen wir die Einträge DM[p,q] und DM[q,p] gleich der Zahl der Eigenschaften, die p und q gemeinsam haben.
Lemma:
Falls M eine perfekte Phylogeny besitzt, dann ist DM eine ultrametrische Matrix.
Beweis:Sei T die perfekte Phylogeny von M. Wir werden T in einen min-ultrametrischen Baum für dieMatrix DM transformieren. Die Wurzel beschriften wir mit 0. Dann beschriften wir den restlichenBaum und zwar von oben nach unten (top-down) wie folgt:
c
b
a
ed
2 3
1
5
4
0
Die Beschriftung eines Knotens v istgleich der Beschriftung seines Vaters plus der Zahl der Eigenschaften, die der Kante vom Vaterzu v zugeordnet sind.
11
2
Die Zahl im kleinsten gemeinsamen Vorfahren von zwei beliebigen Speziesp und q entspricht also der Zahl der Eigenschaften DM[p,q], die p und q gemeinsam besitzen.Ferner wachsen die Zahlen auf jedem Pfad von einem Blatt zur Wurzel.
Man beachte, dass der (min)-ultrametrische Baum einer ultra-metrischen Matrix eindeutig bestimmt ist.
Perfect Phylogeny als ein ultrametrisches Problem
Perfect Phylogeny via ultrametrischen Baum:
(1) Berechne die Matrix DM aus M wie auf der vorhergehenden Seite beschrieben.
(2) Teste, ob DM einen ultrametrischen Baum besitzt, und falls dies der Fall ist, berechne ihn. Falls es keinen ultrametrischen Baum gibt, dann hat M keine perfekte Phylogeny.(3) Falls DM einen ultrametrischen Baum T‘ besitzt, dann versuche die Kanten so zu mit den m Eigenschaften zu beschriften, dass T‘ in eine perfekte Phylogeny von M transformiert wird. Falls dies nicht funktioniert, dann hat M keine perfekte Phylogeny.
Übung: Man beschreibe ein effizientes Verfahren zur Beschriftung der Kanten (bzw. zum Testen, ob eine Beschriftung überhaupt möglich ist).
Split Decomposition
Ein anderes wichtiges Werkzeug zum Analysieren und Visualisieren von Distanz- und Sequenz-daten ist SPLITSTREE (Dress & Huson & Moulton [1996]). Obwohl der Name suggeriert, dass hiermit auch nur Bäume konstruiert werden, konstruiert dieses Tool eventuell auch Graphen (Split-Graphen), falls die Distanzdaten nicht unbedingt durch eine Baumform beschrieben werden könnenbzw. die Interpretation der Daten keine eindeutige, wohldefinierte Baumform als Resultat hervor-bringt.
Dieses neue Tool basiert auf der sogenannten Split-Decomposition-Technik, die von Bandelt undDress zu Beginn der neunziger Jahre in Bielefeld entwickelt wurde. Diese Technik erlaubt es einegegebene Metrik, die auf einer endlichen Menge definiert ist, auf kanonische Art und Weise in eineSumme von einfacheren Metriken zu zerlegen.
Split Decomposition
• Die Summe der Längen der Kanten des kürzesten Weges von einem Knoten (z.B. blue) zu einem anderen Knoten (z.B. red) ist proportional (eine Approximation) zur tatsächlichen (in der Distanzmatrix vorgegebenen) Distanz der beiden Knoten.
• Entfernt man aus einem Baum eine Kante, so zerfällt der Baum in zwei Zusammenhangs- komponenten. Hierdurch werden die Daten in zwei nicht-leere, disjunkte Teilmengen zerlegt.
• Um einen Split-Graphen „aufzusplitten“, kann es erforderlich sein, dass ein ganzes Bündel von parallelen, gleichlangen Kanten entfernt werden muß.
Split Decomposition
Definition:
Sei X = {1,2, ... , n} die Menge der Spezies mit Distanzmatrix d = (d ij)1 i, j n. Eine Bipartitionvon X ist eine Zerlegung von X in zwei disjunkte Teilmengen A und B, d.h.,
X = A B und A B = .
Ein Bipartition A, B von X heißt ein d-Split, wenn für alle i, j A und alle k, l B gilt:
dij + dkl < max {dik + djl , dil + djk }
i
j
k
l
i
k
j
l
i
l
j
k
Split Decomposition
Wie berechnet man die d-Splits einer Menge X={1, ... , n} von Spezies?
Hierzu verwendet man eine rekursive Prozedur: Wir nehmen an, dass die d-Splits der Menge{1, ..., i-1} bereits berechnet wurden, und beschreiben, wie wir ausgehend von diesen d-Splitsdie Menge der d-Splits von {1, ... , i } berechnen können:
Für jeden d-Split A,B von {1, ... , i-1} testen wir, ob (1) A {i}, B ein d-Split von {1, ... , i} ist, und
ob (2) A, B {i} ein d-Split von {1, ... , i} ist.
Ferner testen wir, ob {1, ... , i-1}, {i} ein d-Split von {1, ... , i } ist.
d1
d2
d3
d1 < d2 + d3 d-Split Bedingung für alle Paare von {1, ... , i-1}
Falls d eine Metrik ist, so gilt für jedes Element xX, dass nicht auf einer durch die restlichenPaare von Punkten gebildeten „Linie“ liegt: {x}, X\{x} ist ein d-Split von X.
Bei den obigen Tests betrachtet man natürlich in A {i} bzw. B {i} nur Paare mit i, da alleanderen Paare bereits vorher getestet wurden.
Die Laufzeit des obigen Algorithmus kann durch ein Polynom sechsten Grades in n (O(n6))nach oben abgeschätzt werden.
Split Decomposition
Wie berechnet man den Split-Graphen einer Menge X={1, ... , n} von Spezies?
Zunächst berechnen wir mit der rekursiven Prozedur die Menge {S1 , ... , Sk } aller d-Splits von X.
Wir beginnen mit einem Knoten v, der mit den Namen aller Spezies beschriftet ist. Dann erweitern wir diesen Graphen, indem wir d-Split für d-Split von X betrachten.
Beispiel: X = {a,b,c,d,e,f,g}
S1 = {a,b,f,g},{c,d,e}
S2 = {a,f,g},{b,c,d,e}
S3 = {a,b,c,d},{e,f,g}
S4 = {a,b,c,g},{d,e,f}
a,b,c,d,e,f,g
a,b,f,g c,d,e
Sei G=(V,E) der Graph derd-Splits {S1 , ... , Sk-1}. Wir betrachten nun den Split Sk = A, B:
(1) Erstelle zwei Kopien GA und GB von G, wobei die Knoten von GA nur mit den Elementen von A und die Knoten von GB nur mit den Elementen von B beschriftet werden.
(3) Verbinde die Paare von Knoten von GA und GB, die aus dem gleichen Ursprungsknoten von G hervorgegangen sind.
a,f,g b c,d,e
(2) Lösche alle leeren Knoten in GA und GB , die nicht auf einem kürzesten Pfad zwischen zwei beschrifteten Knoten liegen, und die entsprechenden Kanten.
a b c,d
f,g e
a b c
gd
f e
Split Decomposition
Welche Längen erhalten die Kanten eines d-Splits?
Definition:
Jedem d-Split A, B von X ordnen wir einen Isolations- oder Trennungsindex A,B wie folgt zu:
}},{max{min2
1::
,,,,, klijjkiljlik
BlkAji
dBABA dddddd
Diese Definition kann zu einem Isolationsindex für alle Splits wie folgt erweitert werden:
}},,{max{min2
1::
,,,,, klijklijjkiljlik
BlkAji
dBABA dddddddd
Für Splits, die keine d-Splits sind, hat der Isolationsindex den Wert 0.
Ferner können wir jedem Split A, B eine Split-Metrik A,B zuordnen. A,B (x,y) = 1 genau dann,wenn x ein Element von A und y ein Element von B ist oder umgekehrt. A,B (x,y) = 0, falls beideElemente zur gleichen Menge (A oder B) gehören.
Bandelt & Dress haben gezeigt, dass folgende Ungleichung gilt: ),(),(,
,, yxdyxBSplitsA
BABA Ferner definierten Sie eine Abbildung (Pseudo-Metrik):
),(),(),(,
,,0 yxyxdyxd
BSplitsABABA ),(),(),(
,,,
0 yxyxdyxdBSplitsA
BABA
Die Kanten eines d-Splits erhalten den Wert des Isolationsindexes als Länge. Der Gesamtabstandzwischen zwei Elementen x und y im Split-Graphen entspricht d(x,y) – d0(x,y).
