Komplexität von Haplotypisierungsproblemen

Einer der nächsten Schritte in der Erforschung des menschlichen Genoms wird die Erstellung der Haplotypenkarte sein. Sie wird aufzeigen, welche Beziehungen zwischen den Haplotypen (Variationen in der DNS-Sequenz) eines Individuums und der Wahrscheinlichkeit bestehen, 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 Chromosomsträngen verlorengegangen ist. Unter (praktisch belegten) evolutionstheoretischen Annahmen lassen sich Haplotypen aus Genotypdaten kombinatorisch rekonstruieren, man spricht vom Haplotypisierungsproblem. Die Berechnungskomplexität dieses Problems soll in Abhängigkeit von den gemachten Annahmen klassifiziert werden, um algorithmisch hilfreiche Annahmen zu identifizieren. Lösungsalgorithmen (beziehungsweise Approximations- oder Fixed-Parameter-Algorithmen) sollen weiterentwickelt und neue Ansätze erprobt werden. Die Tauglichkeit der Algorithmen soll mittels öffentlich zugänglicher Genotypdaten validiert und verglichen werden. Kernziel ist ein Algorithmus zur Haplotypisierung, der bei in der Praxis zutreffenden Annahmen effizient arbeitet und der die Haupteinschränkung aller bekannten Verfahren überwindet: das bei der Genotypbestimmung unvermeidliche Fehlen von Daten. Förderung durch die DFG seit November 2005.

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.