A matroid associated with a phylogenetic tree

Dress, Andreas, Huber, Katharina T. and Steel, Mike (2014) A matroid associated with a phylogenetic tree. Discrete Mathematics and Theoretical Computer Science, 16 (2). pp. 41-56. ISSN 1365-8050

Preview

PDF (Dress_Huber-Steel_final) - Published Version Download (407kB) | Preview

Abstract

A (pseudo-)metric D on a finite set X is said to be a `tree metric' 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 13; up to canonical isomorphism 13; uniquely determined by D, and one does not even need all of the distances in order to fully (re-)construct the tree's edge weights in this case. Thus, it seems of some interest to investigate which subsets of X, 2 suffice to determine (`lasso') 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 `tight edge-weight lassos' for T, i.e, the minimal subsets of X, 2 that lasso the edge weights of T.

Item Type:	Article
Additional Information:	This article is free to read from the publisher's website.
Uncontrolled Keywords:	phylogenetic tree,tree metric,matroid,lasso (for a tree),cord (of a lasso)
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology
Related URLs:	https://dmtcs.episciences.org/2078
Depositing User:	Pure Connector
Date Deposited:	09 Jul 2014 12:00
Last Modified:	13 Jun 2023 08:19
URI:	https://ueaeprints.uea.ac.uk/id/eprint/49017
DOI:

Downloads

Actions (login required)

View Item