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/}.

References in zbMATH (referenced in 1 article , 1 standard article )

Showing result 1 of 1.
Sorted by year (citations)

  1. White, W.Timothy J.; Beyer, Stephan; Dührkop, Kai; Chimani, Markus; Böcker, Sebastian: Speedy colorful subtrees (2015)