We give the first tight lower bounds on the complexity of reconstructing k-ary evolutionary trees from additive distance data. We also consider the problem under DNA-based distance estimation assumptions, where the accuracy of distance data depends on the length of the sequence and the distance. We give the first o(n2) algorithm to reconstruct trees in this context, and prove a trade-off between the length of the DNA sequences and the number of distance queries needed to reconstruct the tree. We introduce new computational models for understanding this problem, which simplify the development of algorithms. We prove lower bounds in these models which apply to the type of techniques currently in use.
展开▼
机译：我们给出了从加性距离数据重构 k 元进化树的复杂度的第一个严格的下限。我们还考虑了基于DNA的距离估计假设下的问题，其中距离数据的准确性取决于序列的长度和距离。我们给出第一个 o （ n 2 ）算法在这种情况下重建树，并证明在DNA长度之间进行权衡序列和重构树所需的距离查询数。我们引入了新的计算模型来理解此问题，从而简化了算法的开发。我们证明了这些模型的下限，适用于当前使用的技术类型。
展开▼
