A polynomial time algorithm for constructing the refined Buneman tree (Q1808975)

Let \(X\) be a finite set, and let \({\mathcal D}(X)\) denote the set of distance functions on \(X\). An important problem in phylogenetic analysis is to approximate distances (such as those arising from biomolecular data) by tree metrics. In this paper this problem is investigated by looking for a tree construction map, that is, a map \(f:{\mathcal D}(X)\rightarrow {\mathcal D}(X)\), with \(f({\mathcal D}(X))\subseteq {\mathcal T}(X)\), where \({\mathcal T}(X)\) denotes the set of all tree metrics on \(X\), which satisfies four requirements that are desirable in biological applications. Buneman gave a method for tree construction that satisfies these requirements [Mathematics in the Archaeological and Historical Sciences (edited by F. Hodson, D. Kendall and P. Tautu), Edinburgh University Press, Edinburgh, 387-395 (1971)]. However, the price paid for continuity of the map \(f\) is that the resulting tree is often highly unresolved. The Buneman construction was modified in an attempt to address this problem by \textit{V. Moulton} and \textit{M. Steel} [Discrete Appl. Math. 91, No. 1-3, 215-233 (1999; Zbl 0914.05016)]. The resulting construction is called the refined Buneman tree. However, it is not shown whether the property: ``if \(d\in {\mathcal D}(X)\), then \(f(d)\) can be computed in time that is polynomial in \(|X |\)'' holds for this construction or not. Note that the algorithm currently used for computing the refined Buneman tree in the phylogenetic analysis (program SplitsTree) has exponential time complexity. In this paper an algorithm for computing the refined Buneman tree in polynomial time (in at most \(O(n^{6})\) time for every \(n\geq 4\), where \(n=|X |\)) is presented.