TY - JOUR

T1 - Leaf-Reconstructibility of Phylogenetic Networks

AU - Van Iersel, Leo

AU - Moulton, Vincent

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Graph reconstruction

KW - Phylogenetic networks

KW - Phylogenetic trees

KW - Reconstruction conjecture

UR - http://www.scopus.com/inward/record.url?scp=85053923822&partnerID=8YFLogxK

U2 - 10.1137/17M1111930

DO - 10.1137/17M1111930

M3 - Article

AN - SCOPUS:85053923822

VL - 32

SP - 2047

EP - 2066

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 3

ER -