Constructing Phylogenies from Quartets: Elucidation of Eutherian Superordinal Relationships
Constructing Phylogenies from Quartets: Elucidation of Eutherian Superordinal Relationships
复制标题
从四重奏构建系统发育：阐明真兽上位关系
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
D. Pelleg
中科院分区：
文献类型：
--
作者：
A. Ben;B. Chor;D. Graur;R. Ophir;D. Pelleg
在这项工作中，我们提出了两种建造系统发育树的新方法。输入是n个分类单元上加权四重奏的列表。每个四重奏是四个分类单元的子树，其重量代表了特定拓扑的置信度。目的是构造一个带有n叶的二进制树，以使满足四重奏的总重量最大化（NP硬问题）。我们提出的第一种方法是基于几何思想。使用半决赛编程，我们将n个点嵌入n维单元球体上，同时最大化目标函数。该功能取决于四个点之间的欧几里得距离，并反映了四重奏拓扑。鉴于嵌入，我们通过执行几何聚类来构造二进制树。这个过程类似于传统的邻居加入，不同的是，更新阶段保留了几何含义：当两个邻居融合在一起时，他们的共同祖先被视为原始点的质量中心。几何算法在poly（n）时间内运行，但无法保证其输出质量。相反，我们的第二算法基于动态编程，并且可以保证找到最佳树（相对于给定的四重奏）。它的运行时间是一个适中的指数，因此可以针对n的适度值实现。我们已经实施了算法，并根据n = 15个分类单元（14个哺乳动物订单和一个外部分类单元）的真实数据进行了运行。所得的两棵树木改善了先前出版的树木，并且似乎具有生物学意义。在此数据集上，几何算法产生了一棵树，其得分是此输入集（72.1％vs. 73.4％）的最佳值的98.2％。这引起了人们的希望，即使在较大的情况下，几何方法也可以证明是可行的，而在较大的情况下，指数，动态的编程方法不再可行。
In this work we present two new approaches for constructing phylogenetic trees. The input is a list of weighted quartets over n taxa. Each quartet is a subtree on four taxa, and its weight represents a confidence level for the specific topology. The goal is to construct a binary tree with n leaves such that the total weight of the satisfied quartets is maximized (an NP hard problem). The first approach we present is based on geometric ideas. Using semidefinite programming, we embed the n points on the n-dimensional unit sphere, while maximizing an objective function. This function depends on Euclidean distances between the four points and reflects the quartet topology. Given the embedding, we construct a binary tree by performing geometric clustering. This process is similar to the traditional neighbor joining, with the difference that the update phase retains geometric meaning: When two neighbors are joined together, their common ancestor is taken to be the center of mass of the original points. The geometric algorithm runs in poly(n) time, but there are no guarantees on the quality of its output. In contrast, our second algorithm is based on dynamic programming, and it is guaranteed to find the optimal tree (with respect to the given quartets). Its running time is a modest exponential, so it can be implemented for modest values of n. We have implemented both algorithms and ran them on real data for n = 15 taxa (14 mammalian orders and an outgroup taxon). The two resulting trees improve previously published trees and seem to be of biological relevance. On this dataset, the geometric algorithm produced a tree whose score is 98.2% of the optimal value on this input set (72.1% vs. 73.4%). This gives rise to the hope that the geometric approach will prove viable even for larger cases where the exponential, dynamic programming approach is no longer feasible.