Parameterized algorithmics for bioinformatics

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

Das Projekt Parametrisierte Algorithmik bioinformatischer Probleme (PABI) zielt auf die Untersuchung der Ursachen der NP-Schwere einer großen Zahl von Problemen der algorithmischen Bioinformatik. Der Fokus der Theoriegruppe liegt hierbei auf Problemen des Daten Clustering und der Datenanalyse, der Phylogenetik und damit verwandten Problemen und der Analyse biologischer Netzwerke. Die eingesetzten algorithmischen Entwurfsmethoden umfassen in Polynomzeit ausführbare Datenreduktionsregeln und Problemkerne, tiefenbeschränkte Suchbäume, Color-Coding und iterative Kompression. Diese Untersuchungen werden ergänzt durch Implementierungsarbeiten und darauf basierende Experimente (besonders mit frei verfügbaren, realen Daten), dabei die Leitlinien des Algorithm Engineering beachtend. Alle entwickelten Software-Werkzeuge sollen frei verfügbar gemacht werden. Es gibt einen engen Austausch mit der Jenaer Bioinformatikgruppe (Prof. Böcker), insbesondere die Implementierungen und Experimente (Algorithm Engineering) betreffend. Sowohl die parametrisierte Algorithmik als auch die Bioinformatik prägen des Jenaer Lehr- und Forschungsprofil maßgeblich mit. Etliche studentische Arbeiten laufen in diesem Bereich. Es ist angedacht, ein internationales Dagstuhl-Forschungsseminar im Schnittfeld Parameterisierte Algorithmik, Bioinformatik und Algorithm Engnieering zum Projektende hin zu beantragen, an dem dann Forscher aus aller Welt teilnehmen sollen.

• DFG-Verfahren: Sachbeihilfen