Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time

DOI10.1016/0025-5564(82)90125-0zbMath0489.92003OpenAlexW2124594995WikidataQ113886459 ScholiaQ113886459MaRDI QIDQ1167074

Les R. Foulds, Ronald L. Graham

Publication date: 1982

Published in: Mathematical Biosciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0025-5564(82)90125-0

zbMATH Keywords

NP-completenessprotein sequencesminimal spanning treeminimal phylogeniesphylogeny of maximum parsimony

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) General biology and biomathematics (92B05) Physiological, cellular and medical topics (92Cxx)

Related Items

The computational complexity of inferring rooted phylogenies by parsimony, Computational complexity of inferring phylogenies from dissimilarity matrices, Edge lengths of trees from sequence data, A tabu search algorithm for maximum parsimony phylogeny inference, Tree enumeration modulo a consensus, Reconstructing ancestral character states under Wagner parsimony, Complexity of modification problems for best match graphs, Multicasting in the hypercube, chord and binomial graphs, PULLPRU: a practical approach to estimate phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion, A combinatorial description of the closest tree algorithm for finding evolutionary trees, Learning nonsingular phylogenies and hidden Markov models, Significance of the length of the shortest tree, A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure, The minimum evolution problem: Overview and classification, The role of complexity in comparing classifications, Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem, Counting bichromatic evolutionary trees

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial mathematics VIII. Proceedings of the Eighth Australian Conference on Combinatorial Mathematics held at Deakin University, Geelong, Australia, August 25-29, 1980
• Parallel concepts in graph theory
• The Complexity of Computing Steiner Minimal Trees
• Paths, Trees, and Flowers