University of Kentucky, Lexington, KY 40502-00227, USA.
Bull Math Biol. 2011 Nov;73(11):2627-48. doi: 10.1007/s11538-011-9640-x. Epub 2011 Mar 4.
Balanced minimum evolution (BME) is a statistically consistent distance-based method to reconstruct a phylogenetic tree from an alignment of molecular data. In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear functional over the BME polytope, the convex hull of the BME vectors obtained from Pauplin's formula applied to all binary trees. The BME method is related to the Neighbor Joining (NJ) Algorithm, now known to be a greedy optimization of the BME principle. Further, the NJ and BME algorithms have been studied previously to understand when the NJ Algorithm returns a BME tree for small numbers of taxa. In this paper we aim to elucidate the structure of the BME polytope and strengthen knowledge of the connection between the BME method and NJ Algorithm. We first prove that any subtree-prune-regraft move from a binary tree to another binary tree corresponds to an edge of the BME polytope. Moreover, we describe an entire family of faces parameterized by disjoint clades. We show that these clade-faces are smaller dimensional BME polytopes themselves. Finally, we show that for any order of joining nodes to form a tree, there exists an associated distance matrix (i.e., dissimilarity map) for which the NJ Algorithm returns the BME tree. More strongly, we show that the BME cone and every NJ cone associated to a tree T have an intersection of positive measure.
平衡最小进化法（BME）是一种基于统计学一致性的距离方法，用于从分子数据的比对中重建系统发育树。2000 年，Pauplin 表明 BME 方法等同于在 BME 多面体上优化线性函数，BME 多面体是 Pauplin 公式应用于所有二叉树得到的 BME 向量的凸包。BME 方法与近邻归并（NJ）算法有关，现在已知 NJ 算法是 BME 原理的一种贪婪优化。此外，之前已经研究了 NJ 和 BME 算法，以了解 NJ 算法在少数分类单元的情况下返回 BME 树的情况。在本文中，我们旨在阐明 BME 多面体的结构，并加强对 BME 方法和 NJ 算法之间联系的认识。我们首先证明了从二叉树到另一个二叉树的任何子树修剪重接移动都对应于 BME 多面体的一条边。此外，我们描述了由不相交支系参数化的整个面族。我们表明，这些支系面本身就是较小维度的 BME 多面体。最后，我们表明，对于任何连接节点以形成树的顺序，都存在一个相关的距离矩阵（即不相似性图），其中 NJ 算法返回 BME 树。更确切地说，我们表明树 T 的 BME 锥和每个 NJ 锥都有正测度的交集。
