License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2023.7
URN: urn:nbn:de:0030-drops-186333
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18633/
van Iersel, Leo ;
Jones, Mark ;
Julien, Esther ;
Murakami, Yukihiro
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.
BibTeX - Entry
@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/opus/volltexte/2023/18633},
URN = {urn:nbn:de:0030-drops-186333},
doi = {10.4230/LIPIcs.WABI.2023.7},
annote = {Keywords: Phylogenetics, Network, Orchard Networks, Proximity Measures, NP-hardness}
}
