Making a Network Orchard by Adding Leaves

Leo van Iersel, Mark Jones, Esther Julien, Yukihiro Murakami*

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

7 Downloads (Pure)


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.

Original languageEnglish
Title of host publication23rd International Workshop on Algorithms in Bioinformatics, WABI 2023
EditorsDjamal Belazzougui, A�da Ouangraoua
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages20
ISBN (Electronic)9783959772945
Publication statusPublished - 2023
Event23rd International Workshop on Algorithms in Bioinformatics, WABI 2023 - Houston, United States
Duration: 4 Sept 20236 Sept 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference23rd International Workshop on Algorithms in Bioinformatics, WABI 2023
Country/TerritoryUnited States


  • Network
  • NP-hardness
  • Orchard Networks
  • Phylogenetics
  • Proximity Measures


Dive into the research topics of 'Making a Network Orchard by Adding Leaves'. Together they form a unique fingerprint.

Cite this