A matroid associated with a phylogenetic tree

Abstract : A (pseudo-)metric D on a finite set X is said to be a \textquotelefttree metric\textquoteright if there is a finite tree with leaf set X and non-negative edge weights so that, for all x,y ∈X, D(x,y) is the path distance in the tree between x and y. It is well known that not every metric is a tree metric. However, when some such tree exists, one can always find one whose interior edges have strictly positive edge weights and that has no vertices of degree 2, any such tree is – up to canonical isomorphism – uniquely determined by D, and one does not even need all of the distances in order to fully (re-)construct the tree\textquoterights edge weights in this case. Thus, it seems of some interest to investigate which subsets of X, 2 suffice to determine (\textquoteleftlasso\textquoteright) these edge weights. In this paper, we use the results of a previous paper to discuss the structure of a matroid that can be associated with an (unweighted) X-tree T defined by the requirement that its bases are exactly the \textquotelefttight edge-weight lassos\textquoteright for T, i.e, the minimal subsets of X, 2 that lasso the edge weights of T.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.41--55
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185618
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 17:14:02
Dernière modification le : jeudi 7 septembre 2017 - 01:03:45
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:08:35

Fichier

dmtcs-16-2-4.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185618, version 1

Collections

Citation

Andreas Dress, Katharina Huber, Mike Steel. A matroid associated with a phylogenetic tree. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (in progress) (2), pp.41--55. 〈hal-01185618〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

325