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

Citations by Year