CAS-MPG Partner Institute for Computational Biology, Chinese Academy of Sciences Key Laboratory of Computational Biology, 320 Yue Yang Road, Shanghai, 200032, China.
School of Mathematics and Statistics, Central China Normal University, Luoyu Road 152, Wuhan, 430079, Hubei, China.
Bull Math Biol. 2018 Jun;80(6):1563-1577. doi: 10.1007/s11538-018-0413-7. Epub 2018 Mar 9.
Böcker and Dress (Adv Math 138:105-125, 1998) presented a 1-to-1 correspondence between symbolically dated rooted trees and symbolic ultrametrics. We consider the corresponding problem for unrooted trees. More precisely, given a tree T with leaf set X and a proper vertex coloring of its interior vertices, we can map every triple of three different leaves to the color of its median vertex. We characterize all ternary maps that can be obtained in this way in terms of 4- and 5-point conditions, and we show that the corresponding tree and its coloring can be reconstructed from a ternary map that satisfies those conditions. Further, we give an additional condition that characterizes whether the tree is binary, and we describe an algorithm that reconstructs general trees in a bottom-up fashion.
布克和德雷斯（Adv Math 138:105-125, 1998）提出了符号日期化有根树和符号超度量之间的一一对应关系。我们考虑了无根树的对应问题。更确切地说，给定一个有叶集 X 的树 T 和其内部顶点的适当顶点着色，我们可以将三个不同叶子的每三个组合映射到它们的中值顶点的颜色。我们根据 4-点和 5-点条件来描述所有可以以这种方式获得的三元映射，并证明从满足这些条件的三元映射可以重建相应的树及其着色。此外，我们给出了一个额外的条件来刻画树是否为二叉树，并描述了一个自底向上的算法来重建一般的树。
