A matroid associated with a phylogenetic tree
Andreas Dress, Katharina Huber, Mike Steel
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.
Full Text: PDF PostScript