@inproceedings{e0c78929a9274f0f8d7032a9dc84a123,
title = "Making a Network Orchard by Adding Leaves",
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.",
keywords = "Network, NP-hardness, Orchard Networks, Phylogenetics, Proximity Measures",
author = "{van Iersel}, Leo and Mark Jones and Esther Julien and Yukihiro Murakami",
year = "2023",
doi = "10.4230/LIPIcs.WABI.2023.7",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Djamal Belazzougui and A�da Ouangraoua",
booktitle = "23rd International Workshop on Algorithms in Bioinformatics, WABI 2023",
address = "Germany",
note = "23rd International Workshop on Algorithms in Bioinformatics, WABI 2023 ; Conference date: 04-09-2023 Through 06-09-2023",
}