speedy_colorful_subtrees swMATH ID: 14026 Software Authors: White, W.Timothy J.; Beyer, Stephan; Dührkop, Kai; Chimani, Markus; Böcker, Sebastian Description: Speedy colorful subtrees. Fragmentation trees are a technique for identifying molecular formulas and deriving some chemical properties of metabolites – small organic molecules – solely from mass spectral data. Computing these trees involves finding exact solutions to the NP-hard {sc Maximum Colorful Subtree} problem. Existing solvers struggle to solve the large instances involved fast enough to keep up with instrument throughput, and their performance remains a hindrance to adoption in practice.{par}We attack this problem on two fronts: by combining fast and effective reduction algorithms with a strong integer linear program (ILP) formulation of the problem, we achieve overall speedups of 9.4 fold and 8.8 fold on two sets of real-world problems – without sacrificing optimality. Both approaches are, to our knowledge, the first of their kind for this problem. We also evaluate the strategy of solving {it global} problem instances, instead of first subdividing them into many {it candidate} instances as has been done in the past. Software (C++ source for our reduction program and our CPLEX/Gurobi driver program) available under LGPL at url{https://github.com/wtwhite/speedy_colorful_subtrees/}. Homepage: https://github.com/wtwhite/speedy_colorful_subtrees/ Source Code: https://github.com/wtwhite/speedy_colorful_subtrees/ Related Software: HMDB; Gurobi; GitHub; MolFind; SIRIUS; CPLEX Cited in: 3 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Speedy colorful subtrees. Zbl 1467.92078White, W. Timothy J.; Beyer, Stephan; Dührkop, Kai; Chimani, Markus; Böcker, Sebastian 2015 all top 5 Cited by 8 Authors 2 Fertin, Guillaume 2 Fradin, Julien 2 Jean, Géraldine 1 Beyer, Stephan 1 Böcker, Sebastian 1 Chimani, Markus 1 Dührkop, Kai 1 White, W. Timothy J. Cited in 1 Serial 1 Theoretical Computer Science Cited in 4 Fields 2 Computer science (68-XX) 2 Biology and other natural sciences (92-XX) 1 Combinatorics (05-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year