3 Search Results for "Beerenwinkel, Niko"

Document
DOI: 10.4230/LIPIcs.SEA.2024.3
Practical Minimum Path Cover

Authors: Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoretical advances exploit this idea to obtain algorithms parameterized by the number of paths of an MPC, known as the width. These results obtain fast [Mäkinen et al., TALG 2019] and even linear time [Cáceres et al., SODA 2022] algorithms in the small-width regime. In this paper, we present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new fast pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders of magnitude.
Cite as

Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu. Practical Minimum Path Cover. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{caceres_et_al:LIPIcs.SEA.2024.3,
  author =	{C\'{a}ceres, Manuel and Mumey, Brendan and Toivonen, Santeri and Tomescu, Alexandru I.},
  title =	{{Practical Minimum Path Cover}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.3},
  URN =		{urn:nbn:de:0030-drops-203687},
  doi =		{10.4230/LIPIcs.SEA.2024.3},
  annote =	{Keywords: minimum path cover, directed acyclic graph, maximum flow, parameterized algorithms, edge sparsification, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.WABI.2020.14
The Bourque Distances for Mutation Trees of Cancers

Authors: Katharina Jahn, Niko Beerenwinkel, and Louxin Zhang

Published in: LIPIcs, Volume 172, 20th International Workshop on Algorithms in Bioinformatics (WABI 2020)

Abstract
Mutation trees are rooted trees of arbitrary node degree in which each node is labeled with a mutation set. These trees, also referred to as clonal trees, are used in computational oncology to represent the mutational history of tumours. Classical tree metrics such as the popular Robinson - Foulds distance are of limited use for the comparison of mutation trees. One reason is that mutation trees inferred with different methods or for different patients often contain different sets of mutation labels. Here, we generalize the Robinson - Foulds distance into a set of distance metrics called Bourque distances for comparing mutation trees. A connection between the Robinson - Foulds distance and the nearest neighbor interchange distance is also presented.
Cite as

Katharina Jahn, Niko Beerenwinkel, and Louxin Zhang. The Bourque Distances for Mutation Trees of Cancers. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jahn_et_al:LIPIcs.WABI.2020.14,
  author =	{Jahn, Katharina and Beerenwinkel, Niko and Zhang, Louxin},
  title =	{{The Bourque Distances for Mutation Trees of Cancers}},
  booktitle =	{20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-161-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{172},
  editor =	{Kingsford, Carl and Pisanti, Nadia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2020.14},
  URN =		{urn:nbn:de:0030-drops-128039},
  doi =		{10.4230/LIPIcs.WABI.2020.14},
  annote =	{Keywords: mutation trees, clonal trees, tree distance, phylogenetic trees, tree metric, Robinson - Foulds distance, Bourque distance}
}
Document
DOI: 10.4230/DagRep.7.11.130
Addressing the Computational Challenges of Personalized Medicine (Dagstuhl Seminar 17472)

Authors: Niko Beerenwinkel, Holger Fröhlich, and Susan A. Murphy

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
This report provides an overview of the talks and the working group reports from the Dagstuhl Seminar 17472 "Addressing the Computational Challenges of Personalized Medicine". The seminar brought together leading computational scientists with different backgrounds and perspectives in order to allow for a cross-fertilizing and stimulating discussion. It thus joined expertise that is usually scattered in different research communities. In addition, selected medical researchers, pharmacogenomics researchers and behavioral scientists provided their input and established the link of the computational to the more medical aspects of personalized medicine (PM). The talks and corresponding discussion spanned mainly three areas: 1) how to enhance prediction performance of computational models for PM; 2) how to improve their interpretability; 3) how to validate and implement them in practice.
Cite as

Niko Beerenwinkel, Holger Fröhlich, and Susan A. Murphy. Addressing the Computational Challenges of Personalized Medicine (Dagstuhl Seminar 17472). In Dagstuhl Reports, Volume 7, Issue 11, pp. 130-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{beerenwinkel_et_al:DagRep.7.11.130,
  author =	{Beerenwinkel, Niko and Fr\"{o}hlich, Holger and Murphy, Susan A.},
  title =	{{Addressing the Computational Challenges of Personalized Medicine (Dagstuhl Seminar 17472)}},
  pages =	{130--141},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Beerenwinkel, Niko and Fr\"{o}hlich, Holger and Murphy, Susan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.11.130},
  URN =		{urn:nbn:de:0030-drops-86730},
  doi =		{10.4230/DagRep.7.11.130},
  annote =	{Keywords: data science, machine learning, computational modeling, bioinformatics, systems biology}
}
  • Refine by Author
  • 2 Beerenwinkel, Niko
  • 1 Cáceres, Manuel
  • 1 Fröhlich, Holger
  • 1 Jahn, Katharina
  • 1 Mumey, Brendan
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Bioinformatics
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Network flows

  • Refine by Keyword
  • 1 Bourque distance
  • 1 Robinson - Foulds distance
  • 1 algorithm engineering
  • 1 bioinformatics
  • 1 clonal trees
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact