Parametrisierte Algorithmik bioinformatischer Probleme

• Antragsteller: Professor Dr. Sebastian Böcker
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2009 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 162571619

Dieses Projekt hat das Ziel, NP-schwere Probleme in der Bioinformatik mitHilfe von Festparameteralgorithmen zu lösen. Durch eine genaue Analyse derProblemstruktur können exakte Lösungen für scheinbar unlösbare Instanzenbestimmt werden. Die Grundidee der Festparameteralgorithmik ist es, denexponentiellen Anteil der Laufzeit auf einen möglichst kleinen Parameter zubeschränken, der für jedes Problem individuell gewählt wird. In derBioinformatik lohnt sich -- trotz längerer Laufzeiten -- die Berechnungexakter Lösungen für NP-schwere Probleme, da dies häufig eine bessere Analysevon Daten aus teuren und arbeitsintensiven Experimentenermöglicht. Biologische Probleme zeigen oftmals Eigenschaften, die sich füreinen Festparameteralgorithmus ausnutzen lassen.In den ersten beiden Jahren des Projekts haben wir Festparameteralgorithmenund Datenreduktionsregeln für verschiedene Probleme aus der Bioinformatikentwickelt, implementiert, "engineered" und evaluiert. Außerdem wurdenbereits einige der entwickelten Algorithmen Biologen und Biochemikern inbenutzerfreundlichen Programmen zugänglich gemacht. In den nächsten beidenJahren werden wir auch weiter die (parametrisierte) Komplexität neuerbioinformatischer Probleme analysieren und neue parametrisierte Algorithmenentwickeln; wir werden unser Arbeit an Problemen fortsetzen, die wir in dervorigen Förderperiode untersucht haben; und wir werden auch weiterhin dieresultierenden Methoden Biologen zugänglich zu machen.

• DFG-Verfahren: Sachbeihilfen