1 Search Results for "White, W. Timothy J."

Document

DOI: 10.4230/LIPIcs.WABI.2018.23

Heuristic Algorithms for the Maximum Colorful Subtree Problem

Authors: Kai Dührkop, Marie A. Lataretu, W. Timothy J. White, and Sebastian Böcker

Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Abstract

In metabolomics, small molecules are structurally elucidated using tandem mass spectrometry (MS/MS); this computational task can be formulated as the Maximum Colorful Subtree problem, which is NP-hard. Unfortunately, data from a single metabolite requires us to solve hundreds or thousands of instances of this problem - and in a single Liquid Chromatography MS/MS run, hundreds or thousands of metabolites are measured. Here, we comprehensively evaluate the performance of several heuristic algorithms for the problem. Unfortunately, as is often the case in bioinformatics, the structure of the (chemically) true solution is not known to us; therefore we can only evaluate against the optimal solution of an instance. Evaluating the quality of a heuristic based on scores can be misleading: Even a slightly suboptimal solution can be structurally very different from the optimal solution, but it is the structure of a solution and not its score that is relevant for the downstream analysis. To this end, we propose a different evaluation setup: Given a set of candidate instances of which exactly one is known to be correct, the heuristic in question solves each instance to the best of its ability, producing a score for each instance, which is then used to rank the instances. We then evaluate whether the correct instance is ranked highly by the heuristic. We find that one particular heuristic consistently ranks the correct instance in a top position. We also find that the scores of the best heuristic solutions are very close to the optimal score; in contrast, the structure of the solutions can deviate significantly from the optimal structures. Integrating the heuristic allowed us to speed up computations in practice by a factor of 100-fold.

Cite as

Kai Dührkop, Marie A. Lataretu, W. Timothy J. White, and Sebastian Böcker. Heuristic Algorithms for the Maximum Colorful Subtree Problem. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duhrkop_et_al:LIPIcs.WABI.2018.23,
  author =	{D\"{u}hrkop, Kai and Lataretu, Marie A. and White, W. Timothy J. and B\"{o}cker, Sebastian},
  title =	{{Heuristic Algorithms for the Maximum Colorful Subtree Problem}},
  booktitle =	{18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Parida, Laxmi and Ukkonen, Esko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.23},
  URN =		{urn:nbn:de:0030-drops-93256},
  doi =		{10.4230/LIPIcs.WABI.2018.23},
  annote =	{Keywords: Fragmentation trees, Computational mass spectrometry}
}

Refine by Author
1 Böcker, Sebastian
1 Dührkop, Kai
1 Lataretu, Marie A.
1 White, W. Timothy J.

Refine by Classification
1 Applied computing → Computational biology
1 Applied computing → Metabolomics / metabonomics

Refine by Keyword
1 Computational mass spectrometry
1 Fragmentation trees

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "White, W. Timothy J."

Heuristic Algorithms for the Maximum Colorful Subtree Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message