A class of phylogenetic networks reconstructable from ancestral profiles

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.