PUB - Publikationen an der Universität Bielefeld

Steiner trees for (finite) subsets D of metric spaces S are discussed. For a given (abstract) tree topology over D Steiner interpretations in S are defined and their properties are studied. An algorithm to obtain Steiner interpretations for a given tree topology is given which is efficient if S is the (L1-) product of small metric spaces, e.g., if S is the sequence space Al over an alphabet A of small cardinality. A variant of the same algorithm can be used to minimize efficiently and exactly spin glass Hamiltonians of k-meshed graphs. The interpretation algorithm is used as an ingredient for a variant of the stochastic search algorithm called “simulated annealing” which is used to find Steiner trees for various given data sets D in various sequence spaces S = Al. For all data sets analyzed so far the trees obtained this way are shorter than or at least as short as the best ones derived using other tree construction methods. Two main features can be observed: 1. (1) Very often the shape of Steiner trees constructed this way is more or less chain-like. The trees are “long and slim.” 2. (2) Generally, the method allows to find many different Steiner trees. As a consequence, one may conclude that tree reconstruction programs should be executed in an interactive fashion so that additional biological knowledge, not explicitly represented in the data set, can be introduced at various stages of the reconstruction algorithm to reduce the number of possible solutions. Moreover, as the “Simulated Annealing” search procedure is universally applicable, one may also use this algorithm during such an interactive reconstruction program to optimize any other of the known tree reconstruction minimality principles.