2011/09/25 by F. A. Matsen, Matsen, Frederick A., Aaron Gallagher +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Earth and Planetary Sciences · #Data Structures and Algorithms (cs.DS) #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #cs.DS #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1109.5423
Version submitted to Algorithms for Molecular Biology. A number of fixes from previous version
openalex publication_date 2011/09/25 · arxiv created 2011/10/01 · arxiv updated 2011/10/04 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Although taxonomy is often used informally to evaluate the results of phylogenetic inference and find the root of phylogenetic trees, algorithmic methods to do so are lacking. In this paper we formalize these procedures and develop algorithms to solve the relevant problems. In particular, we introduce a new algorithm that solves a "subcoloring" problem for expressing the difference between the taxonomy and phylogeny at a given rank. This algorithm improves upon the current best algorithm in terms of asymptotic complexity for the parameter regime of interest; we also describe a branch-and-bound algorithm that saves orders of magnitude in computation on real data sets. We also develop a formalism and an algorithm for rooting phylogenetic trees according to a taxonomy. All of these algorithms are implemented in freely-available software.