Komplexität von Haplotypisierungsproblemen

• Antragsteller: Professor Dr. Till Tantau
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5453766

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.

• DFG-Verfahren: Sachbeihilfen