Computing the Distribution of a Tree Metric
Computing the Distribution of a Tree Metric
复制标题
DOI：
10.1109/tcbb.2009.32
复制
发表时间：
2009-07-01
影响因子：
4.5
通讯作者：
Steel, Mike
中科院分区：
文献类型：
--
作者：
Bryant, David;Steel, Mike
Robinson-Foulds (RF) 距离是迄今为止最广泛使用的树木之间差异性度量。尽管人们对这些距离的分布进行了 20 年的研究，但尚未描述一种明确的多项式时间算法来计算给定树周围树木的分布。在本文中，我们推导了该分布的多项式时间算法。我们展示了如何通过泊松分布来近似分布，泊松分布由给定树的“樱桃”中的叶子比例确定。我们还描述了如何使用我们的结果来导出最近提出的超级树构建的最大似然方法所需的归一化常数。
The Robinson-Foulds (RF) distance is by far the most widely used measure of dissimilarity between trees. Although the distribution of these distances has been investigated for 20 years, an algorithm that is explicitly polynomial time has yet to be described for computing the distribution for trees around a given tree. In this paper, we derive a polynomial-time algorithm for this distribution. We show how the distribution can be approximated by a Poisson distribution determined by the proportion of leaves that lie in "cherries" of the given tree. We also describe how our results can be used to derive normalization constants that are required in a recently proposed maximum likelihood approach to supertree construction.