Leaf-reconstructibility of phylogenetic networks

van Iersel, Leo and Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 (2018) Leaf-reconstructibility of phylogenetic networks. SIAM Journal on Discrete Mathematics, 32 (3). 2047–2066. ISSN 0895-4801

Preview

PDF (Accepted manuscript) - Accepted Version Download (351kB) | Preview

Abstract

An important problem in evolutionary biology is to reconstruct the evolutionary history of a set $X$ of species. This history is often represented as a phylogenetic network, that is, a connected graph with leaves labelled by elements in $X$ (for example, an evolutionary tree), which is usually also binary, i.e., all vertices have degree 1 or 3. A common approach used in phylogenetics to build a phylogenetic network on $X$ involves constructing it from networks on subsets of $X$. Here we consider the question of which (unrooted) phylogenetic networks are leaf-reconstructible, i.e., which networks can be uniquely reconstructed from the set of networks obtained from it by deleting a single leaf (its $X$-deck). This problem is closely related to the (in)famous reconstruction conjecture in graph theory but, as we shall show, presents distinct challenges. We show that some large classes of phylogenetic networks are reconstructible from their $X$-deck. This includes phylogenetic trees, binary networks containing at least one nontrivial cut-edge, and binary level-4 networks. (The level of a network measures how far it is from being a tree.) We also show that for fixed $k$, almost all binary level-$k$ phylogenetic networks are leaf-reconstructible. As an application of our results, we show that a level-3 network $N$ can be reconstructed from its quarnets, that is, 4-leaved networks that are induced by $N$ in a certain recursive fashion. Our results lead to several interesting open problems which we discuss, including the conjecture that all phylogenetic networks with at least five leaves are leaf-reconstructible.

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 > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Pure Connector
Date Deposited:	07 Jun 2018 11:31
Last Modified:	14 Jun 2023 13:25
URI:	https://ueaeprints.uea.ac.uk/id/eprint/67326
DOI:	10.1137/17M1111930

Downloads

Actions (login required)

View Item