| Durchführung: Termine, Themen, Abstracts |
18.April 2006, Arfst Nickelsen.
Einführung zu Perfekten Phylogenien und Haplotypisierung
[Handout]
30. Mai 2006, Gaby Wangorsch.
Das Phylogenie-Problem für Haplotyp-Matrizen – ein Linearzeit-Algorithmus
Literatur:
Gusfield, 1991, Efficient Algorithms for Inferring Evolutionary Trees, Abschnitte 1.1 und 1.2.
Abstract:
Ich werde in meinem Referat auf das Phylogenie-Problem eingehen:
Was ist ein phylogenetischer Baum, was ist eine perfekte Phylogenie,
wie kann man aus gegebenen Daten-Matrix einen phylogenetischen Baum erzeugen?
Anhand von Beispielen werde ich zeigen, wie man mit einem effizienten Linearzeit-Algorithmus ermitteln kann,
ob es überhaupt möglich ist, aus einer Datenmatrix einen phylogenetischen Baum zu erzeugen.
Neben dem Vorgehen des Algorithmus (Sortieren mit Radix-Sort, Matrixoperationen,....)
werde ich den (Korrektheits-)Beweis dazu führen und versuchen zu erklären,
dass es sich auch wirklich um einen Linearzeit-Algorithmus handelt.
Hat eine Datenmatrix eine Phylogenie, so kann mit einem Linearzeit-Algorithmus ein Baum konstruiert werden.
Auch dies werde ich beweisen und an einem Beispiel zeigen.
6. Juni 2006, Maren Vens.
Auf Pfaden zur Haplotypisierung in Linearzeit
Literatur:
Gramm, Nierhoff, Sharan, Tantau, 2005, Haplotyping with Missing Data via Perfect Phylogenies; Abschnitt 5.
Abstract:
Kern des Vortrages wird sein, wie man von einer Genotypmatrix zu einer möglichen Haplotypisierung kommt.
Um das Problem zu vereinfachen, wird im Laufe des Vortrages
auf biologische Eigenschaften des menschlichen Genoms zurückgegriffen,
welche schließlich zu den perfekten Pfadphylogenien führen.
Es wird ein Algorithmus vorgestellt, der in Linearzeit bestimmt,
ob einer gegebenen Genotypmatrix eine perfekte Pfadphylogenie zugrunde liegt, und diese gegebenenfalls berechnet.
13. Juni 2006, Michael Elberfeld.
Perfekte Pfad-Phylogenie mit fehlenden Daten ist NP-vollständig
Literatur:
Gramm, Nierhoff, Sharan, Tantau, 2005, Haplotyping with Missing Data via Perfect Phylogenies.
Abstract:
Die Frage, ob eine perfekte Phylogenie für eine Menge von Haplotypen
bzw. Genotypen möglich ist, lässt sich in Linearzeit beantworten
(Vortrag von Gaby). Ähnlich effizient ist dieses Problem lösbar, wenn
man nach der Existenz einer perfekten Pfad-Phylogenie fragt (Vortrag von
Maren). Hierbei hat der phylogenetische Baum die Form zweier Listen, die
sich das erste Element (die Wurzel des Baumes) teilen.
Es kommt vor, dass bei der Erhebung von Genotypinformationen Fehler
auftreten, d.h. einige Einträge in der Genotypmatrix sind leer. Die
Algorithmen für obige Probleme lassen sich auf diese Eingabedaten nicht
anwenden. Das Problem ist nun zu entscheiden, ob man die fehlenden
Einträge so ausfüllen kann, dass eine perfekte Pfadphylogenie möglich
wird. Dieses Problem hat sich als NP-vollständig herausgestellt.
Im ersten Teil meines Vortrags werde ich darauf eingehen, was ein
Problem ist, wie man zeigt, dass ein Problem NP-vollständig ist und was
das heißt. Eine zentrale Idee ist hierbei, die Eingabe von Problemen
ineinander zu transformieren. Durch diese Technik zeigt man, dass
verschiedenste Probleme mit gleichem Zeitaufwand lösbar sind – man sagt,
sie sind "gleich schwer". Im zweiten Teil schauen wir uns eine konkrete
Transformation an, die Eingaben für das Problem der perfekten Pfad-Phylogenie
mit fehlenden Einträgen erzeugt. Dieses ist ein Algorithmus,
den ich anhand eines Beispiels erklären möchte. Mit den Betrachtungen
aus dem ersten Teil wird die NP-Vollständigkeit folgen.
20. Juni 2006, Jennifer Levering.
Konfliktgraphen zur Lösung des SNP-Haplotyp-Assembly-Problems
Literatur: Lippert, Schwartz, Lancia, Istrail, 2002, Algorithmic Strategies for the
Single Nucleotide Polymorphism Haplotype Assembly Problem; bis Theorem 3.2.
Abstract:
Das SNP-Haplotyp-Assembly-Problem besteht in der Bestimmung der tatsächlich zugrundeliegenden Haplotypen
aus kurzen, einsträngigen Sequenzfragmenten, die nur wenige SNPs beinhalten.
Eine Möglichkeit der Lösung dieses Problems ist die Benutzung von Konfliktgraphen.
Ich werde in meinem Vortrag das SNP-Haplotyp-Assembly-Problem formalisieren und auf dessen Lösung eingehen,
insbesondere auf den Zusammenhang zwischen Haplotypen und bipartiten Graphen sowie den Zusammenhang
zwischen Haplotypen und Flussproblemen.
27. Juni 2006, Dörte van Straaten.
Lösung des PPH-Problems mittels Erstellung eines linearen Gleichungssystems
Literatur: Eskin, Halperin, Karp, 2002, Efficient Reconstruction of Haplotype
Structure via Perfect Phylogeny; Abschnitt 3.
Abstract:
Ich möchte Euch einen Algorithmus vorstellen, dessen Aufgabe die Lösung
des PPH-Problems ist, d.h. eine Perfekte Phylogenie von Haplotypen zu
einer gegebenen Genotyp-Matrix zu erstellen bzw. zu erkennen, dass es
keine Perfekte Phylogenie gibt.
Der Algorithmus beruht darauf, für Spaltenpaare sogenannte induzierte
Mengen zu bestimmen. Die induzierten Mengen enthalten die Haplotypen, die
durch diese Spalten bereits festgelegt sind. Haplotypen sind nicht
festgelegt, falls ein Spaltenpaar eine Zeile mit zwei Zweien enthält. Der
Algorithmus klärt nun, ob die beiden Zweien gleich aufgelöst werden, wobei
die Haplotypen {00,11} entstehen oder ob die Zweien ungleich aufgelöst
werden, so dass sich die Haplotypen {01,10} ergeben.
Zur Lösung dieser Aufgabe wird für jede Zeile der Genotypmatrix ein Graph
erstellt, dessen Kanten durch eine Labeling-Funktion markiert werden.
Mithilfe der Labeling-Funktion kann die Aufgabenstellung in ein System von
linearen Gleichungen umgeschrieben werden, das dann mit herkömmlichen
Algorithmen gelöst werden kann. Die erhaltene Lösung kann anschließend auf
die Lösung des PPH-Problems übertragen werden.
4. Juli 2006, Britta Nisius.
Lösung des PPH-Problems in O(nm2)
Literatur: Eskin, Halperin, Karp, 2002, Efficient Reconstruction of Haplotype
Structure via Perfect Phylogeny; Abschnitt 4.
Abstract:
Ähnlich wie in Dörtes Vortrag am 27.06. basiert auch der von mir vorgestellte Algorithmus auf induzierten Mengen,
mit deren Hilfe bestimmt werden kann, welche Spaltenpaare gleich und welche ungleich aufgelöst werden müssen.
Um dieses Problem zu lösen, arbeitet der Algorithmus mit Relationen,
ähnlich wie sie schon in Marens Vortrag vorgestellt wurden.
Basierend auf diesen Relationen kann eine Pivotspalte bestimmt werden, d.h. eine Spalte,
die bezüglich der gewählten Relation die maximale ist.
Der Algorithmus löst dann iterativ jeweils alle Zeilen der
Eingabematrix auf, in denen die Pivotspalte eine 2 enthält.
Für alle diese Zeilen können die zugehörigen Haplotypen
durch Erstellen eines bipartiten Graphen bestimmt werden.
Alle Zeilen der Ausgangsmatrix A, für die die Haplotypen bestimmt
wurden, werden durch die zugrundeliegenden Haplotypen ersetzt, so dass
nach jedem Iterationsschritt die Matrix insgesamt mehr Zeilen enthält,
aber darunter weniger Zeilen, in denen noch eine 2 vorkommt.
Außerdem können in jeder Iteration auch einige Spalten, darunter mindestens die Pivotspalte, gelöscht werden,
so dass sich die Anzahl der Spalten pro Iterationsschritt um mindestens eine verringert.
Jede Iteration hat die Laufzeit O(m²), es müssen maximal n Iterationen durchgeführt werden,
so dass die Gesamtlaufzeit O(nm2) beträgt. |
