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 criter ion 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 profi t from good heuristics. The heuristics proposed in the literature in the un weighted case do not typically generalize to the weighted case, for instanc e to phylogenetic models incorporating an evolutionary noise which is not p roportional to the distance values. We propose an original method for the c onstruction of a tree by stepwise addition, with a calculation of the lengt hs of the new edges according to a least-squares criterion allowing the int roduction of arbitrary weights. This procedure is tested on some examples a nd compared, on the basis of a classical scheme already used several times in the literature, to classical unweighted methods, and to the weighted met hods recently proposed by Gonnet (1994) and by Felsenstein (1997).