Multivariate Algorithmik für Graph- und Zeichenkettenprobleme der Bioinformatik
Bioinformatik und Theoretische Biologie
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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter 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
(Siehe online unter https://doi.org/10.4230/LIPIcs.CPM.2020.17)
