V. Makarenkov et B. Leclerc, An algorithm for the fitting of a tree metric according to a weighted least-squares criterion, J CLASSIF, 16(1), 1999, pp. 3-26
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).