2015/06/21 by Olivier Boes, Mareike Fischer, Boes, Olivier +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Earth and Planetary Sciences · #Data Structures and Algorithms (cs.DS) #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #cs.DS #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1506.06404
arxiv created 2015/06/21 · openalex publication_date 2015/06/21 · arxiv updated 2015/06/23 · openalex created_date 2022/09/22 · openalex updated_date 2026/07/28
Given two phylogenetic trees on the same set of taxa X, the maximum parsimony distance dMP is defined as the maximum, ranging over all characters c on X, of the absolute difference in parsimony score induced by c on the two trees. In this note we prove that for binary trees there exists a character achieving this maximum that is convex on one of the trees (i.e. the parsimony score induced on that tree is equal to the number of states in the character minus 1) and such that the number of states in the character is at most 7dMP - 5. This is the first non-trivial bound on the number of states required by optimal characters, convex or otherwise. The result potentially has algorithmic significance because, unlike general characters, convex characters with a bounded number of states can be enumerated in polynomial time.