×

Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves. (English) Zbl 0623.62051

Given two dendrograms (rooted tree diagrams) which have some but not all of their base points in common, a supertree is a dendrogram from which each of the original trees can be regarded as samples. The distinction is made between inconsistent and consistent sample trees, defined by whether or not the samples provide contradictory information about the supertree.
An algorithm for obtaining the strict consensus supertree of two consistent sample trees is presented, as are procedures for merging two inconsistent sample trees. Some suggestions for future work are made.

MSC:

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

References:

[1] ADAMS, E N (1972), ”Consensus Techniques and the Comparison of Taxonomic Trees,”Systematic Zoology, 21, 390–397 · doi:10.2307/2412432
[2] DAY, W H E (1985), ”Optimal Algorithms for Comparing Trees with Labeled Leaves,”Journal of Classification, 2, 7–28 · Zbl 0589.62044 · doi:10.1007/BF01908061
[3] FINDEN, C R, and GORDON, A D (1985), ”Obtaining Common Pruned Trees,”Journal of Classification, 2, 255–276 · doi:10.1007/BF01908078
[4] GORDON, A D (1980), ”On the Assessment and Comparison of Classifications,” inAnalvse de Données et Informatique, Ed R Tomassone, Le Chesnay: INRIA, 149–160
[5] HARDING, E F (1971), ”The Probabilities of Rooted Tree-Shapes Generated by Random Bifurcation,”Advances in Applied Probability, 3, 44–77 · Zbl 0241.92012 · doi:10.2307/1426329
[6] McMORRIS, F R, MERONK, D B, and NEUMANN, D A (1983), ”A View of Some Consensus Methods for Trees,” inNumerical Taxonomy, Ed J Felsenstein Berlin: Springer-Verlag, 122–126
[7] MAIER, D (1978), ”The Complexity of Some Problems on Subsequences and Supersequences,”Journal of the Association for Computing Machinery, 25, 322–336 · Zbl 0371.68018
[8] MARGUSH, T, and McMORRIS, F R (1981), ”Consensus n-Trees,”Bulletin of Mathematical Biology, 43, 239–244 · Zbl 0455.92019
[9] MURTAGH, F (1984), ”Counting Dendrograms: A Survey,”Discrete Applied Mathematics, 7, 191–199 · Zbl 0528.62055 · doi:10.1016/0166-218X(84)90066-0
[10] NEUMANN, D A (1983), ”Faithful Consensus Methods for n-Trees,”Mathematical Biosciences, 63, 271–287 · Zbl 0539.62073 · doi:10.1016/0025-5564(82)90043-8
[11] PHIPPS, J B (1976), ”The Numbers of Classifications,”Canadian Journal of Botany, 54, 686–688 · doi:10.1139/b76-073
[12] SIBSON, R (1972), ”Order Invariant Methods for Data Analysis,”Journal of the Royal Statistical Society, Series B, 34, 311–349 · Zbl 0253.62004
[13] SNEATH, P H A (1983), ”Philosophy and Method in Biological Classification,” inNumerical Taxonomy, Ed J Felsenstein, Berlin: Springer-Verlag, 22–37
[14] SOKAL, R R, and ROHLF, F J (1981), ”Taxonomic Congruence in the Leptopodomorpha Re-examined,”Systematic Zoology, 30, 309–325 · doi:10.2307/2413252
[15] STINEBRICKNER, R (1984), ”s-Consensus Trees and Indices,”Bulletin of Mathematical Biology, 46, 923–935 · Zbl 0546.92001
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.