Constructing rooted supertrees using distances

Abstract

Suppose that a family of rooted phylogenetic trees Ti with different sets Xi of leaves is given. A supertree for the family is a single rooted tree T whose leaf set is the union of all the Xi, such that the branching information in T corresponds to the branching information in all the trees Ti. This paper proposes a polynomial-time method BUILD-WITH-DISTANCES that makes essential use of distance information provided by the trees Ti to construct a rooted tree S0. When a supertree also containing the distance information exists, then S0 is a supertree. The supertree S0 often shows increased resolution over the trees found by methods that utilize only the topology of the input trees. When no supertree exists because the input trees are incompatible, several variants of the method are described which still produce trees with provable properties.