PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of amolbioBioMed CentralBiomed Central Web Sitesearchsubmit a manuscriptregisterthis articleAlgorithms for Molecular Biology : AMB
 
Algorithms Mol Biol. 2012; 7: 8.
Published online May 2, 2012. doi:  10.1186/1748-7188-7-8
PMCID: PMC3384453
Reconciling taxonomy and phylogenetic inference: formalism and algorithms for describing discord and inferring taxonomic roots
Frederick A Matsencorresponding author1 and Aaron Gallagher1
1Fred Hutchinson Cancer Research Center, Seattle, Washington, USA
corresponding authorCorresponding author.
Frederick A Matsen: matsen/at/fhcrc.org; Aaron Gallagher: agallagh/at/fhcrc.org
Received September 30, 2011; Accepted May 2, 2012.
Abstract
Background
Although taxonomy is often used informally to evaluate the results of phylogenetic inference and the root of phylogenetic trees, algorithmic methods to do so are lacking.
Results
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 to express the difference between a taxonomy and a 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.
Conclusions
The algorithms in this paper, and the associated freely-available software, will help biologists better use and understand taxonomically labeled phylogenetic trees.
Keywords: phylogenetics, taxononomy, dynamic program, branch and bound, convex coloring, algorithms
Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of
BioMed Central