The combinatorics of distance-based tree inference

Fabio Pardi 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 combinatorial 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 efficient search algorithms for distance-based tree reconstruction.
Type de document :
Communication dans un congrès
Phylogenetics: New Data, New Phylogenetic Challenges, Jun 2011, Cambridge, United Kingdom. 2011, 〈https://www.newton.ac.uk/event/plgw05〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01236880
Contributeur : Fabio Pardi <>
Soumis le : mercredi 2 décembre 2015 - 11:49:18
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-01236880, version 1

Collections

Citation

Fabio Pardi. The combinatorics of distance-based tree inference. Phylogenetics: New Data, New Phylogenetic Challenges, Jun 2011, Cambridge, United Kingdom. 2011, 〈https://www.newton.ac.uk/event/plgw05〉. 〈lirmm-01236880〉

Partager

Métriques

Consultations de la notice

40