Click here to flash read.
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. 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.
No creative common's license