Identifying phylogenetic trees

Abstract

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection C of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays C have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when C identifies an X-tree, and the second describes when a compatible subset of C is of maximum size.