Speedy Colorful Subtrees
Speedy Colorful Subtrees
复制标题
快速彩色子树
DOI：
10.1007/978-3-319-21398-9_25
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sebastian Böcker
中科院分区：
文献类型：
--
作者：
W. Timothy J. White;Stephan Beyer;Kai Dührkop;Markus Chimani;Sebastian Böcker
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-hardMaximum Colorful Subtreeproblem. 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.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 solvingglobalproblem instances, instead of first subdividing them into manycandidateinstances as has been done in the past. Software (C++ source for our reduction program and our CPLEX/Gurobi driver program) available under LGPL at https://github.com/wtwhite/speedy_colorful_subtrees/ .
登录
查看更多内容
影响因子：
5.8
作者：
Boecker, Sebastian;Rasche, Florian
通讯作者：
Rasche, Florian
影响因子：
7.4
作者：
Rasche, Florian;Scheubert, Kerstin;Boecker, Sebastian
通讯作者：
Boecker, Sebastian
影响因子：
1.1
作者：
Boecker, Sebastian;Liptak, Zsuzsanna
通讯作者：
Liptak, Zsuzsanna
MS/MS 数据改进了质谱法分子式的自动测定
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
M. Meringer;S. Reinker;Juan Zhang;Alban Muller
通讯作者：
Alban Muller
DOI：
10.5702/massspectrometry.s0037
发表时间：
2014-01-01
期刊：
Mass spectrometry (Tokyo, Japan)
影响因子：
--
作者：
Duhrkop, Kai;Hufsky, Franziska;Bocker, Sebastian
通讯作者：
Bocker, Sebastian