An algorithm for reconstructing level-2 phylogenetic networks from trinets

Leo van Iersel, Sjors Kole, Vincent Moulton, Leonie Nipius

Research output: Contribution to journalArticlepeer-review

Abstract

Evolutionary histories for species that cross with one another or exchange genetic material can be represented by leaf-labelled, directed graphs called phylogenetic networks. A major challenge in the burgeoning area of phylogenetic networks is to develop algorithms for building such networks by amalgamating small networks into a single large network. The level of a phylogenetic network is a measure of its deviation from being a tree; the higher the level of a network, the less treelike it becomes. Various algorithms have been developed for building level-1 networks from small networks. However, level-1 networks may not be able to capture the complexity of some data sets. In this paper, we present a polynomial-time algorithm for constructing a rooted binary level-2 phylogenetic network from a collection of 3-leaf networks or trinets. Moreover, we prove that the algorithm will correctly reconstruct such a network if it is given all of the trinets in the network as input. The algorithm runs in time with t the number of input trinets and n the number of leaves. We also show that there is a fundamental obstruction to constructing level-3 networks from trinets, and so new approaches will need to be developed for constructing level-3 and higher level-networks.
Original languageEnglish
Article number106300
JournalInformation Processing Letters
Volume178
Early online date5 Jul 2022
DOIs
Publication statusE-pub ahead of print - 5 Jul 2022

Keywords

  • Directed graph
  • Graph algorithms
  • Phylogenetic network
  • Polynomial-time algorithm
  • Subnetworks

Cite this