Komplexität von Haplotypisierungsproblemen
Final Report Abstract
Einer der nächsten Schritte in der Erforschung des menschlichen Genoms wird die Erstellung der Haplotypenkarte sein. Ging es beim Humangenom-Projekt darum, die Basensequenz eines einzelnen Individuums komplett zu bestimmen, wird die Haplotypenkarte die Variationen in den DNS-Sequenzen der Menschheit aufzeigen. Dies wird es ermöglichen, Beziehungen zwischen den Haplotypen eines Individuums und der Wahrscheinlichkeit zu bestimmen, auf bestimmte Medikamente anzusprechen oder bestimmte Krankheiten zu bekommen. Kostengünstige und schnelle Verfahren zur individuellen Haplotypenbestimmung werden große Bedeutung für Vorsorge- und Behandlungsplanung haben. Gängige Verfahren liefern allerdings lediglich Genotypen, die zwar alle Informationen über die Variation der DNS-Sequenz an verschiedenen Stellen enthalten, bei denen aber die Zuordnung zu den beiden Chromosomensträngen verlorengegangen ist. Unter (praktisch belegten) evolutionstheoretischen Annahmen lassen sich Haplotypen aus Genotypdaten kombinatorisch rekonstruieren, man spricht von Haplotypisierungsproblemen. Im Projekt wurde die Berechnungskomplexität dieser Probleme in Abhängigkeit von den gemachten Annahmen untersucht. Unsere Ergebnisse, zusammen mit den Ergebnissen anderer Gruppen, erlauben es nun, den Einfluss der verschiedenen Kombinationen von evolutionstheoretischen Annahmen auf die Komplexität der Haplotypisierung zu benennen. Dadurch ist es möglich, neue Algorithmen zu entwickeln, die möglichst universell einsetzbar sind (da sie nur wenige Annahmen machen) und trotzdem effizient bleiben. Eine Annahme bezüglich der Eingabedaten, die oft nicht zutrifft, ist die Complete-Data-Assumption. In der Praxis sind Daten in aller Regel gerade nicht vollständig; bei der Bestimmung der Genotypen im Labor sind Fehler und fehlende Daten unvermeidlich. Leider machen fehlende Daten die Haplotypisierung (nachweislich) ungleich schwieriger, weshalb sowohl wir wie auch andere Gruppen sich intensiv mit der Frage beschäftigen, wie man das Problem der fehlenden Daten überwindet. Einer unser Beiträge hierzu ist ein Fixed-Parameter-Algorithmus, die für unvollständige Genotypdaten eine effiziente Haplotypisierung durchführen kann. Es liegt nahe, dass bei einer Haplotypisierung Wissen über die Ethnizität der untersuchten Individuen hilfreich sein kann, da dieses Wissen die Menge der möglichen Haplotypen einschränkt. Es wurde aber von anderen Arbeitsgruppen vermutet, dass keine effizienten Algorithmen zur Haplotypisierung existieren, die dieses Wissen berücksichtigen. Ein spannendes von uns erzieltes Ergebnis ist eine Widerlegung dieser Vermutung: Es gibt einen sehr effizienten Algorithmus, der Informationen über die Ethnizität von Individuen zur Verbesserung der Haplotypisierung benutzt. Die theoretischen Untersuchungen wurden komplementiert durch Implementationen verschiedener Algorithmen zur Haplotypisierung. Diese Algorithmen kann man mittels öffentlich zugänglicher Genotypdaten des HapMap-Projektes testen, vergleichen und auf ihre Praxistauglichkeit überprüfen. Anhand realer Daten haben wir im Projekt validieren (und in einem Fall auch falsifizieren) können, dass die für Haplotypisierungsalgorithmen essenziellen Annahmen auf die Daten aus der HapMap-Datenbank tatsächlich zutreffen. Ein Beispiel für eine häufig gemachte, aber kaum durch Untersuchungen realer Daten gestützte Annahme ist die Perfect-Phylogeny-Assumption; wir konnten zeigen, dass sich tatsächlich relativ große zusammenhängende Bereiche im Genom durch perfekte Phylogenien erklären lassen.
Publications
- On the complexity of SNP block partitioning under the perfect phylogeny model. In Proceedings of Workshop on Algorithms in Bioinformatics (WABI), volume 4175 of Lecture Notes in Computer Science, pages 92–102, 2006
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, and Till Tantau
- Haplotyping with missing data via perfect path phylogenies. Discrete and Applied Mathematics, 155:788–805, 2007
Jens Gramm, Till Nierhoff, Roded Sharan, and Till Tantau
- Computational complexity of perfect-phylogeny-related haplotyping problems. In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), volume 5162 of Lecture Notes in Computer Science, pages 299–310, 2008
Michael Elberfeld and Till Tantau
- Fixed-parameter algorithms in phylogenetics. In Jonathan Keith, editor, Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, volume 452 of Methods in Molecular Biology, pages 507–535. The Humana Press, 2008
Jens Gramm, Arfst Nickelsen, and Till Tantau
- Influence of tree topology restrictions on the complexity of haplotyping with missing data. In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), volume 5532 of Lecture Notes in Computer Science, pages 201–210, 2009
Michael Elberfeld, Ilka Schnoor, and Till Tantau
- Phylogeny- and parsimony-based haplotype inference with constraints. In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), volume 6129 of Lecture Notes in Computer Science, pages 177–189, 2010
Michael Elberfeld and Till Tantau
