Comparing trees shapes: beyond the symmetry

GOLOBOFF P.; ARIAS J.S.; C. SZUMIK

Buenos Aires

Congreso; XXXV Internacional Meeting of the Willi Hennig Society; 2016

This paper describes two types of problems related to tree shapes, as well as algorithms that can be used to solve these problems. The first problem is that of comparing the similarity of shapes instead of merely their degree of balance; this can be used to determine, based on tree shape similarity alone, whether the taxa in two phylogenies are likely to have a correspondence (e.g. hosts and parasites with high specifity). It is shown that tree balance is insufficient for this task, and that standard measures of topological difference (e.g. Robinson-Foulds distances, SPR-distances, or retention indices of the MRPs) can be easily adapted to the problem. The second type of problem is to determine which taxa of uncertain correspondence unique to two different phylogenies could best be matched (e.g. larvae and adults of metamorphic animals, fossils known from different body parts, or hosts and parasites where the actual association is not known). This second problem can be solved by two criteria: re-labeling taxa in such a way that the number of consensus nodes is maximized, or re-labeling taxa in such a way that the sum of the number of steps in the MRP of each tree mapped onto the other is minimum.