×

Reconstructing the shape of a tree from observed dissimilarity data. (English) Zbl 0613.62083

Authors’ abstract: Branching structures, alias topological tree structures are fundamental to any hierarchical classification that aims to relate objects according to their similarities or dissimilarities. This paper provides a rigorous treatment of these structures, and continues previous work of Colonius and Schulze on H-structures. Thus extensive use is made of the so-called neighbors relation associated with a dissimilarity index. Arbitrary dissimilarity data are then analyzed by comparing their neighbors relations with ideal, that is, tree-like relations: if it matches an ideal relation, then one can readily construct a tree representing the data that is optimal in a certain sense. Finally, some algorithms are proposed for fitting observed data to tree-like data.
Reviewer: V.Yu.Urbakh

MSC:

62H30 Classification and discrimination; cluster analysis (statistical aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdi, H.; Barthélemy, J.-P; Luong, N. X., Tree representations of associative structures in semantic and episodic memory research, (Degreef, E.; Van Buggenhaut, J., Trends in Mathematical Psychology (1984), Elsevier: Elsevier Amsterdam/New York), 3-31
[2] Barthélemy, J.-P; Luong, N. X., Représentations arborées de mesures de dissimilarité, (Colloq. ASSU (1984), La Grande Motte: La Grande Motte France)
[3] Bock, H.-H, (Distanzmaβe zum Vergleich von Bäumen, Hierarchien und Sequenzen, Studien zur Klassifikation, Bd. 15 (1984), Indeks Verlag: Indeks Verlag Frankfurt), 52-67
[4] Buneman, P., The recovery of trees from measures of dissimilarity, (Hodson, F. R.; Kendall, D. G.; Tautu, P., Mathematics in the Archaeological and Historical Sciences (1971), Edinburgh Univ. Press: Edinburgh Univ. Press Edinburgh), 387-395
[5] Buneman, P., A note on the metric properties of trees, J. Combin. Theory Ser. B, 17, 48-50 (1974) · Zbl 0286.05102
[6] Colonius, H.; Schulze, H. H., Repräsentation nichtnumerischer Ähnlichkeitsdaten durch Baumstrukturen, Psych. Beitr., 21, 98-111 (1979)
[7] Colonius, H.; Schulze, H. H., Tree structures for proximity data, Braunschweiger Bericht. Inst. Psych., 1 (1980) · Zbl 0472.62107
[8] Colonius, H.; Schulze, H. H., Tree structures for proximity data, British J. Math. Statist. Psych., 34, 167-180 (1981) · Zbl 0472.62107
[9] Cunningham, J. P., Free trees and bidirectional trees as representations of psychological distance, J. Math. Psych., 17, 165-188 (1978) · Zbl 0383.94041
[10] Day, W. H.E, Distributions of distances between pairs of classifications, (Felsenstein, J., Numerical Taxonomy (1983), Springer-Verlag: Springer-Verlag Berlin/New York), 127-131
[11] Defays, D., Tree representations of ternary relations, J. Math. Psych., 19, 208-218 (1979) · Zbl 0397.92029
[12] Dobson, A. J., Unrooted trees for numerical taxonomy, J. Appl. Probab., 11, 32-42 (1974) · Zbl 0277.92004
[13] Dress, A., A characterization of tree-like metric spaces or how to construct an evolutionary tree (1979), Universität Bielefeld, preprint
[14] Dress, A. W.M, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces, Adv. in Math., 53, 321-402 (1984) · Zbl 0562.54041
[15] Dress, A.; Krüger, M., Parsimonious phylogenetic trees in metric spaces and simulated annealing, Advances in Applied Mathematics (1986), In press · Zbl 0637.92024
[16] Estabrook, G. F.; McMorris, F. R.; Meacham, C. A., The comparison of undirected phylogenetic trees based on subtrees of four evolutionary units, Systematic Zool., 34, 193-200 (1985)
[17] Fitch, W. M., A non-sequential method for constructing trees and hierarchical classifications, J. Mol. Evol., 18, 30-37 (1981)
[18] Meacham, C. A., A manual method for character compatibility analysis, Taxon, 30, 591-600 (1981)
[19] Meacham, C. A., A probability measure for character compatibility, Math. Biosci., 57, 1-18 (1981) · Zbl 0478.92003
[20] Peacock, D., Data handling for phylogenetic trees, (Gutfreund, H., Biochemical Evolution (1981), Cambridge Univ. Press: Cambridge Univ. Press London/New York), 88-115
[21] Robinson, D. F.; Foulds, L. R., Comparison of phylogenetic trees, Math. Biosci., 53, 131-147 (1981) · Zbl 0451.92006
[22] Rohlf, F. J., Numbering binary trees with labeled terminal vertices, Bull. Math. Biol., 45, 33-40 (1983) · Zbl 0513.05027
[23] Sattah, S.; Tversky, A., Additive similarity trees, Psychometrika, 42, 319-345 (1977)
[24] Schulze, H. H.; Colonius, H., Eine neue Methode zur Erforschung des subjektiven Lexikons, (Eckensberger, L. H., Bericht über den 31. Kongress der Deutschen Gesellschaft für Psychologie (1979), Hogrefe: Hogrefe Stuttgart), 85-88
[25] Sibley, C. G.; Ahlquist, J. E., The phylogeny of the hominoid primates, as indicated by DNA-DNA hybridization, J. Mol. Evol., 20, 2-15 (1984)
[26] Simões-Pereira, J. M.S, A note on the tree realizability of a distance matrix, J. Combin. Theory, 6, 303-310 (1969) · Zbl 0177.26903
[27] Simões-Pereira, J. M.S; Zamfirescu, C. M., Submatrices of non-tree-realizable distance matrices, Linear Algebra Appl., 44, 1-17 (1982) · Zbl 0483.05045
[28] Waterman, M. S.; Smith, T. F., On the similarity of dendrograms, J. Theoret. Biol., 73, 789-800 (1978)
[29] Waterman, M. S.; Smith, T. F.; Singh, M.; Beyer, W. A., Additive evolutionary trees, J. Theoret. Biol., 64, 199-213 (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.