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

• 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

• Beyond adjacency maximization: Scaffold filling for new string distances. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, (CPM ’17), Band 78 von LIPIcs, S. 27:1–27:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017
  L. Bulteau, G. Fertin und C. Komusiewicz
  (See online at https://doi.org/10.4230/LIPIcs.CPM.2017.27)
• Parameterizing Edge Modification Problems Above Lower Bounds. Theory of Computing Systems, 62(3):739–770, 2018
  R. van Bevern, V. Froese und C. Komusiewicz
  (See online at https://doi.org/10.1007/s00224-016-9746-5)
• Tight running time lower bounds for vertex deletion problems. ACM Transactions on Computation Theory, 10(2):6:1–6:18, 2018
  C. Komusiewicz
  (See online at https://doi.org/10.1145/3186589)
• Assessing the computational complexity of multilayer subgraph detection. Network Science, 7(2):215–241, 2019
  R. Bredereck, C. Komusiewicz, S. Kratsch, H. Molter, R. Niedermeier und M. Sorge
  (See online at https://doi.org/10.1017/nws.2019.13)
• Enumerating connected induced subgraphs: Improved delay and experimental comparison. Discrete Applied Mathematics, 2020.
  C. Komusiewicz und F. Sommer
  (See online at https://doi.org/10.1016/j.dam.2020.04.036)
• FixCon: A generic solver for fixed-cardinality subgraph problems. In Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX ’20), S. 12–26. SIAM, 2020
  C. Komusiewicz und F. Sommer
  (See online at https://doi.org/10.1137/1.9781611976007.2)
• Graph Motif Problems Parameterized by Dual. Journal of Graph Algorithms and Applications, 24(3):371–396, 2020
  G. Fertin und C. Komusiewicz
  (See online at https://doi.org/10.7155/jgaa.00538)
• Parameterized algorithms for Module Map problems. Discrete Applied Mathematics, 283:396–416, 2020
  F. Sommer und C. Komusiewicz
  (See online at https://doi.org/10.1016/j.dam.2020.01.029)
• Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping. Theoretical Computer Science, 847:27–38, 2020
  C. Komusiewicz, M. de Oliveira Oliveira und M. Zehavi
  (See online at https://doi.org/10.1016/j.tcs.2020.09.034)
• String Factorizations Under Various Collision Constraints. In Proceedings of the Thirty-First Annual Symposium on Combinatorial Pattern Matching (CPM ’20), Band 161 von LIPIcs, S. 17:1–17:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020
  N. Grüttemeier, C. Komusiewicz, N. Morawietz und F. Sommer
  (See online at https://doi.org/10.4230/LIPIcs.CPM.2020.17)