Combinatorics of least-squares trees

DOI10.1073/PNAS.0802089105MaRDI QIDQ3073998zbMATH OpenOpenAlexWikidataFDO

Authors Radu Mihaescu, Lior Pachter

Publication date 12 February 2011

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.2395

zbMATH Keywords

independence of irrelevant pathsminimum evolutionphylogeneticssemimultiplicative mapstree additivity

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Problems related to evolution (92D15)

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

Recommendations

• Minimum evolution using ordinary least-squares is less robust than neighbor-joining
• An algorithm for the fitting of a tree metric according to a weighted least-squares criterion
• scientific article; zbMATH DE number 1945176
• Consistent formulas for estimating the total lengths of trees
• On the consistency of the minimum evolution principle of phylogenetic inference

Cites work

• A regular decomposition of the edge-product space of phylogenetic trees
• Consistent formulas for estimating the total lengths of trees
• Independence of Irrelevant Alternatives
• On the consistency of the minimum evolution principle of phylogenetic inference
• Tree fitting: Topological recognition from ordinary least-squares edge length estimates

Cited in

(12)

• The applicability of ordinary least squares to consistently short distances between taxa in phylogenetic tree construction and the normal distribution test consequences
• Tree-tree matrices and other combinatorial problems from taxonomy
• An algorithm for the fitting of a tree metric according to a weighted least-squares criterion
• Consistent formulas for estimating the total lengths of trees
• Minimum evolution using ordinary least-squares is less robust than neighbor-joining
• Tree composition condition and moments vanishing
• Combinatorics of non-ambiguous trees
• On the combinatorics of leftist trees
• A combinatorial approach to Golomb forests
• Semi‐labeled unrooted binary tree optimization subject to nonnegativity
• Robustness of phylogenetic inference based on minimum evolution
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering

This page was built for publication: Combinatorics of least-squares trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073998)