2026-07-23T19:18:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18633 2024-03-06T11:02:19Z ddc:004 open_access

Making a Network Orchard by Adding Leaves van Iersel, Leo Jones, Mark Julien, Esther Murakami, Yukihiro Phylogenetics Network Orchard Networks Proximity Measures NP-hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leo van Iersel and Mark Jones and Esther Julien and Yukihiro Murakami 2023 Is Part Of LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2023.7 urn:nbn:de:0030-drops-186333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.7 eng https://creativecommons.org/licenses/by/4.0/legalcode