Tools
Tools
van Iersel, Leo, Kole, Sjors, Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435 and Nipius, Leonie
(2022)
An algorithm for reconstructing level-2 phylogenetic networks from trinets.
Information Processing Letters, 178.
ISSN 0020-0190
Preview |
PDF (vanIersel_etal_2022_IPL)
- Published Version
Available under License Creative Commons Attribution. Download (374kB) | Preview |
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.
| 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 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/85930 |
| DOI: | 10.1016/j.ipl.2022.106300 |
Downloads
Downloads per month over past year
Actions (login required)
 |
View Item |