Leaf-Reconstructibility of Phylogenetic Networks

Leo Van Iersel, Vincent Moulton

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)
12 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)2047-2066
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number3
DOIs
Publication statusPublished - 2018

Keywords

  • Graph reconstruction
  • Phylogenetic networks
  • Phylogenetic trees
  • Reconstruction conjecture

Fingerprint Dive into the research topics of 'Leaf-Reconstructibility of Phylogenetic Networks'. Together they form a unique fingerprint.

Cite this