Algorithmische Methoden zur Kartierung von DNA-Sequenzen

In der Molekularbiologie traten in den letzten Jahren vermehrt diskrete Optimierungs- und Zuordnungsprobleme im Bereich der Untersuchung des Erbguts und der Proteine auf. Dies gilt insbesondere für das Human Genome Project, dessen primäres Ziel die Erforschung der genetischen Information des Menschen ist. Hierzu gehört die vollständige Sequenzierung des Genoms, d. h. die Erforschung von Nucleotidsequenzen bzw. deren Funktion. Hier wird eine spezifische Problemstellung betrachtet, deren Ziel die Ermittlung der realen Ordnung von Klonen (Teilabschnitten von Chromosomen) mit Hilfe von experimentell ermittelten - in der Regel fehlerbehafteten - Daten ist (STS-Kartierungsstrategie). Die sich daraus ergebende kombinatorische Problemstellung wird diskutiert, und es werden verschiedene Methoden zur Generierung von Lösungen sowie zur Identifikation experimenteller Fehler entwickelt und analysiert.