Optimal solutions for hard problems in computational biology

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2000 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants
• Participating Person: Professor Dr. Klaus-Jörn Lange