Reconstructing tree-child networks from reticulate-edge-deleted subnetworks

Murakami, Yukihiro, van Iersel, Leo, Janssen, Remie, Jones, Mark and Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 (2019) Reconstructing tree-child networks from reticulate-edge-deleted subnetworks. Bulletin of Mathematical Biology, 81 (10). 3823–3863. ISSN 0092-8240

Preview

PDF (Published_Version) - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

Network reconstruction lies at the heart of phylogenetic research. Two well-studied classes of phylogenetic networks include tree-child networks and level-k networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-k network, the maximum number of reticulations contained in a biconnected component is k. Here, we show that level-k tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if k≥2 . Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with k reticulations.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	LivePure Connector
Date Deposited:	12 Jul 2019 07:30
Last Modified:	21 Apr 2023 00:05
URI:	https://ueaeprints.uea.ac.uk/id/eprint/71724
DOI:	10.1007/s11538-019-00641-w

Downloads

Actions (login required)

View Item