Making a Network Orchard by Adding Leaves
From MaRDI portal
Publication:6435401
arXiv2305.03106MaRDI QIDQ6435401FDOQ6435401
Authors: Leo Van Iersel, Mark Jones, Esther Julien, Yukihiro Murakami 
Publication date: 4 May 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 effectiveness of our implementation.
Has companion code repository: https://github.com/estherjulien/orchardproximity
This page was built for publication: Making a Network Orchard by Adding Leaves
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435401)
