PROPERTIES OF THE NEAREST NEIGHBOR INTERCHANGE METRIC FOR TREES OF SMALL SIZE
PROPERTIES OF THE NEAREST NEIGHBOR INTERCHANGE METRIC FOR TREES OF SMALL SIZE
复制标题
DOI：
10.1016/0022-5193(83)90341-7
复制
发表时间：
1983-01-01
影响因子：
2
通讯作者：
DAY, WHE
中科院分区：
文献类型：
--
作者：
DAY, WHE
提出交叉或最近邻交换度量用于数值分类学，以获得分类之间距离的定量度量，这些分类被建模为带有标记叶子的无根二叉树。这个指标似乎很难计算，而且人们对它的属性知之甚少。还提出了一种称为最近分区距离度量的变体，但尚未出现有效的计算算法，并且其与最近邻居交换度量的关系尚未完全理解。研究了关于最近邻交换和最近分区距离测量的四个猜想，并建立了它们对于具有多达 7 个标记顶点的树的有效性。对于这个大小范围内的树木，两个距离测量是相同的。如果某个分解属性适用于最近邻交换度量，则对于任何大小的树，在小距离处，2 个距离度量也是相同的。
The crossover or nearest neighbor interchange metric was proposed for use in numerical taxonomy to obtain a quantitative measure of distance between classifications that are modeled as unrooted binary trees with labeled leaves. This metric seems difficult to compute and its properties are poorly understood. A variant called the closest partition distance measure has also been proposed, but no efficient algorithm for its computation has yet appeared and its relationship to the nearest neighbor interchange metric is incompletely understood. Four conjectures concerning the nearest neighbor interchange and closest partition distance measures are investigated and their validity for trees with as many as 7 labeled vertices are established. For trees in this size range the 2 distance measures are identical. If a certain decomposition property holds for the nearest neighbor interchange metric, then the 2 distance measures are also identical at small distances for trees of any size.