Optimal algorithms for comparing trees with labeled leaves

DOI10.1007/BF01908061zbMath0589.62044OpenAlexW1996437477MaRDI QIDQ1074275

William H. E. Day

Publication date: 1985

Published in: Journal of Classification (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01908061

zbMATH Keywords

algorithmssimilarityclustersconsensustaxonomyrooted treesphylogenetic treesdissimilarityalgorithm designcomparingcomparing hierarchical classificationleaf labelsPidgin Algol proceduresstrict consensus tree

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to statistics (62-04) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25)

Related Items

Combining polynomial running time and fast convergence for the disk-covering method., The agreement metric for labeled binary trees, Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves, Fast algorithms for the rooted triplet distance between caterpillars, On determining if tree-based networks contain fixed trees, Neighborhoods of Phylogenetic Trees: Exact and Asymptotic Counts, Approximating geodesic tree distance, On the use of ordered sets in problems of comparison and consensus of classifications, N-trees as nestings: Complexity, similarity, and consensus, Non-shared edges and nearest neighbor interchanges revisited, Unnamed Item, Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, Cache Oblivious Algorithms for Computing the Triplet Distance between Trees, Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks, Constructing the R* consensus tree of two trees in subcubic time, Faster computation of the Robinson-Foulds distance between phylogenetic networks, New Gromov-inspired metrics on phylogenetic tree space, Discriminative measures for comparison of phylogenetic trees, A cubic-time algorithm for computing the trinet distance between level-1 networks, SUBTREE TRANSFER DISTANCE FOR DEGREE-D PHYLOGENIES, The complexity of reconstructing trees from qualitative characters and subtrees, Dissimilarity and similarity measures for comparing dendrograms and their applications, Enumeration of viral capsid assembly pathways: tree orbits under permutation group action, A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, The asymmetric median tree. --- A new model for building consensus trees, Efficiently Calculating Evolutionary Tree Measures Using SAT, Rapidly computing the phylogenetic transfer index, Distribution and asymptotic behavior of the phylogenetic transfer distance, An algebraic metric for phylogenetic trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The role of complexity in comparing classifications
• A metric and an ordering on sets
• Faithful consensus methods for n-trees
• s-consensus trees and indices
• Numbering binary trees with labeled terminal vertices
• A computationally efficient approximation to the nearest neighbor interchange metric
• Comparison of phylogenetic trees
• Consensus n-trees
• Distances between trees
• Consensus functions defined on trees
• Comparing Trees with Pendant Vertices Labelled
• On a certain distance of sets and the corresponding distance of functions