Multivariate Algorithmik für Graph- und Zeichenkettenprobleme der Bioinformatik

• Antragsteller: Professor Dr. Christian Komusiewicz
• Fachliche Zuordnung: Theoretische Informatik ; Bioinformatik und Theoretische Biologie
• Förderung: Förderung von 2015 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 289297972

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

Das Projekt MAGZ beschäftigte sich mit der Fortentwicklung des Ansatzes der multivariaten Algorithmik zur Lösung algorithmisch schwieriger Probleme, mit einem besonderen Fokus auf schwere Graph- und Zeichenkettenprobleme der Bioinformatik. Die multivariate Algorithmik versucht, strukturelle Aspekte von typischen Eingabedaten auszunutzen um so zu effizienten Algorithmen für realistische Probleminstanzen zu gelangen. Diese strukturellen Aspekte werden durch Parameter beschrieben. Auf theoretischer Seite sollten in MAGZ neue Parameter entdeckt werden, welche bisher weniger untersuchte strukturelle Aspekte der Eingabedaten beschreiben. Für Cluster Editing, ein fundamentales Problem im graphbasierten Datenclustern, konnte etwa eine neue Familie von Parametern identifiziert werden, welche sich algorithmisch ausnutzen lassen. Diese Parameter messen, wie weit entfernt die Größe k einer optimale Lösung von einer zuvor berechneten unteren Schranke ℓ für k ist. Daher sind diese Parameter kleiner als der bisher für Cluster Editing verwandte Parameter k und somit können Algorithmen, die diese Parameter verwenden, eine größere Menge an Eingabedaten effizient lösen. Auch für einige Zeichenkettenprobleme mit Anwendungen in der vergleichenden Genomik und synthetischen Biologie konnten substanziell verbesserte FPT-Algorithmen entwickelt werden. Der hier für zwei Probleme verwandte Ansatz der Übersetzung der Zeichenkettenprobleme auf ein Pfadproblem in einem Hilfsgraphen und anschließende Berechnung des Pfades mit algebraischen Algorithmen könnte für weitere schwere Zeichenkettenprobleme vielversprechend sein. Darüber hinaus konnten für eine große Reihe an Teilgraphproblemen scharfe untere Laufzeitschranken bewiesen werden. Diese haben zur Folge, dass exakte Algorithmen für diese Teilgraphprobleme mutmaßlich exponentielle Laufzeit benötigen. Auf praktischer Seite hatte MAGZ zum Ziel, mehrere multivariate Algorithmen so fortzuentwickeln, dass sie etablierten Lösungsansätzen für schwere Probleme, etwa dem ganzzahligen linearen Programmieren (ILP), ebenbürtig sind. Die entwickelten Algorithmen sollten in der Lage sein, exakte Lösungen für schwere Probleme auf Instanzen zu berechnen, die auf genomweiten Daten basieren. Für Graphprobleme bedeutet dies etwa, dass die Probleme auf Graphen mit etwa 100 000 Knoten gelöst werden sollten. Mit FixCon wurde in MAGZ ein generischer Solver für eine große Klasse an Teilgraphproblemen entwickelt. Dieser Solver erreichte das Projektziel, einen den ILPs ebenbürtigen Lösungsalgorithmus zu entwickeln, der diese Teilgraphprobleme auf genomweiten Datensätzen zufriedenstellend löst. Eine Weiterentwicklung und Erweiterung dieses Solvers, etwa für Teilgraphprobleme in gewichteten und gefärbten Graphen, ist geplant.

Projektbezogene Publikationen (Auswahl)

• 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
  
• Parameterizing Edge Modification Problems Above Lower Bounds. Theory of Computing Systems, 62(3):739–770, 2018
  R. van Bevern, V. Froese und C. Komusiewicz
  
• Tight running time lower bounds for vertex deletion problems. ACM Transactions on Computation Theory, 10(2):6:1–6:18, 2018
  C. Komusiewicz
  
• 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
  
• Enumerating connected induced subgraphs: Improved delay and experimental comparison. Discrete Applied Mathematics, 2020.
  C. Komusiewicz und F. Sommer
  
• 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
  
• Graph Motif Problems Parameterized by Dual. Journal of Graph Algorithms and Applications, 24(3):371–396, 2020
  G. Fertin und C. Komusiewicz
  
• Parameterized algorithms for Module Map problems. Discrete Applied Mathematics, 283:396–416, 2020
  F. Sommer und C. Komusiewicz
  
• 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
  
• 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