A strengthened bound on the number of states required to characterize maximum parsimony distance

2025/06/11 by Fischer, Mareike, Kelk, Steven, Alferez, Sofia Vazquez
#Combinatorics (math.CO) #FOS: Biological sciences #FOS: Mathematics #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.2506.09888

Abstract

In this article we prove that the distance d_MP(T₁,T₂) = k between two unrooted binary phylogenetic trees T₁, T₂ on the same set of taxa can be defined by a character that is convex on one of T₁, T₂ and which has at most 2k states. This significantly improves upon the previous bound of 7k-5 states. We also show that for every k ≥ 1 there exist two trees T₁, T₂ with d_MP(T₁,T₂) = k such that at least k+1 states are necessary in any character that achieves this distance and which is convex on one of T₁, T₂. We augment these lower and upper bounds with an empirical analysis which shows that in practice significantly fewer than k+1 states are usually required.

Citations

• A branch-&-price approach to the unrooted maximum agreement forest problem
• Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
• Reduction rules for the maximum parsimony distance on phylogenetic trees
• A note on convex characters, Fibonacci numbers and exponential-time algorithms
• A linear bound on the number of states in optimal convex characters for maximum parsimony distance
• On the complexity of computing MP distance between binary phylogenetic trees
• On the Maximum Parsimony distance between phylogenetic trees
• Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology

Related

• A linear bound on the number of states in optimal convex characters for maximum parsimony distance
• On the complexity of computing MP distance between binary phylogenetic trees
• On the Maximum Parsimony distance between phylogenetic trees
• A Near-Linear Kernel for Two-Parsimony Distance
• Reduction rules for the maximum parsimony distance on phylogenetic trees