TY - JOUR

T1 - An algorithm for reconstructing level-2 phylogenetic networks from trinets

AU - van Iersel, Leo

AU - Kole, Sjors

AU - Moulton, Vincent

AU - Nipius, Leonie

N1 - Funding Information: Research funded in part by the Netherlands Organisation for Scientific Research (NWO) Vidi grant 639.072.602.

PY - 2022/11

Y1 - 2022/11

N2 - 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.

AB - 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.

KW - Directed graph

KW - Graph algorithms

KW - Phylogenetic network

KW - Polynomial-time algorithm

KW - Subnetworks

UR - http://www.scopus.com/inward/record.url?scp=85134167416&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2022.106300

DO - 10.1016/j.ipl.2022.106300

M3 - Article

VL - 178

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 106300

ER -