Parsimonious phylogenetic trees in metric spaces and simulated annealing
type: Item
instance of: scholarly article
title: Parsimonious phylogenetic trees in metric spaces and simulated annealing
zbMATH Open document ID: 0637.92024
DOI: 10.1016/0196-8858(87)90003-0
author: Andreas W. M. Dress
author: Michael Krüger
published in: Advances in Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Steiner trees for finite subsets D of metric spaces S are discussed. For a given tree topology over D Steiner interpretations in S are defined and their properties are studied. An algorithm is presented to obtain Steiner interpretations for a given tree topology. 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 data sets D in various sequence spaces S. For all the 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. (From authors' abstract).
reviewed by: Ivan Křivý
Mathematics Subject Classification ID: 92F05
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92D15
zbMATH DE Number: 4039706
zbMATH Keywords: subsets of metric spaces
zbMATH Keywords: hierarchical kinship relations
zbMATH Keywords: Steiner trees
zbMATH Keywords: tree topology
zbMATH Keywords: Steiner interpretations
zbMATH Keywords: spin glass Hamiltonians of k- meshed graphs
zbMATH Keywords: interpretation algorithm
zbMATH Keywords: stochastic search algorithm
zbMATH Keywords: simulated annealing
MaRDI profile type: Publication
full work available at URL: 0196-8858(87)90003-0
OpenAlex ID: W2034145232
cites work: Reconstructing the shape of a tree from observed dissimilarity data
cites work: The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
cites work: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
cites work: Rewarding maps: On greedy optimization of set functions
cites work: Q3943876
cites work: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
cites work: Q5732992
cites work: Proving phylogenetic trees minimal with l-clustering and set partitioning
cites work: Optimization by Simulated Annealing
cites work: Equation of State Calculations by Fast Computing Machines
cites work: Q4117322
cites work: Q3036154
description: scientific article; zbMATH DE number 4039706