Trinets encode orchard phylogenetic networks

Abstract

Rooted triples, rooted binary phylogenetic trees on three leaves, are sufficient to encode rooted binary phylogenetic trees. That is, if [Formula: see text] and [Formula: see text] are rooted binary phylogenetic X-trees that infer the same set of rooted triples, then [Formula: see text] and [Formula: see text] are isomorphic. However, in general, this sufficiency does not extend to rooted binary phylogenetic networks. In this paper, we show that trinets, phylogenetic network analogues of rooted triples, are sufficient to encode rooted binary orchard networks. Rooted binary orchard networks naturally generalise rooted binary tree-child networks. Moreover, we present a polynomial-time algorithm for building a rooted binary orchard network from its set of trinets. As a consequence, this algorithm affirmatively answers a previously-posed question of whether there is a polynomial-time algorithm for building a rooted binary tree-child network from the set of trinets it infers.

Keywords: Level-k networks; Orchard networks; Tree-child networks; Trinets.