Metrics on Multilabeled Trees: Interrelationships and Diameter Bounds
Metrics on Multilabeled Trees: Interrelationships and Diameter Bounds
复制标题
DOI：
10.1109/tcbb.2010.122
复制
发表时间：
2011-07-01
影响因子：
4.5
通讯作者：
Moulton, Vincent
中科院分区：
文献类型：
--
作者：
Huber, Katharina T.;Spillner, Andreas;Moulton, Vincent
多标树或MUL-树，简称MUL-树，是指这样的树，其叶由某个非空有限集X的元素标记，使得多个叶可以由X的同一元素标记。这类树包括系统发育树和树的形状。例如，多树自然地出现在生物地理学和基因进化研究中，也出现在系统发育网络重建领域。在本文中，我们介绍了可用于比较MUL树的新度量，其中大多数度量推广了关于系统发育树和树形状的众所周知的度量。例如，可以使用这些度量来更好地理解MUL树的空间或帮助可视化MUL树的集合。此外，我们还描述了我们提出的MUL-树度量之间的一些关系，并给出了这些度量的一些新的直径界。最后，我们简要讨论了一些尚未解决的问题，并指出了MUL-树度量如何被用来定义系统发育网络空间上的度量。
Multilabeled trees or MUL-trees, for short, are trees whose leaves are labeled by elements of some nonempty finite set X such that more than one leaf may be labeled by the same element of X. This class of trees includes phylogenetic trees and tree shapes. MUL-trees arise naturally in, for example, biogeography and gene evolution studies and also in the area of phylogenetic network reconstruction. In this paper, we introduce novel metrics which may be used to compare MUL-trees, most of which generalize well-known metrics on phylogenetic trees and tree shapes. These metrics can be used, for example, to better understand the space of MUL-trees or to help visualize collections of MUL-trees. In addition, we describe some relationships between the MUL-tree metrics that we present and also give some novel diameter bounds for these metrics. We conclude by briefly discussing some open problems as well as pointing out how MUL-tree metrics may be used to define metrics on the space of phylogenetic networks.