T-theory and how Buneman's construction of a network can help
by
Katharina Huber
Institute of Fundamental Sciences, Massey University, Palmerston North, New Zealand
Coauthors: A. Dress, V. Moulton

In phylogenetic analysis, X-trees, where X denotes a finite set (of taxa), are of great importance. An X-tree is a graph theoretical tree with vertex set V together with a labeling map \psi:X --> V such that every vertex of degree less or equal 2 is contained in \psi(X). Obviously, removing an edge in an X-tree induces a split S:={A, B} of X i. e. a bipartition of X into two non-empty disjoint subsets A and B of X, and any two splits S₁ and S₂ of X obtained in this way are pairwise compatible, that is, there exists some set A_i in S_i (i=1, 2) such that A₁ \cap A₂=\emptyset. In P. Buneman studied the question of when for a given system S of splits of X there exists an X-tree whose edges represent S. Introducing an interesting construction that also constitutes the basis for what we call the Buneman complex (see below), and that also immediately generalizes to arbitrary systems of splits to provide a network called the Buneman graph, he showed that it is only the systems of compatible splits that can be represented by an X-tree To any split S:={A, B} of X, assign a (pseudo) metric \delta_S:X×X --> {0, 1} with \delta_S(a, b)=0 if and only if a, b in A or a, b in B. Hence, any system S of splits naturally gives rise to a metric d_S:=\sum_{S in S}\delta_S on X. Surprisingly, the T-construction of the metric space (X, d_S) for S a system of compatible splits is also an X-tree, which corresponds to the one constructed by Buneman. Defined in a much more general setup, the T-construction of any (not neccessarily finite) metric space (X, d), denoted by T(d)=T(X, d), is the object of main interest in T-theory (see for an overview). In general, the T-construction associated to a metric space is very hard to compute, even though for a finite metric space (X, d), the space T(d) can be described as the union of all the compact faces of the (non-compact!) convex polytope {f in R^X: f(x)+f(y) >= d(x, y), for allx, y in X} . In this talk, we give a brief introduction to T-theory. For a system S of splits of X, we define and discuss the Buneman complex B(S) as introduced in . Moreover, we characterize those systems S of splits for which the cellular structure of B(S) is the same as that of T(d_S) .

[]

P. Buneman, The recovery of trees from measures of dissimilarity. In F. Hodson et al., Mathematics in the Archeological and Historical Sciences, Edinburgh University Press, 1971, pp. 387-395.

[]

A. Dress, K. Huber, V. Moulton, Some variations on a theme by Buneman, Annals of Combinatorics, 1 1997 339-352.

[]

A. Dress, V. Moulton, W. Terhalle, T-theory: An Overview, Europ. J. Combinatorics 17 1996 161-175.

[]

K. Huber, A T-theoretical approach to phylogenetic analysis and cluster analysis, Dissertation, Bielefeld 1997.

Date received: May 21, 1998

Copyright © 1998 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cabd-14.