Project Details
Projekt Print View

Multivariate Algorithmics for Graph and String Problems in Bioinformatics

Subject Area Theoretical Computer Science
Bioinformatics and Theoretical Biology
Term from 2015 to 2022
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 289297972
 
Final Report Year 2021

Final Report Abstract

The aim of the research project MAGZ was to further develop the approach of Multivariate Algorithmics for solving algorithmically hard graph and string problems, particularly focusing on hard problems in bioinformatics. Multivariate Algorithmics tries to exploit structural aspects of typical input data to develop efficient algorithms for realistic problem instances. These structural aspects are described by numerical parameters. From a theoretical point of view, the project had the aim to identify parameters that describe new, previously unexploited structural aspects of typical input data. For example, for Cluster Editing, a fundamental problem in graph-based data clustering, we identified a new family of parameters that can be exploited algorith- mically. These parameters measure the difference between an optimal solution k and a precomputed lower bound ℓ and are thus smaller than the previously app- lied parameter k. Consequently, algorithms that exploit these parameters instead of k may solve a larger set of instances efficiently. We also achieved substan- tially improved multivariate algorithms for string problems with applications in comparative genomics and synthetic biology. An approach that was used for two string problems relies on a translation to a graph problem which is then solved by an algebraic algorithm. This approach could be useful for further hard string problems. In addition, we showed for a wide range of subgraph problems that exact algorithms for these problems presumably must have an exponential running time. From a practical point of view, one of the goals of the project was to improve several multivariate algorithms so that they are competitive with standard solvers for NP-hard problems such as integer linear programs (ILPs). It was further- more the aim that the developed algorithms should be capable of solving hard problems for genome-wide data sets. For graph problems, this means that the algorithms should be able to handle graphs with approximately 100 000 nodes. Within the research project, we developed FixCon, a generic solver for cardinality- constrained optimization problems in graphs. This solver achieved our goals of being competitive with ILPs and of solving problem instances on graphs derived from genome-wide data. In the future, we plan to develop and extend FixCon so that it can be used for solving problems on weighted and colored graphs.

Publications

 
 

Additional Information

Textvergrößerung und Kontrastanpassung