Art und Inhalt

Jedes Chromosom und damit jedes Gen liegt bei einem Individuum in doppelter Ausführung vor. Die Basensequenz auf einem einzelnen Chromosom heißt Haplotyp, die Kombination der zwei Basensequenzen heißt Genotyp. In der Regel liegen für eine Population nur Genotyp-Daten vor. Ziel ist es daher, eine (biologisch wahrscheinliche) Menge von Haplotypen zu berechnen, die diese Genotypen erklärt. Zum Teil gibt es effiziente Algorithmen für diese Problemstellung, andererseits sind manche Varianten NP-vollständig.

Im Seminar wird anhand von Originalarbeiten die algorithmische Komplexität von Haplotypisierungsproblemen behandelt und es werden neue Algorithmen in diesem Bereich vorgestellt.

• Dan Gusfield; Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions; 2002
• Eskin, Halperin, and Karp; Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny; 2002
• Gramm et al.; Haplotyping with Missing Data via Perfect Phylogenies; 2005
• Lippert et al.; Algorithmic Strategies for the Single Nucleotide Polymorphism Haplotype Assembly Problem; 2002
• Dan Gusfield: Efficient Algorithms for Inferring Evolutionary Trees; 1991
• Lippert et al. (Journal Version von ...) Algorithmic Strategies for the Single Nucleotide Polymorphism Haplotype Assembly Problem; 2002

Vorlesung

18.April 2006, Arfst Nickelsen.
Einführung zu Perfekten Phylogenien und Haplotypisierung

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(nm²)

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(nm²) beträgt.