Patricia Alexandra Ebert: Inferring Phylogenetic Networks from Allowed and Forbidden (Anchored) Triples

Abstract: Evolutionary histories are often visualized by rooted networks, where leaves correspond to extant taxa and internal vertices to their ancestors (see, e.g., the tree of life). Constructing such networks, however, relies on incomplete data, typically genomic sequences of extant species. Such data can be used to infer relative evolutionary relationships, for instance that two species A and B are more closely related than A and C. This gives rise to so-called triples AB∣C, stating that the least common ancestor (LCA) of A and B is a descendant of the LCA of A and C, which itself coincides with the LCA of B and C. We further propose a generalization of triples to anchored triples which only require the LCA of A and B to be a descendant of the LCA of A and C. Then, a natural question is under which conditions there exists a phylogenetic network that displays a given set of (anchored) triples.

Somewhat surprisingly, this question has not been addressed in the literature so far. We study the concept of (anchored) triples in phylogenetic networks and provide polynomial-time algorithms to decide whether a network exists displaying a given set of (anchored) triples and, in the affirmative case, to construct such a network. Furthermore, we consider the more general setting of allowed and forbidden (anchored) triples and investigate whether there exists a phylogenetic network that displays all allowed (anchored) triples while not displaying any of the forbidden ones.