An algorithm for reconstructing level-2 phylogenetic networks from trinets

van Iersel, Leo, Kole, Sjors, Moulton, Vincent ORCID: and Nipius, Leonie (2022) An algorithm for reconstructing level-2 phylogenetic networks from trinets. Information Processing Letters, 178. ISSN 0020-0190

[thumbnail of vanIersel_etal_2022_IPL]
PDF (vanIersel_etal_2022_IPL) - Published Version
Available under License Creative Commons Attribution.

Download (374kB) | Preview


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.

Item Type: Article
Additional Information: Funding Information: Research funded in part by the Netherlands Organisation for Scientific Research (NWO) Vidi grant 639.072.602.
Uncontrolled Keywords: directed graph,graph algorithms,phylogenetic network,polynomial-time algorithm,subnetworks,theoretical computer science,signal processing,information systems,computer science applications ,/dk/atira/pure/subjectarea/asjc/2600/2614
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Faculty of Science > Research Groups > Computational Biology
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 04 Jul 2022 13:30
Last Modified: 22 Apr 2023 02:22
DOI: 10.1016/j.ipl.2022.106300


Downloads per month over past year

Actions (login required)

View Item View Item