A class of phylogenetic networks reconstructable from ancestral profiles
Preprint
Abstract
Rooted phylogenetic networks provide an explicit representation of the evolutionary history of a set $X$ of sampled species. In contrast to phylogenetic trees which show only speciation events, networks can also accommodate reticulate processes (for example, hybrid evolution, endosymbiosis, and lateral gene transfer). A major goal in systematic biology is to infer evolutionary relationships, and while phylogenetic trees can be uniquely determined from various simple combinatorial data on $X$, for networks the reconstruction question is much more subtle. Here we ask when can a network be uniquely reconstructed from its `ancestral profile' (the number of paths from each ancestral vertex to each element in $X$). We show that reconstruction holds (even within the class of all networks) for a class of networks we call `orchard networks', and we provide a polynomial-time algorithm for reconstructing any orchard network from its ancestral profile. Our approach relies on establishing a structural theorem for orchard networks, which also provides for a fast (polynomial-time) algorithm to test if any given network is of orchard type. Since the class of orchard networks includes tree-sibling tree-consistent networks and tree-child networks, our result generalise reconstruction results from 2008 and 2009. Orchard networks allow for an unbounded number $k$ of reticulation vertices, in contrast to tree-sibling tree-consistent networks and tree-child networks for which $k$ is at most $2|X|-4$ and $|X|-1$, respectively.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Recovering normal networks from shortest inter-taxa distance informationJournal of Mathematical Biology, 2018
- Determining phylogenetic networks from inter-taxa distancesJournal of Mathematical Biology, 2015
- The Turbulent Network Dynamics of Microbial Evolution and the Statistical Tree of LifeJournal of Molecular Evolution, 2015
- Trinets encode tree-child and level-2 phylogenetic networksJournal of Mathematical Biology, 2013
- The global diversity of birds in space and timeNature, 2012
- On encodings of phylogenetic networks of bounded levelJournal of Mathematical Biology, 2011
- Properties of Normal Phylogenetic NetworksBulletin of Mathematical Biology, 2009
- A distance metric for a class of tree-sibling phylogenetic networksBioinformatics, 2008
- Reconstruction of certain phylogenetic networks from the genomes at their leavesJournal of Theoretical Biology, 2008
- Accumulation PhylogeniesAnnals of Combinatorics, 2006