2012 Feb 16 at 11:30
DC 2310
David Loker, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Users of phylogenetic methods require rooted trees, because the direction of time depends on the placement of the root. Phylogenetic trees are typically rooted through the use of an outgroup. However, this rooting mechanism is inappropriate when adding an outgroup yields a different topology for the ingroup.
We perform a formal analysis of the response of different phylogenetic algorithms to the inclusion of distant outgroups. We prove that linkage-based algorithms, which include UPGMA, do not modify the topology of the ingroup when an outgroup is included. A class of bisecting algorithms are similarly unaffected. These results are the first to provide formal guarantees on the use of outgroups for rooting phylogentic trees, guaranteeing that this rooting mechanism will not effect the structure of any ingroup when certain algorithms are used.
By contrast, the popular neighbour joining algorithm fails this property in a strong sense. Every data set can have its structure destroyed by some arbitrarily distant outlier. Moreover, including multiple outliers can lead to an arbitrary topology on the ingroup. The standard rooting approach that uses outgroups may be fundamentally unsuited for neighbour joining.