The combinatorics of distance-based tree inference

Update: 2011-06-28

Description

Several popular methods for phylogenetic inference (or hierarchical clustering) are based on a matrix of pairwise distances between taxa (or any kind of objects): the objective is to construct a tree with branch lengths so that the distances between the leaves in that tree are as close as possible to the input distances. If we hold the structure (topology) of the tree fixed, in some relevant cases the optimal values for the branch lengths can be expressed using simple combinatiorial formulae. Here we define a general form for these formulae and show that they all have two desirable properties: first, the common tree reconstruction approaches (least squares, minimum evolution), when used in combination with these formulae, are guaranteed to infer the correct tree when given enough data (consistency); second, the branch lengths of all the simple (NNI) rearrangements of a tree can be calculated, optimally, in quadratric time in the size of the tree. The study presented here may form the basis for novel effcient search algorithms for distance-based tree reconstruction.

Comments

In Channel

Estimating ultra-large phylogenies and alignments

2011-06-2856:13

The combinatorics of distance-based tree inference

2011-06-2817:50

Assessing the limits of phylogenomics: can too much data be a bad thing?

2011-06-2701:04:29

Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstructions

2011-06-2720:34

Integrative analysis if environmental sequences

2011-06-2701:00:47

Mammalian phylogeny reveals recent diversi cation rate shifts

2011-06-2725:01

A generalization of Stirling numbers and distribution of phylogenetic trees

2011-06-2717:17

A Lie algebraic classification of continuous-time Markov models

2011-06-2722:34

Tree reconciliations: beyond the LCA mapping

2011-06-2719:06

Coalescent-based Species Tree Inference from Gene Tree Topologies Under Incomplete Lineage Sorting by Maximum Likelihood

2011-06-2717:54

Speciation & Extinction Rate Estimation from Phylogenetic Trees

2011-06-2722:15

Trees as representations of evolutionary information worth keeping

2011-06-2759:54

Are there alternatives to handling site-to-site rate variation in evolutionary characters

2011-06-2701:06:53

An empirical study of the effect of sequence alignment on phylogenetic analysis

2011-06-2720:41

Modelling protein evolution

2011-06-2757:39

Sequence Classification using Reference Taxonomies

2011-06-2401:03:44

Evaluating the goodness of fit between a phylogenetic model and an alignment

2011-06-2457:49

Phylodynamic inference - accounting for the interaction of evolutionary and ecological processes

2011-06-2415:40

Genome sequencing of Leishmania donovani clinical lines reveals dynamic phylogenetic variation

2011-06-2421:10

New methods of identifying fast-evolving sites in aligned sequence data

2011-06-2424:42

00:00

The combinatorics of distance-based tree inference

#box-pro-ellipsis-175783056686838{-webkit-line-clamp:2;}The combinatorics of distance-based tree inference

The combinatorics of distance-based tree inference

Steve Greenham

The combinatorics of distance-based tree inference