V. Berry, An Improved Polynomial Time Algorithm for Computing the Refined Buneman Tree (March 25, 1998).
We consider the problem of inferring a tree with positive weight edges on a set X from a dissimilarity measure on X. This problem arises in classification and more precisely in evolutionary biology, where we try to estimate the evolutionary tree, or "phylogeny", of a set of species. Several studies recently put the emphasis on inferring trees containing reliable edges [Berry and Gascuel 98, Rice et al 97]. A method first proposed by Buneman [71] was recently investigated [Berry and Gascuel 98] to obtain a tree containing almost only safe edges. However, this tree is in most cases a conservative estimator of the species' phylogeny, due to strict constraints imposed on its edges. Moulton and Steel [98] proposed a variant of the Buneman construction to obtain a less conservative tree, whose edges still verify important combinatorial constraints. Bryant and Moulton recently proposed an O(n6) polynomial time algorithm for this variant of the Buneman construction. We improve this result by providing an O(n5) algorithm for this problem that relies on an interesting technique similar to a merge sort procedure on quartets.