3 Search Results for "Murakami, Yukihiro"

Document
DOI: 10.4230/LIPIcs.WABI.2025.19
Which Phylogenetic Networks Are Level-k Networks with Additional Arcs? Structure and Algorithms

Authors: Takatora Suzuki and Momoko Hayamizu

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Reticulate evolution gives rise to complex phylogenetic networks, making their interpretation challenging. A typical approach is to extract trees within such networks. Since Francis and Steel’s seminal paper, "Which Phylogenetic Networks are Merely Trees with Additional Arcs?" (2015), tree-based phylogenetic networks and their support trees (spanning trees with the same root and leaf-set as a given network) have been extensively studied. However, not all phylogenetic networks are tree-based, and for the study of reticulate evolution, it is often more biologically relevant to identify support networks rather than trees. This study generalizes Hayamizu’s structure theorem, which yielded optimal algorithms for various computational problems on support trees of rooted almost-binary phylogenetic networks, to extend the theoretical framework for support trees to support networks. This allows us to obtain a direct-product characterization of each of three sets: all, minimal, and minimum support networks, for a given network. Each characterization yields optimal algorithms for counting and generating the support networks of each type. Applications include a linear-time algorithm for finding a support network with the fewest reticulations (i.e., the minimum tier). We also provide exact and heuristic algorithms for finding a support network with the minimum level, both running in exponential time but practical across a reasonably wide range of reticulation numbers.
Cite as

Takatora Suzuki and Momoko Hayamizu. Which Phylogenetic Networks Are Level-k Networks with Additional Arcs? Structure and Algorithms. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{suzuki_et_al:LIPIcs.WABI.2025.19,
  author =	{Suzuki, Takatora and Hayamizu, Momoko},
  title =	{{Which Phylogenetic Networks Are Level-k Networks with Additional Arcs? Structure and Algorithms}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.19},
  URN =		{urn:nbn:de:0030-drops-239454},
  doi =		{10.4230/LIPIcs.WABI.2025.19},
  annote =	{Keywords: Phylogenetic networks, Support networks, Level-k networks, Tier-k networks, Structure theorem, Enumeration, Optimization}
}
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.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 Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2022

  • Refine by Author
  • 2 Julien, Esther
  • 2 van Iersel, Leo
  • 1 Bernardini, Giulia
  • 1 Hayamizu, Momoko
  • 1 Jones, Mark
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

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

  • Refine by Keyword
  • 2 Phylogenetics
  • 1 Cherry Picking
  • 1 Enumeration
  • 1 Heuristic
  • 1 Hybridization
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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