Parsimonious phylogenetic trees in metric spaces and simulated annealing

Dress A, Krüger M (1987)
Advances in Applied Mathematics 8(1): 8-37.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Dress, AndreasUniBi; Krüger, Michael
Abstract / Bemerkung
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.
Erscheinungsjahr
1987
Zeitschriftentitel
Advances in Applied Mathematics
Band
8
Ausgabe
1
Seite(n)
8-37
ISSN
0196-8858
Page URI
https://pub.uni-bielefeld.de/record/1655811

Zitieren

Dress A, Krüger M. Parsimonious phylogenetic trees in metric spaces and simulated annealing. Advances in Applied Mathematics. 1987;8(1):8-37.
Dress, A., & Krüger, M. (1987). Parsimonious phylogenetic trees in metric spaces and simulated annealing. Advances in Applied Mathematics, 8(1), 8-37. https://doi.org/10.1016/0196-8858(87)90003-0
Dress, A., and Krüger, M. (1987). Parsimonious phylogenetic trees in metric spaces and simulated annealing. Advances in Applied Mathematics 8, 8-37.
Dress, A., & Krüger, M., 1987. Parsimonious phylogenetic trees in metric spaces and simulated annealing. Advances in Applied Mathematics, 8(1), p 8-37.
A. Dress and M. Krüger, “Parsimonious phylogenetic trees in metric spaces and simulated annealing”, Advances in Applied Mathematics, vol. 8, 1987, pp. 8-37.
Dress, A., Krüger, M.: Parsimonious phylogenetic trees in metric spaces and simulated annealing. Advances in Applied Mathematics. 8, 8-37 (1987).
Dress, Andreas, and Krüger, Michael. “Parsimonious phylogenetic trees in metric spaces and simulated annealing”. Advances in Applied Mathematics 8.1 (1987): 8-37.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar