Post on 23-Apr-2019
transcript
Clustering und Parsimonie Simon Fischer, 5. September 2002
Sommerakademie der Studienstiftung des deutschen Volkes
St. Johann 2002
Arbeitsgruppe 3:
Bioinformatik - Neue Paradigmen fur die Forschung
Clustering und Parsimonie
Simon Fischer
Universitat Dortmund, FB Informatik
simon@united-wizards.de
- 1 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
WORUM ES GEHT� Rekonstruktion von Stammbaumen (Phylogenie)
� Annahme: Evolution hat gemeinsamen Vorfahren aller Lebewesen
� Darstellung der Geschichte als binarer Baum
� Kantenlangen als Entfernungsmaß der Verwandtschaft
� Heute lebende und ausgestorbene Spezies an den Blattern
� Ziel: Rekonstruktion eines solchen Baumes aus heutigen Beobachtungen
- 2 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
CLUSTERING� Inferenz von Stammbaumen
� Zusammenfassen verwandter, d.h. ahnlicher Taxa
� zwei ahnliche Taxa erhalten einen gemeinsamen Vorfahren
- 3 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
EIN- /AUSGABE FUR CLUSTERINGVERFAHREN
Eingabe:
� Metrik auf den Taxa, d.h. eine Abstandsmatrix �
� Abstrahiert von Beschreibung der Taxa (z.B. als Sequenzen)
� Abstandsmatrix kann erhalten werden durch Alignmentverfahren
Ausgabe:
� Ein binarer Stammbaum
� An den Blattern stehen die Taxa
� Innere Knoten sind unbeschriftet und stehen fur gemeinsame Vorfahren
� Kantenbeschriftungen: Vergangene Zeit seit Aufspaltung der Population
- 4 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
UPGMA
Unweighted Pair Group Method using Arithmetic Averages
1. Eingabe
Eine � � � -Abstandsmatrix auf � Taxa
2. Initialisierung
bilde � Cluster � ��� ��� definiere ein Blatt pro Taxon auf Hohe .
3. Iteration
(a) Wahle zwei Cluster � � und � � mit � � � � minimal
(b) � � � ��� � � , definiere � ��� fur alle Cluster � �
(c) Definiere einen Knoten � als Elter von� und � auf Hohe � � � �� �
(d) Fuge � zur Menge der Cluster hinzu und entferne � � und � �
- 5 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
ABSTANDSMASS FUR CLUSTER
Der neue Cluster � entsteht aus � �� � � . Bestimme die Abstande aller anderen
Cluster � � zu � :
Ungewichtetes Mittel � ��� �
� � �� � � � ���
Durchschnittlicher Abstand der Elemente � ��� � �� � �� � � �� � �� � �� � � ��
�� � � � �� � �
Minimaler Abstand der Elemente � ��� � � � � � � ��� � � � ��� �
Maximaler Abstand der Elemente � ��� � � �� � � � � � � � � ��� �- 6 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
ULTRAMETRISCHE BAUME� Eine Metrik � auf Blattern eines Baumes heißt additiv, wenn die Entfernung
zweier Blatter der Pfadlange zwischen den Blattern entspricht.
� Eine additive Metrik heißt Ultrametrik, wenn jeder Pfad von der Wurzel zu einem
Blatt gleich lang ist.
� Bezug zur Evolution:
– Nur Ersetzungen
– keine Auslassungen und Einfugungen
– konstante molekulare Uhr
� ultrametrischer evolutionarer Stammbaum
- 7 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
EIGENSCHAFTEN VON ULTRAMETRIKEN
3-Punkt-Bedingung Fur drei Punkte� � � � � mit den Abstanden � �� � � � , � �� � � �
und � � � � � � sind zwei Abstande gleich und der dritte ist nicht großer.
Semantisch: Von drei Taxa sind zwei enger verwandt als die beiden eng
verwandten mit dem dritten.
4-Punkt-Bedingung Fur vier Punkte� � � � � ��� mit Abstandssummen
� � � � �� � � ��� � � � �� � , � � � � �� � � ��� � � � ��� � und � � � � �� ��� � � � � � � � �
sind zwei der Summen gleich und nicht geringer als die dritte.
- 8 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
KORREKTHEIT VON UPGMA
auf ultrametrischen Baumen
Satz: Sei � ein ultrametrische Baum. Im� -ten Schritt erzeugt UPGMA einen
Teilbaum von � , dessen Wurzel in � dem Knoten mit der� -kleinsten Hohe
entspricht. Außerdem erzeugt der Algorithmus einen zugehorigen Cluster, der alle
Blatter des Teilbaums enthalt. (Wir benutzen diese Formulierug, obwohl es mehrere
Knoten mit gleicher Hohe geben kann.)
Fur� � � haben wir die Korrektheit von UPGMA.
- 9 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
KORREKTHEIT VON UPGMA - BEWEIS
durch vollstandige Induktion nach� :
� Induktionsanfang In den ersten Schritten erzeugt UPGMA korrekt die Blatter
� Induktionsschritt
– UPGMA wahlt zwei Cluster ��� und ��� � mit minimalem Abstand
– Zu �� und �� � gehoren nach I.V. korrekt rekonstruierte Teilbaume �� und
�� � mit gemeinsamem Vorganger �
– � � � � � � � � � �� � �� fur� � �� � � � �� �
� � � �� � �� � � � � � � � neuer Knoten auf Hohe � , korrekt
– Da � � � minimal gewahlt war, gibt es keinen Knoten dazwischen
- 10 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
NICHT ULTRAMETRISCHE BAUME - FARRIS TRANSFORMATION
Sei die Abstandsmatrix � nun keine Ultrametrik
� Idee: Berechne � aus � mit gleicher Topologie, aber � Ultrametrik
� � � � �� � � � � �� � ��� �� � ��
� �
�� �
wobei
�� � ��
��� � � � ��
�
der durchschnittliche Abstand zur Wurzel ist.
� UPGMA erzeugt auf � die korrekte topologische Ordnung.
- 11 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
FARRIS TRANSFORMATION - BEWEIS
Jungster gemeinsamer Vorganger von� und � heiße� �� �� � � � .
� Da sich der Abstand als Pfadlange berechnet, ist
� � � � � � � �� � � � �� � � � � � ���� � � � � � �
also� � � � �� � �� �� � ��
�
� �� � ���� � � � � � �
� Durch Einsetzen in die Definition folgt� � � � �
�� � �� � ���� � � � � � ���
� Da� �� �� ��� � � � und � � �� � folgt
� � �� �
�� � � �� �
- 12 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
NICHT ULTRAMETRISCHE BAUME - FITCH-MARGOLIASH
Eine weitere einfache Beobachtung fuhrt zum Algorithmus von Fitch-Margoliash
� � , � eng verwandt, � reprasentiert den ferner verwandten Rest
� � � � ��� � � � �� �� � ��
�
� � � � ��� � � � �� �� � ��
�
ba c
x y
zu
- 13 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
ALGORITHMUS VON FITCH-MARGOLIASH
...
3. Iteration
(a) Wahle einen Cluster � � und � � mit � � � � minimal
(b) Berechne den temporaren Restcluster �
(c) Berechne � � � � � � � � � � � � �
� � ��
�� � � �� � und � � � � � analog.
(d) Vereinige die beiden Cluster und erzeuge den Elter � von� und � . Berechne
die Kantenlangen
� �� � � � �� � � � � � � � � � � � �� � � � �
�und� � � � � � analog
- 14 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
PARSIMONIE� Benutze Wissen uber Sequenzen
� Suche Baum mit minimalen Mutationskosten
� Nur Ersetzungen, keine Loschungen und Einfugungen
� Zwei Module:
1. Berechne Kosten fur einen Baum mit gegebener Struktur und fest
zugeteilten Blattern
2. Durchsuche den Baumraum
- 15 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
MINIMALE MUTATIONSKOSTEN
bei einem Baum mit � gegebenen Sequenzen uber � an den Blattern
� Gesucht: Belegung der inneren Knoten mit Sequenzen, die die Mutationskosten
minimieren
� Erste Erkenntnis: Einzelne Stellen sind unabhangig zu behandeln
� Zweite Erkenntnis: Betrachte einen Knoten � , fur dessen Kinder alle
Moglichkiten bekannt sind
– Es gibt gemeinsame Moglichkeiten � An � ist ohne Kosten die
Schnittmenge der Moglichkeiten moglich
– Es gibt keine gemeinsamen Moglichkeiten � An � entstehen auf jeden Fall
Kosten, egal welcher Buchstabe aus � gewahlt wird
- 16 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
TRADITIONELLE PARSIMONIE
1. Eingabe: Baum mit � Blattern, an denen Zeichen aus � stehen
2. Rekursion (Bestimme fur den Knoten � , beginnend bei der Wurzel die Menge
� �� � der moglichen Zeichen an diesem Knoten)
� ist Blatt: Liefere � � � � Zeichen an diesem Blatt zuruck
� kein Blatt: Bestimme fur die Kinder � und � rekursiv � � und � � .
� � �
��
� �� � � falls � �� � � � �
� � � � � sonst
Im zweiten Fall erhohe die Kosten um 1.
- 17 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
KONSTRUKTION DER BELEGUNG� An der Wurzel wahle ein Zeichen zufallig aus � �
� Ist beim Kind � das gleiche Zeichen moglich, wahle dieses auch beim Kind
� Ansonsten wahle ein zufalliges Zeichen aus � �
� Fahre rekursiv fort
- 18 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
GEWICHTETE PARSIMONIE
1. Eingabe wie gehabt plus Mutationskostenmatrix �
2. Rekursion (Bestimme fur Knoten � , beginnend mit der Wurzel die Kosten
� � �� � des Teilbaums, falls an Knoten � das Zeichen� � � stehen soll.)
� ist Blatt � � �� � �
��
falls� das Zeichen an Blatt �
� sonst
� kein Blatt � � �� � � � � � � � � � � ��� � �� � � � �� � � � � � � � � ��� � �� � � � �
3. Ende Liefere als minimale Kosten des Baumes
� �� � � �� �� �� � �
- 19 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
BEMERKUNGEN� Falls � �� �� � � und � �� � � � � � fur� � � erhalten wir traditionelle
Parsimonie
� Rekursionsformel fur Laufzeit (bei � Knoten):
� � � � � � � � � � �� � �
� � �� � �
� � � � � �Also bei Sequenzlange � � � � � � �
� � � �
- 20 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
SUCHVERFAHREN� Suchraum exponentiell groß
� (Randomisierte) lokale Suche
– Zweige verbiegen
– neuen Baum bewerten
– veranderter Baum besser � mit neuem Baum weitermachen
� Metropolis Verfahren: Auch Verschlechterungen akzeptieren; ermoglicht
Verlassen von lokalen Optima
� Bechneidung des Suchraums durch Problemwissen:”Kilometerzahlermethode“
- 21 -
Clustering und Parsimonie Simon Fischer, 5. September 2002
ZUSAMMENFASSUNG UND AUSBLICK
Geloste Probleme:
� Effiziente Algorithmen fur Rekonstruktion von Stammbaumen im idealisierten
Fall (Ultrametrik): Varianten von UPGMA
� Effiziente Algorithmen fur Zuteilung von Sequenzen mit minimalen
Mutationskosten auf einen Baum mit gegebener Struktur: Parsimonie
Offene Probleme:
� Effizientes durchsuchen der Menge aller moglichen Baume
� Ausnutzen von Wissen uber Sequenzen? Struktur des Suchraums?
- 22 -