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

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

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

Publication date: 12 January 2000

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00028-6

zbMATH Keywords

phylogenyquartet methodsdistance-based methodsevolutionary tree reconstructiondyadic closure methodshort quartet methodswitness--antiwitness method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90)

Related Items

Circular Networks from Distorted Metrics ⋮ Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges ⋮ Cyclic permutations and evolutionary trees ⋮ Average case analysis for tree labelling schemes ⋮ Comparing evolutionary distances via adaptive distance functions ⋮ On the variational distance of two trees ⋮ Fast and accurate branch support calculation for distance-based phylogenetic placements ⋮ Fast error-tolerant quartet phylogeny algorithms ⋮ Combinatorial statistics and the sciences ⋮ Unnamed Item ⋮ Learning a tree-structured Ising model in order to make predictions ⋮ Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis ⋮ Fast phylogeny reconstruction through learning of ancestral sequences ⋮ Learning Minimal Latent Directed Information Polytrees ⋮ On the hardness of inferring phylogenies from triplet-dissimilarities ⋮ Fast Error-Tolerant Quartet Phylogeny Algorithms ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ Phase transition in the sample complexity of likelihood-based phylogeny inference ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ Unnamed Item ⋮ Network delay inference from additive metrics ⋮ The impact and interplay of long and short branches on phylogenetic information content ⋮ Phase transitions in phylogeny ⋮ Rapidly computing the phylogenetic transfer index ⋮ Large-Scale Multiple Sequence Alignment and Phylogeny Estimation ⋮ Topology discovery of sparse random graphs with few participants ⋮ Inverting random functions ⋮ Ancestral state reconstruction with large numbers of sequences and edge-length estimation

Cites Work

• 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
• A few logs suffice to build (almost) all trees (I)
• 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