ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

16. Applications

1991 MS Classification: 92, 05, 51 Andreas Dress, Werner Terhalle, Universität Bielefeld, Germany The Tree of Life and Other Affine Buildings

(1) Given a field K with a valuation v, that is, a map v : K → ℝ ∪ {−∞} satisfying the conditions v(x) = −∞ ⟺ x = 0, v(x · y) = v(x) + v(y), and v(x + y) ≥ max(v(x), v(y)), the points in the associated affine building of GL(n, K) can be identified in a canonical fashion with the maps f from the set K^{n} \ {0} of non-zero vectors in K^{n} into ℝ satisfying the (including the creation of software implementing the resulting algorithms) following condition for each non-zero vector 𝔵:

f(x) = sup(v(det(x, x_{2}, …, x_{n})) − f(x_{2}) − … f(x_{n}))

where x_{2}, …, x_{n} range over K^{n} \ {0}, that is, with the minimal elements in the infinite dimensional convex polytope of all maps f from K^{n} \ {0} into ℝ satisfying the infinitely many linear inequalities

f(x_{1}) + ⋯ + f(x_{n}) ≥ v(det(x_{1}, …, x_{n})

(x_{1}, …, x_{n} ranging again over all non-zero vectors in K^{n}).

(2) In the special case n = 2, the following generalization is possible and of some interest: We may replace the set K^{2} \ {0} by any set X and the map v ∘ det by any map w : X^{2} → ℝ ∪ {−∞} satisfying the (generalized Grassmann-Pl“ucker) relation

w(x_{1}, x_{2}) + w(y_{1}, y_{2}) ≤ max(w(x_{1}, y_{1}) + w(x_{2}, y_{2}), w(x_{1}, y_{2}) + w(x_{2}, y_{1}))

for all x_{1}, x_{2}, y_{1}, y_{2} from X. Then the above construction always leads to an ℝ-tree so that the elements x ∈ X with w(x, x) ≠ −∞ represent points in that tree and the elements x ∈ X with w(x, x) = −∞ represent ends. In particular, if w(x, x) = 0 holds for all x ∈ X, the pair (X, w) is a metric space, and the above construction identifies the resulting ℝ-tree with its injective hull in the category of metric spaces as defined by Isbell; so, it shows in particular that ℝ-trees can be characterized as the injective objects in that category which are of dimension 1. In some way, in all of these constructions, a (generally contractable) space is constructed which somehow ‘fills the empty space between the elements from X’.

(3) In evolutionary theory, an important task is to unravel the phylogenetic relationships between present day (and, maybe, also some former) species. The final outcome of phylogenetic analysis is a phylogenetic tree representing the (putative) branching pattern of species evolution. The task is similar to that described above: we know the present day species, and we want to ‘fill the empty space between them’ by a tree-like structure representing their joint evolutionary history.

(4) The remarkable observation that will be discussed in the lecture is that the apparent similarity between the two tasks mentioned above is not just a superficial similarity: methods developed in the context of ℝ-trees and affine buildings have inspired methods for phylogenetic analysis which have proved helpful in replacing black-box type square-mallet computer programs by much more sensitive algorithms which allow an interactive and visually supported exploration of kinship relations -not just between species, but also between, say, proteins or other types of bio-molecules, and which can also be applied to analyze other types of (dis)similarity data regarding, say, languages, archaeological artifacts, or manuscripts.