Multivariate Algorithmics for Graph and String Problems in Bioinformatics

• Applicant: Professor Dr. Christian Komusiewicz
• Subject Area: Theoretical Computer Science ; Bioinformatics and Theoretical Biology
• Term: from 2015 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 289297972

The current best approach to solving NP-hard problems arising inbioinformatics is the combination of data reduction and formulation asinteger linear program (ILP). Parameterized algorithmics has alsocontributed to the development of efficient algorithms for theseproblems. The research project MAGZ aims to promote the evolution fromparameterized to multivariate algorithmics. This shall result inalgorithms that identify and exploit different structural features ofbiological data. The aim is to establish multivariate algorithmics asan equally powerful alternative to ILPs for solving NP-hard problemsin bioinformatics. Eventually, this shall significantly increase therange of solvable instances.

• DFG Programme: Research Grants