Two metrics on rooted unordered trees with labels.
Two metrics on rooted unordered trees with labels.
复制标题
带标签的有根无序树上的两个度量。
DOI：
10.1186/s13015-022-00220-0
复制
发表时间：
2022-06-06
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
受精卵的早期发育可以用发育树进行数学描述。为了比较不同物种的发育树，我们需要定义树上的距离。如果分裂后的子细胞不可区分，则发育树由可能具有重复标记的根树空间表示，其中所有顶点都是无序的。如果分裂后的子细胞是部分可区分的，则发育树由可能具有重复标记的根树空间表示，其中的顶点可以是有序的或无序的。在标号可能重复的有根无序树空间上，我们定义了两个度量：最佳匹配度量和左正则度量，这两个度量比已有的方法有一定的优势。在具有有序或无序顶点的有根标号树空间上，没有度量，我们定义了一个半度量，它是最佳匹配度量的一个变体。为了计算两棵树之间的最佳匹配距离，期望时间复杂度和最坏情况时间复杂度都是，其中n是树的大小。要计算两棵树之间的左正则距离，期望的时间复杂度为，最坏情况的时间复杂度为。对于具有(完全/部分)无序顶点的有根标记树，我们定义了具有快速算法且优于现有方法的度量(半度量)。这类树也出现在发育生物学之外，这种度量方法可以应用于其他类型的树，这些树的应用更广泛，特别是在分子生物学方面。
The early development of a zygote can be mathematically described by a developmental tree. To compare developmental trees of different species, we need to define distances on trees. If children cells after a division are not distinguishable, developmental trees are represented by the space of rooted trees with possibly repeated labels, where all vertices are unordered. If children cells after a division are partially distinguishable, developmental trees are represented by the space of rooted trees with possibly repeated labels, where vertices can be ordered or unordered. On , the space of rooted unordered trees with possibly repeated labels, we define two metrics: the best-match metric and the left-regular metric, which show some advantages over existing methods. On , the space of rooted labeled trees with ordered or unordered vertices, there is no metric, and we define a semimetric, which is a variant of the best-match metric. To compute the best-match distance between two trees, the expected time complexity and worst-case time complexity are both , where n is the tree size. To compute the left-regular distance between two trees, the expected time complexity is , and the worst-case time complexity is . For rooted labeled trees with (fully/partially) unordered vertices, we define metrics (semimetric) that have fast algorithms to compute and have advantages over existing methods. Such trees also appear outside of developmental biology, and such metrics can be applied to other types of trees which have more extensive applications, especially in molecular biology.
登录
查看更多内容
影响因子：
1.1
作者：
Billera, LJ;Holmes, SP;Vogtmann, K
通讯作者：
Vogtmann, K
DOI：
10.2478/amcs-2013-0050
发表时间：
2013-09-01
影响因子：
1.9
作者：
Bogdanowicz, Damian;Giaro, Krzysztof
通讯作者：
Giaro, Krzysztof
影响因子：
6.5
作者：
Critchlow, DE;Pearl, DK;Qian, CL
通讯作者：
Qian, CL
影响因子：
1.7
作者：
Wang, Yue;Minarsky, Andrey;Morozova, Nadya
通讯作者：
Morozova, Nadya
影响因子：
9.8
作者：
Feldman JL;Geimer S;Marshall WF
通讯作者：
Marshall WF