Parsimonious phylogenetic trees in metric spaces and simulated annealing

DOI10.1016/0196-8858(87)90003-0MaRDI QIDQ1099115zbMATH OpenOpenAlexFDO

Authors Andreas W. M. Dress, Michael Krüger

Publication date 1987

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(87)90003-0

zbMATH Keywords

hierarchical kinship relationsinterpretation algorithmsimulated annealingspin glass Hamiltonians of k- meshed graphsSteiner interpretationsSteiner treesstochastic search algorithmsubsets of metric spacestree topology

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Other natural sciences (mathematical treatment) (92F05)

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).

Recommendations

• A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
• Melzak algorithm for phylogenetic spaces
• scientific article; zbMATH DE number 2044913
• Probability Steiner trees and maximum parsimony in phylogenetic analysis
• A subdivision approach to maximum parsimony

Cites work

• Equation of state calculations by fast computing machines
• scientific article; zbMATH DE number 3830712 (Why is no real title available?)
• scientific article; zbMATH DE number 3761270 (Why is no real title available?)
• scientific article; zbMATH DE number 3541882 (Why is no real title available?)
• scientific article; zbMATH DE number 3196612 (Why is no real title available?)
• Optimization by simulated annealing
• Proving phylogenetic trees minimal with l-clustering and set partitioning
• Reconstructing the shape of a tree from observed dissimilarity data
• Rewarding maps: On greedy optimization of set functions
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(12)

• Reconstructing the shape of a tree from observed dissimilarity data
• Was Euclid an unnecessarily sophisticated psychologist?
• Two applications of the divide \(\&\) conquer principle in the molecular sciences
• Melzak algorithm for phylogenetic spaces
• Hyperconvexity and tight-span theory for diversities
• Betweenness structures of small linear co-size
• A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure
• Characterizing local optima for maximum parsimony
• Distance-driven adaptive trees in biological metric spaces: uninformed accretion does not prevent convergence
• Probability Steiner trees and maximum parsimony in phylogenetic analysis
• Matchings and phylogenetic trees
• A characterization of uniquely representable graphs

This page was built for publication: Parsimonious phylogenetic trees in metric spaces and simulated annealing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099115)