Reconstructing the shape of a tree from observed dissimilarity data

DOI10.1016/0196-8858(86)90038-2zbMath0613.62083OpenAlexW2042959539MaRDI QIDQ103560

Andreas W. M. Dress, Hans-Jürgen Bandelt, Hans-Jürgen Bandelt, Andreas W. M. Dress

Publication date: September 1986

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-8858(86)90038-2

zbMATH Keywords

algorithms hierarchical classification dissimilarity index neighbors relation topological tree structures tree-like data

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Related Items

On approximating tree spanners that are breadth first search trees ⋮ A fixed-parameter algorithm for minimum quartet inconsistency ⋮ Polynomial-Time Statistical Estimation of Species Trees Under Gene Duplication and Loss ⋮ Spanners of de Bruijn and Kautz graphs ⋮ The dual complex of \({\overline{M}_{0,n}}\) via phylogenetics ⋮ Tree spanners on chordal graphs: complexity and algorithms ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Computational complexity of inferring phylogenies from dissimilarity matrices ⋮ Generating sparse spanners for weighted graphs ⋮ A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors ⋮ Parsimonious phylogenetic trees in metric spaces and simulated annealing ⋮ Reconstructing phylogenetic trees from multipartite quartet systems ⋮ Trees, taxonomy, and strongly compatible multi-state characters ⋮ Restrictions of minimum spanner problems ⋮ Drawing polytopal graphs with {\texttt{polymake}} ⋮ Analytic solutions for three taxon ML trees with variable rates across sites ⋮ Full reconstruction of Markov models on evolutionary trees: identifiability and consistency. ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Inducibility in Binary Trees and Crossings in Random Tanglegrams ⋮ Labellable phylogenetic networks ⋮ On the facets of the secondary polytope ⋮ A high quartet distance construction ⋮ On the quartet distance given partial information ⋮ New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Tree spanners of bounded degree graphs ⋮ Unique determination of some homoplasies at hybridization events ⋮ New fixed-parameter algorithms for the minimum quartet inconsistency problem ⋮ Non-hereditary maximum parsimony trees ⋮ A few logs suffice to build (almost) all trees. II ⋮ A property tester for tree-likeness of quartet topologies ⋮ Testing consistency of quartet topologies: a parameterized approach ⋮ Injectivity and weak ternary separation ⋮ Likelihood-mapping: A simple method to visualize phylogenetic content of a sequence alignment ⋮ A phase transition for a random cluster model on phylogenetic trees. ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent ⋮ Tree representations of non-symmetric group-valued proximities ⋮ Split decomposition over an Abelian group. I: Generalities ⋮ Reconstructing a phylogenetic level-1 network from quartets ⋮ Encoding phylogenetic trees in terms of weighted quartets ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ A canonical decomposition theory for metrics on a finite set ⋮ Convex tree realizations of partitions ⋮ On sparse spanners of weighted graphs ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ The complexity of reconstructing trees from qualitative characters and subtrees ⋮ Patchworks ⋮ Polytopes with many splits and their secondary fans ⋮ Spectral analysis and a closest tree method for genetic sequences ⋮ Quartet ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Network flow spanners ⋮ Quarnet inference rules for level-1 networks ⋮ Analyzing and visualizing sequence and distance data using SPLITSTREE ⋮ On the Maximum Quartet Distance between Phylogenetic Trees ⋮ Quartets in maximal weakly compatible split systems ⋮ Set relations and set systems induced by some families of integral domains ⋮ Unique reconstruction of tree-like phylogenetic networks from distances between leaves ⋮ Characterizing weak compatibility in terms of weighted quartets ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Choosing the tree which actually best explains the data: another look at the bootstrap in phylogenetic reconstruction. ⋮ Reconstructing phylogenies from nucleotide pattern probabilities: A survey and some new results ⋮ A note on maximal hierarchies ⋮ Retractions of finite distance functions onto tree metrics ⋮ An improved bound on the maximum agreement subtree problem ⋮ Inferring evolutionary trees with strong combinatorial evidence ⋮ Distance measures in terms of substitution processes ⋮ A reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance ⋮ Topology discovery of sparse random graphs with few participants ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle ⋮ Unanimity in attribute-based preference domains ⋮ Patching up \(X\)-trees ⋮ What can and what cannot be inferred from pairwise sequence comparisons? ⋮ NP-completeness of minimum spanner problems ⋮ On the consistency of the minimum evolution principle of phylogenetic inference ⋮ Recovering a tree from the leaf colourations it generates under a Markov model ⋮ Minimum tree cost quartet puzzling

Cites Work