Making a Network Orchard by Adding Leaves
From MaRDI portal
Publication:6435401
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.
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)
