Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks
Yukihiro Murakami (TU Delft - Discrete Mathematics and Optimization)
Leo van Iersel (TU Delft - Discrete Mathematics and Optimization)
Remie Janssen (TU Delft - Discrete Mathematics and Optimization)
Mark Jones (TU Delft - Discrete Mathematics and Optimization)
Vincent Moulton (University of East Anglia)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.
help_outline