5 Search Results for "van Iersel, Leo"

Document
DOI: 10.4230/LIPIcs.WABI.2024.9
Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation

Authors: Tsuyoshi Urata, Manato Yokoyama, and Momoko Hayamizu

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
The 𝒞-Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired class 𝒞, and to find such an orientation if one exists. The problem can arise when visualising evolutionary data, for example, because popular phylogenetic network reconstruction methods such as Neighbor-Net are distance-based and thus inevitably produce undirected graphs. The complexity of 𝒞-Orientation remains open for many classes 𝒞, including binary tree-child networks, and practical methods are still lacking. In this paper, we propose an exponential but practically efficient FPT algorithm for 𝒞-Orientation, which is parameterised by the reticulation number and the maximum size of minimal basic cycles used in the computation. We also present a very fast heuristic for Tree-Child Orientation. To evaluate the empirical performance of the proposed methods, we compared their accuracy and execution time for Tree-Child Orientation with those of an exponential time 𝒞-orientation algorithm from the literature. Our experiments show that the proposed exact algorithm is significantly faster than the state-of-the-art exponential time algorithm. The proposed heuristic runs even faster but the accuracy decreases as the reticulation number increases.
Cite as

Tsuyoshi Urata, Manato Yokoyama, and Momoko Hayamizu. Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{urata_et_al:LIPIcs.WABI.2024.9,
  author =	{Urata, Tsuyoshi and Yokoyama, Manato and Hayamizu, Momoko},
  title =	{{Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.9},
  URN =		{urn:nbn:de:0030-drops-206531},
  doi =		{10.4230/LIPIcs.WABI.2024.9},
  annote =	{Keywords: Phylogenetic Networks, Tree-Child Networks, Graph Orientation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.16
Finding Maximum Common Contractions Between Phylogenetic Networks

Authors: Bertrand Marchand, Nadia Tahiri, Olivier Tremblay-Savard, and Manuel Lafond

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
In this paper, we lay the groundwork on the comparison of phylogenetic networks based on edge contractions and expansions as edit operations, as originally proposed by Robinson and Foulds to compare trees. We prove that these operations connect the space of all phylogenetic networks on the same set of leaves, even if we forbid contractions that create cycles. This allows to define an operational distance on this space, as the minimum number of contractions and expansions required to transform one network into another. We highlight the difference between this distance and the computation of the maximum common contraction between two networks. Given its ability to outline a common structure between them, which can provide valuable biological insights, we study the algorithmic aspects of the latter. We first prove that computing a maximum common contraction between two networks is NP-hard, even when the maximum degree, the size of the common contraction, or the number of leaves is bounded. We also provide lower bounds to the problem based on the Exponential-Time Hypothesis. Nonetheless, we do provide a polynomial-time algorithm for weakly galled trees, a generalization of galled trees.
Cite as

Bertrand Marchand, Nadia Tahiri, Olivier Tremblay-Savard, and Manuel Lafond. Finding Maximum Common Contractions Between Phylogenetic Networks. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{marchand_et_al:LIPIcs.WABI.2024.16,
  author =	{Marchand, Bertrand and Tahiri, Nadia and Tremblay-Savard, Olivier and Lafond, Manuel},
  title =	{{Finding Maximum Common Contractions Between Phylogenetic Networks}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.16},
  URN =		{urn:nbn:de:0030-drops-206606},
  doi =		{10.4230/LIPIcs.WABI.2024.16},
  annote =	{Keywords: Phylogenetic networks, contractions, algorithms, weakly galled trees}
}
Document
DOI: 10.4230/LIPIcs.WABI.2023.7
Making a Network Orchard by Adding Leaves

Authors: Leo van Iersel, Mark Jones, Esther Julien, and Yukihiro Murakami

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

Abstract
Phylogenetic networks are used to represent the evolutionary history of species. Recently, the new class of orchard networks was introduced, which were later shown to be interpretable as trees with additional horizontal arcs. This makes the network class ideal for capturing evolutionary histories that involve horizontal gene transfers. Here, we study the minimum number of additional leaves needed to make a network orchard. We demonstrate that computing this proximity measure for a given network is NP-hard and describe a tight upper bound. We also give an equivalent measure based on vertex labellings to construct a mixed integer linear programming formulation. Our experimental results, which include both real-world and synthetic data, illustrate the efficiency of our implementation.
Cite as

Leo van Iersel, Mark Jones, Esther Julien, and Yukihiro Murakami. Making a Network Orchard by Adding Leaves. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vaniersel_et_al:LIPIcs.WABI.2023.7,
  author =	{van Iersel, Leo and Jones, Mark and Julien, Esther and Murakami, Yukihiro},
  title =	{{Making a Network Orchard by Adding Leaves}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.7},
  URN =		{urn:nbn:de:0030-drops-186333},
  doi =		{10.4230/LIPIcs.WABI.2023.7},
  annote =	{Keywords: Phylogenetics, Network, Orchard Networks, Proximity Measures, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.69
Embedding Phylogenetic Trees in Networks of Low Treewidth

Authors: Leo van Iersel, Mark Jones, and Mathias Weller

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2^O(t²)⋅|N| time and space.
Cite as

Leo van Iersel, Mark Jones, and Mathias Weller. Embedding Phylogenetic Trees in Networks of Low Treewidth. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vaniersel_et_al:LIPIcs.ESA.2022.69,
  author =	{van Iersel, Leo and Jones, Mark and Weller, Mathias},
  title =	{{Embedding Phylogenetic Trees in Networks of Low Treewidth}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.69},
  URN =		{urn:nbn:de:0030-drops-170070},
  doi =		{10.4230/LIPIcs.ESA.2022.69},
  annote =	{Keywords: fixed-parameter tractability, treewidth, phylogenetic tree, phylogenetic network, display graph, tree containment, embedding}
}
Document
DOI: 10.4230/LIPIcs.WABI.2022.16
Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning

Authors: Giulia Bernardini, Leo van Iersel, Esther Julien, and Leen Stougie

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)

Abstract
Combining a set of phylogenetic trees into a single phylogenetic network that explains all of them is a fundamental challenge in evolutionary studies. In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of heuristics that are guaranteed to produce a network containing each of the input trees, for practical-size datasets. The main contribution of this paper is the design and training of a machine learning model that captures essential information on the structure of the input trees and guides the algorithms towards better solutions. This is one of the first applications of machine learning to phylogenetic studies, and we show its promise with a proof-of-concept experimental study conducted on both simulated and real data consisting of binary trees with no missing taxa.
Cite as

Giulia Bernardini, Leo van Iersel, Esther Julien, and Leen Stougie. Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bernardini_et_al:LIPIcs.WABI.2022.16,
  author =	{Bernardini, Giulia and van Iersel, Leo and Julien, Esther and Stougie, Leen},
  title =	{{Reconstructing Phylogenetic Networks via Cherry Picking and Machine Learning}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.16},
  URN =		{urn:nbn:de:0030-drops-170507},
  doi =		{10.4230/LIPIcs.WABI.2022.16},
  annote =	{Keywords: Phylogenetics, Hybridization, Cherry Picking, Machine Learning, Heuristic}
}
  • Refine by Author
  • 3 van Iersel, Leo
  • 2 Jones, Mark
  • 2 Julien, Esther
  • 1 Bernardini, Giulia
  • 1 Hayamizu, Momoko
  • Show More...

  • Refine by Classification
  • 2 Applied computing → Bioinformatics
  • 2 Applied computing → Biological networks
  • 1 Applied computing → Computational biology
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Trees
  • Show More...

  • Refine by Keyword
  • 2 Phylogenetics
  • 1 Cherry Picking
  • 1 Graph Orientation Algorithms
  • 1 Heuristic
  • 1 Hybridization
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2022
  • 2 2024
  • 1 2023

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