speedy_colorful_subtrees
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/}.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
Sorted by year (- Fertin, Guillaume; Fradin, Julien; Jean, Géraldine: The \textscMaximumColorful Arborescence problem: how (computationally) hard can it be? (2021)
- Fertin, Guillaume; Fradin, Julien; Jean, Géraldine: Algorithmic aspects of the maximum colorful arborescence problem (2017)
- White, W. Timothy J.; Beyer, Stephan; Dührkop, Kai; Chimani, Markus; Böcker, Sebastian: Speedy colorful subtrees (2015)