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

Abstract

In this article we prove that the distance d_MP(T_1,T_2) = k between two unrooted binary phylogenetic trees T_1, T_2 on the same set of taxa can be defined by a character that is convex on one of T_1, T_2 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_1, T_2 with d_MP(T_1,T_2) = 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_1, T_2.

Tasks

Reproductions