The Complexity of Constructing Evolutionary Trees Using Experiments
The Complexity of Constructing Evolutionary Trees Using Experiments
复制标题
使用实验构建进化树的复杂性
DOI：
10.1007/3-540-48224-5_12
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Anna Pagh
中科院分区：
文献类型：
--
作者：
G. Brodal;Rolf Fagerberg;Christian N. S. Pedersen;Anna Pagh
对于实验模型中构造进化树的问题，我们给出了严密的上界和下界。我们描述了一种算法，该算法在O（和logd n）时间内构建了一个n个物种的进化树，使用最多n个（log2ċd/ 2<s:1> 1 n+O(1)）个（d bbb2）实验，以及最多n个（log n+O(1)）个（d = 2）实验，其中d是树的度。这将之前的最佳上界提高了一个因子Θ（log d）。对于d = 2，先前运行时间为O（n log n）的最佳算法的实验次数上限为4n log n。通过一个明确的对手论证，我们展示了一个Ω（和logd n）下界，与我们的上界相匹配，并将之前的最佳下界改进了一个Θ（logd n）因子。我们算法的核心是构建和维护小高度的分隔树，这可能是独立的兴趣。
We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time O(nd logd n) using at most n⌈d/2⌉(log2ċd/2ċ 1 n+O(1)) experiments for d > 2, and at most n(log n+O(1)) experiments for d = 2, where d is the degree of the tree. This improves the previous best upper bound by a factor Θ(log d). For d = 2 the previously best algorithm with running time O(n log n) had a bound of 4n log n on the number of experiments. By an explicit adversary argument, we show an Ω(nd logd n) lower bound, matching our upper bounds and improving the previous best lower bound by a factor Θ(logd n). Central to our algorithm is the construction and maintenance of separator trees of small height, which may be of independent interest.