Optimale Lösungen harter Probleme der algorithmischen Biologie

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2000 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5292128

Die algorithmische Biologie hat sich zu einem unabhängigen und interdisziplinären Forschungsgebiet im Querschnitt der Bereiche Biologie, Chemie, Informatik und Mathematik entwickelt. Viele Probleme aus diesem Bereich sind kombinatorischer Natur und erweisen sich als von hoher Berechnungskomplexität. Der Molekularbiologe Joseph Felsenstein wird 1998 wie folgt zitiert: "About ten years ago some computer scientists came by and said they heard we have some really cool problems. They showed that the problems were NP-complete and went away."Die Untersuchung der Handhabbarkeit kombinatorisch schwieriger Probleme der Molekularbiologie ist das zentrale Anliegen dieses Projekts. Der Schwerpunkt liegt dabei auf exakten Algorithmen mit optimalen Lösungen und garantierten Laufzeitschranken. Insbesondere ist unser Anliegen, die parametrisierte Komplexität von biologischen Problemen zu ermitteln. Kernidee der parametrisierten Komplexität ist es, die "kombinatorische Explosion", z.B. bei NP-harten Problemen, auf einen Parameter einzuschränken und dadurch schnelle Algorithmen mit optimalen und nicht nur angenäherten Lösungen zu erhalten. Die Implementierung dieser Festparameter-Algorithmen ergänzen wir mit heuristischen Strategien und können so das Laufzeitverhalten weiter verbessern. [...]In Zusammenarbeit mit Partnern aus Biologie und Biochemie arbeiten wir an harten kombinatorischen Problemen in der Analyse von DNA-Sequenzen wie Phylogenetik, Primer-Design, Motivsuche und Genomvergleich.

• DFG-Verfahren: Sachbeihilfen
• Beteiligte Person: Professor Dr. Klaus-Jörn Lange