A few logs suffice to build (almost) all trees. II

DOI10.1016/S0304-3975(99)00028-6zbMath0933.68100MaRDI QIDQ1960520

László A. Székely, Péter L. Erdős, Mike A. Steel, Tandy J. Warnow

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

phylogeny; quartet methods; distance-based methods; evolutionary tree reconstruction; dyadic closure method; short quartet methods; witness--antiwitness method

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

92D15: Problems related to evolution

05C90: Applications of graph theory

Related Items

Phase transitions in phylogeny, Learning nonsingular phylogenies and hidden Markov models, On the variational distance of two trees, Inverting random functions, Cyclic permutations and evolutionary trees, Average case analysis for tree labelling schemes, On the hardness of inferring phylogenies from triplet-dissimilarities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• The complexity of reconstructing trees from qualitative characters and subtrees
• Taxonomy with confidence
• Reconstructing phylogenies from nucleotide pattern probabilities: A survey and some new results
• Recovering a tree from the leaf colourations it generates under a Markov model
• A robust model for finding optimal evolutionary tree
• Extension operations on sets of leaf-labelled trees
• Approximation algorithms for tree alignment with a given phylogeny
• Aligning sequences via an evolutionary tree
• Fast Algorithms for Finding Nearest Common Ancestors
• On the Distribution of Lengths of Evolutionary Trees
• Tree structures for proximity data
• Improved Approximation Algorithms for Tree Alignment
• A More Efficient Approximation Scheme for Tree Alignment
• Constructing big trees from short sequences
• Estimation of evolutionary distances between homologous nucleotide sequences.
• The probabilities of rooted tree-shapes generated by random bifurcation