Parameterized Algorithmics for Bioinformatics
Final Report Abstract
We have developed efficient & exact algorithms for numerous computationally hard problems in bioinformatics. We have given particular focus to developing algorithms which perform fast in practice. Noteworthy examples include the Cluster Editing problem, where our algorithms can solve instances exactly with tens of thousands of vertices and edge modifications; and the Maximum Colorful Subtree problem, where our code solves millions of instances every day for the interpretation of metabolomics data. All problems have direct applications in bioinformatics and biology, be it clustering, phylogenetics, biochemistry, metabolomics, or the analysis of genome rearrangements. On the theoretical side, we have developed numerous parameterized algorithms with improved worst-case running times for NP-hard problems; for other problems, we have proven that parameterized algorithms are very unlikely to exist. In bioinformatics research, the objective function of a problem is usually only a “crutch” used to find the optimum structure, whereas the value of the objective function has little or no meaning. Even elaborate heuristics for an NP-hard problem, which are capable of finding solutions with objective function value very close to the optimum, can result in solutions which are structurally very dissimilar from the optimum structure. We were able to show that this is not only a theoretical possibility, but happens regularly for real-world instances. This underlines the importance of finding exact solutions for bioinformatics problems; the structure of heuristic solutions, including local search heuristics such as Markov chain Monte Carlo, may deviate significantly from the optimal solution.
Publications
- Kernel and Fast Algorithm for Dense Triplet Inconsistency. In Proc. of Theory and Applications of Models of Computation (TAMC 2010), volume 6108 of Lect Notes Comput Sci, pages 247-257. Springer, Berlin, 2010
Sylvain Guillemot and Matthias Mnich
(See online at https://doi.org/10.1007/978-3-642-13562-0_23) - A Closer Look at the Closest String and Closest Substring Problem. In Proc. of Algorithm Engineering & Experiments (ALENEX 2011), pages 13-24. SIAM, 2011
Markus Chimani, Matthias Woste and Sebastian Böcker
(See online at https://doi.org/10.1137/1.9781611972917.2) - Automated Bond Order Assignment as an Optimization Problem. Bioinformatics, 27(5):619-625, 2011
Anna Katharina Dehof, Alexander Rurainski, Quang Bao Anh Bui, Sebastian Böcker, Hans-Peter Lenhof and Andreas Hildebrandt
(See online at https://doi.org/10.1093/bioinformatics/btq718) - Comprehensive cluster analysis with Transitivity Clustering. Nat Protocols, 6:285-295, 2011
Tobias Wittkop, Dorothea Emig, Anke Truss, Mario Albrecht, Sebastian Böcker and Jan Baumbach
(See online at https://doi.org/10.1038/nprot.2010.197) - Exact Algorithms for Cluster Editing: Evaluation and Experiments. Algorithmica, 60(2):316-334, 2011
Sebastian Böcker, Sebastian Briesemeister and Gunnar W. Klau
(See online at https://doi.org/10.1007/s00453-009-9339-7) - On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem. Inform Process Lett, 112(7):272-276, 2012
Guillaume Blin, Paola Bonizzoni, Riccardo Dondi and Florian Sikora
(See online at https://doi.org/10.1016/j.ipl.2011.12.009) - Finding and counting vertex-colored subtrees. Algorithmica, 65(4):828-844, 2013
Sylvain Guillemot and Florian Sikora
(See online at https://doi.org/10.1007/s00453-011-9600-8) - Finding Maximum Colorful Subtrees in practice. J Comput Biol, 20(4):1-11, 2013
Imran Rauf, Florian Rasche, François Nicolas and Sebastian Böcker
(See online at https://doi.org/10.1089/cmb.2012.0083) - The generalized Robinson-Foulds metric. In Proc. of Workshop on Algorithms in Bioinformatics (WABI 2013), volume 8126 of Lect Notes Comput Sci, pages 156-169. Springer, Berlin, 2013
Sebastian Böcker, Stefan Canzar and Gunnar W. Klau
(See online at https://doi.org/10.1007/978-3-642-40453-5_13) - Speedy Colorful Subtrees. In Proc. of Computing and Combinatorics Conference (COCOON 2015), volume 9198 of Lect Notes Comput Sci, pages 310-322. Springer, Berlin, 2015
W. Timothy J. White, Stephan Beyer, Kai Dührkop, Markus Chimani and Sebastian Böcker
(See online at https://doi.org/10.1007/978-3-319-21398-9_25) - Exact and heuristic algorithms for Cograph Editing. Technical report
W. Timothy J. White, Marcus Ludwig and Sebastian Böcker
- Heuristic algorithms for the Maximum Colorful Subtree problem. Technical report
Kai Dührkop, Marie A. Lataretu, W. Timothy J. White and Sebastian Böcker
