title: Family-Joining: A Fast Distance-Based Method for Constructing Generally Labeled Trees.
abstract: The widely used model for evolutionary relationships is a bifurcating tree with all taxa/observations placed at the leaves. This is not appropriate if the taxa have been densely sampled across evolutionary time and may be in a direct ancestral relationship, or if there is not enough information to fully resolve all the branching points in the evolutionary tree. In this article, we present a fast distance-based agglomeration method called family-joining (FJ) for constructing so-called generally labeled trees in which taxa may be placed at internal vertices and the tree may contain polytomies. FJ constructs such trees on the basis of pairwise distances and a distance threshold. We tested three methods for threshold selection, FJ-AIC, FJ-BIC, and FJ-CV, which minimize Akaike information criterion, Bayesian information criterion, and cross-validation error, respectively. When compared with related methods on simulated data, FJ-BIC was among the best at reconstructing the correct tree across a wide range of simulation scenarios. FJ-BIC was applied to HIV sequences sampled from individuals involved in a known transmission chain. The FJ-BIC tree was found to be compatible with almost all transmission events. On average, internal branches in the FJ-BIC tree have higher bootstrap support than branches in the leaf-labeled bifurcating tree constructed using RAxML. 36% and 25% of the internal branches in the FJ-BIC tree and RAxML tree, respectively, have bootstrap support greater than 70%. To the best of our knowledge the method presented here is the first attempt at modeling evolutionary relationships using generally labeled trees.
authors.affiliation: Department of Computational Biology and Applied Algorithmics, Max Planck Institute for Informatics, Saarbrücken, Germany Graduate School of Computer Science, Saarland University, Saarbrücken, Germany prabhavk@mpi-inf.mpg.de.
authors.forename: Prabhav
authors.initials: P
authors.lastname: Kalaghatgi
authors.affiliation: Department of Computational Biology and Applied Algorithmics, Max Planck Institute for Informatics, Saarbrücken, Germany.
authors.forename: Nico
authors.initials: N
authors.lastname: Pfeifer
authors.affiliation: Department of Computational Biology and Applied Algorithmics, Max Planck Institute for Informatics, Saarbrücken, Germany.
authors.forename: Thomas
authors.initials: T
authors.lastname: Lengauer
mesh_terms: D000465:Algorithms; D001499:Bayes Theorem; D005075:Biological Evolution; D003198:Computer Simulation; D008957:Models, Genetic; D010802:Phylogeny; D013223:Statistics as Topic / Q000379:methods*
keywords: densely sampled taxa; distance-based phylogenies; generally labeled trees; latent tree graphical models.