Parsimonious phylogenetic trees in metric spaces and simulated annealing (Q1099115): Difference between revisions

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