An algorithm for the fitting of a tree metric according to a weighted least-squares criterion

The fitting of a tree metric to a given dissimilarity with a weighted least-squares criterion is considered. According to several authors, this criterion is well adapted to the problem of inferring evolutionary trees, as, for instance, phylogenies. Because the problem is already known to be NP-hard for the unweighted least-squares formulation, the weighted case would profit from good heuristics. The heuristics proposed in the literature in the unweighted case do not typically generalize to the weighted case, for instance to phylogenetic models incorporating an evolutionary noise which is not proportional to the distance values. We propose an original method for the construction of a tree by stepwise addition, with a calculation of the lengths of the new edges according to a least-squares criterion allowing the introduction of arbitrary weights. This procedure is tested on some examples and compared, on the basis of a classical scheme already used several times in the literature, to classical unweighted methods, and to the weighted methods recently proposed by Gonnet (1994) and by Felsenstein (1997).