On the space of rooted trees with possibly repeated labels, where all vertices are unordered, we define two metrics: the best-match metric and the left-regular metric. On the space of rooted trees with possibly repeated labels, where vertices can be ordered or unordered, we cannot define a proper metric. However, the best-match metric can be slightly modified to become a semimetric on this space. To compute the best-match distance between two trees, the expected time complexity and worst-case complexity are both $\mathcal{O}(n^2)$, where $n$ is the tree size. To compute the left-regular distance between two trees, the expected time complexity is $\mathcal{O}(n)$, and the worst-case time complexity is $\mathcal{O}(n\log n)$. Such metrics (semimetric) can be used to compare developmental trees, which describe embryogenesis in developmental biology.
翻译:在有可能被反复标注的根树间,所有脊椎都没有顺序排列,我们定义了两种尺度:最匹配的量度和最左的量度。在可能重复标注的根树间,可以排列或未排列的量度,我们无法定义适当的量度。然而,最匹配的量度可以稍作修改,成为这个空间的半量度。要计算两棵树之间最匹配的距离,预期的时间复杂性和最差的复杂度是$\mathcal{O}(n%2)$,其中美元是树的大小。要计算两棵树之间的偏常距离,预期的时间复杂性是$\mathcal{O}(n)$,最差的时间复杂性是$\macal{O}(n)$,最差的时间复杂性是$\macal{O}(n\log n)$。这些量度(半量度)可以用来比较发育中的树木,这说明发育生物学中的胚胎生长。