A Caltech Library Service

Combinatorics of least squares trees

Mihaescu, Radu and Pachter, Lior (2008) Combinatorics of least squares trees. Proceedings of the National Academy of Sciences of the United States of America, 105 (36). pp. 13206-13211. ISSN 0027-8424. PMCID PMC2533170. doi:10.1073/pnas.0802089105.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper CentralArticle
Pachter, Lior0000-0002-9164-6231
Additional Information:© 2008 National Academy of Sciences. Edited by Peter J. Bickel, University of California, Berkeley, CA, and approved May 21, 2008 (received for review March 3, 2007) R.M. was supported by a National Science Foundation (NSF) Graduate Fellowship and partially by the Fannie and John Hertz. Author contributions: R.M. and L.P. designed research, performed research, and wrote the paper. The authors declare no conflict of interest. This article is a PNAS Direct Submission.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Fannie and John Hertz FoundationUNSPECIFIED
Issue or Number:36
PubMed Central ID:PMC2533170
Record Number:CaltechAUTHORS:20170306-144249240
Persistent URL:
Official Citation:Combinatorics of Least-Squares Trees Radu Mihaescu and Lior Pachter Proceedings of the National Academy of Sciences of the United States of America,Vol. 105, No. 36 (Sep. 9, 2008), pp. 13206-13211
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74805
Deposited By: Ruth Sustaita
Deposited On:07 Mar 2017 00:17
Last Modified:11 Nov 2021 05:30

Repository Staff Only: item control page