Speedy colorful subtrees
Autor(en): | White, W.T.J. Beyer, S. Dührkop, K. Chimani, M. Böcker, S. |
Herausgeber: | Xu, D. Du, D. |
Stichwörter: | C++ (programming language); Combinatorial mathematics; Computer software; Forestry; Integer programming; Trees (mathematics), Exact solution; Global problems; Integer linear programs; Mass spectral data; Molecular formula; Real-world problem; Reduction algorithms; Small organic molecules, Problem solving | Erscheinungsdatum: | 2015 | Herausgeber: | Springer Verlag | Journal: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Volumen: | 9198 | Startseite: | 310 | Seitenende: | 322 | Zusammenfassung: | 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 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. 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 global problem instances, instead of first subdividing them into many 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 https://github.com/wtwhite/speedy_colorful_subtrees/. © Springer International Publishing Switzerland 2015. |
Beschreibung: | Conference of 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 ; Conference Date: 4 August 2015 Through 6 August 2015; Conference Code:158929 |
ISBN: | 9783319213972 | ISSN: | 03029743 | DOI: | 10.1007/978-3-319-21398-9_25 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84951207956&doi=10.1007%2f978-3-319-21398-9_25&partnerID=40&md5=2b6b1a2b512c884333b24cdceae418c2 |
Zur Langanzeige
Seitenaufrufe
5
Letzte Woche
1
1
Letzter Monat
0
0
geprüft am 13.05.2024