Reconciling taxonomy and phylogenetic inference: formalism and algorithms for describing discord and inferring taxonomic roots.
Reconciling taxonomy and phylogenetic inference: formalism and algorithms for describing discord and inferring taxonomic roots.
复制标题
DOI：
10.1186/1748-7188-7-8
复制
发表时间：
2012-05-02
期刊：
影响因子：
--
通讯作者：
Gallagher A
中科院分区：
文献类型：
--
作者：
Matsen FA;Gallagher A
尽管分类学经常被非正式地用来评估系统发育推断的结果和系统发育树的根源，但缺乏这样做的算法方法。在本文中，我们将这些过程形式化，并开发算法来解决相关问题。特别是，我们引入了一种新的算法，它解决了一个“子着色”问题，以表示在给定等级的分类和系统发育之间的差异。该算法在当前最好算法的基础上对感兴趣的参数区域的渐近复杂性进行了改进；我们还描述了一种分支定界算法，该算法在真实数据集上的计算节省了数量级。我们还开发了一种形式化方法和一种算法，用于根据分类学来建立系统发育树。本文中的算法，以及相关的免费软件，将帮助生物学家更好地使用和理解分类标记的系统发育树。
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. 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. The algorithms in this paper, and the associated freely-available software, will help biologists better use and understand taxonomically labeled phylogenetic trees.
登录
查看更多内容
影响因子：
1.1
作者：
Hein, J;Jiang, T;Zhang, KZ
通讯作者：
Zhang, KZ
影响因子：
1.1
作者：
Moran, Shlomo;Snir, Sagi
通讯作者：
Snir, Sagi
影响因子：
5.8
作者：
Stamatakis, Alexandros
通讯作者：
Stamatakis, Alexandros
DOI：
10.1038/ismej.2011.139
发表时间：
2012-03
期刊：
The ISME journal
影响因子：
--
作者：
通讯作者：
--
影响因子：
1.1
作者：
Moran, Shlomo;Snir, Sagi
通讯作者：
Snir, Sagi