Two Metrics on Rooted Unordered Trees with Labels

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. On this space, we define two metrics: the best-match metric and the left-regular metric, which show some advantages over existing methods. 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. This space cannot have a metric. Instead, 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 $\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)$.