2023/05/04 by Leo van Iersel, van Iersel, Leo, Mark Jones +5
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Genomics and Phylogenetic Studies #Plant and animal studies #Plant biochemistry and biosynthesis
paper · pdf · doi:10.48550/arxiv.2305.03106
openalex publication_date 2023/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.