The computational complexity of inferring rooted phylogenies by parsimony
type: Item
instance of: scholarly article
title: The computational complexity of inferring rooted phylogenies by parsimony
zbMATH Open document ID: 0607.92002
DOI: 10.1016/0025-5564(86)90161-6
author: W. H. E. Day
author: D. S. Johnson
author: David Sankoff
published in: Mathematical Biosciences
publication date: 1986-01-01T00:00:00Z
review text: In systematics, parsimony methods construct phylogenies, or evolutionary trees, in which characters evolve with the least evolutionary change. The Camin-Sokal and Dollo parsimony criteria are used to construct phylogenies from discrete characters. Variations of these problems depend on whether characters are: cladistic or qualitative, binary or multistate. The authors proved that the basic variants of these problems are all NP-complete.
Mathematics Subject Classification ID: 92B05
Mathematics Subject Classification ID: 92-08
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 92D10
Mathematics Subject Classification ID: 92D15
zbMATH DE Number: 3982966
zbMATH Keywords: computational complexity
zbMATH Keywords: rooted phylogenies
zbMATH Keywords: evolutionary trees
zbMATH Keywords: evolutionary change
zbMATH Keywords: Camin-Sokal and Dollo parsimony criteria
zbMATH Keywords: cladistic
zbMATH Keywords: qualitative
zbMATH Keywords: binary
zbMATH Keywords: multistate
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
full work available at URL: 0025-5564(86)90161-6
OpenAlex ID: W2084289491
cites work: The Steiner problem in phylogeny is NP-complete
cites work: Q4198056
cites work: Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
cites work: Parallel concepts in graph theory
description: scientific article; zbMATH DE number 3982966