title: Combinatorics of least-squares trees.
abstract: A recurring theme in the least-squares approach to phylogenetics has been the discovery of elegant combinatorial formulas for the least-squares estimates of edge lengths. These formulas have proved useful for the development of efficient algorithms, and have also been important for understanding connections among popular phylogeny algorithms. For example, the selection criterion of the neighbor-joining algorithm is now understood in terms of the combinatorial formulas of Pauplin for estimating tree length. We highlight a phylogenetically desirable property that weighted least-squares methods should satisfy, and provide a complete characterization of methods that satisfy the property. The necessary and sufficient condition is a multiplicative four-point condition that the variance matrix needs to satisfy. The proof is based on the observation that the Lagrange multipliers in the proof of the Gauss-Markov theorem are tree-additive. Our results generalize and complete previous work on ordinary least squares, balanced minimum evolution, and the taxon-weighted variance model. They also provide a time-optimal algorithm for computation.
authors.affiliation: Departments of Mathematics and Computer Science, University of California, Berkeley, CA 94704, USA. mihaescu@berkeley.edu
authors.forename: Radu
authors.initials: R
authors.lastname: Mihaescu
authors.forename: Lior
authors.initials: L
authors.lastname: Pachter
mesh_terms: D000465:Algorithms; D016018:Least-Squares Analysis; D008954:Models, Biological; D010802:Phylogeny
references.citation: Mol Biol Evol. 1993 Sep;10(5):1073-95
references.pmid: 8412650
references.citation: J Mol Evol. 2000 Jul;51(1):41-7
references.pmid: 10903371
references.citation: Mol Biol Evol. 1987 Jul;4(4):406-25
references.pmid: 3447015
references.citation: Evolution. 1967 Sep;21(3):550-570
references.pmid: 28563688
references.citation: Mol Biol Evol. 2004 Mar;21(3):587-98
references.pmid: 14694080
references.citation: Mol Biol Evol. 1989 May;6(3):290-300
references.pmid: 2576093
references.citation: Science. 1967 Jan 20;155(3760):279-84
references.pmid: 5334057