  Within the field of phylogenetics there is great interest in distance
measures to quantify the dissimilarity of two trees. Here, based on an idea of
Bruen and Bryant, we propose and analyze a new distance measure: the Maximum
Parsimony (MP) distance. This is based on the difference of the parsimony
scores of a single character on both trees under consideration, and the goal is
to find the character which maximizes this difference. In this article we show
that this new distance is a metric and provides a lower bound to the well-known
Subtree Prune and Regraft (SPR) distance. We also show that to compute the MP
distance it is sufficient to consider only characters that are convex on one of
the trees, and prove several additional structural properties of the distance.
On the complexity side, we prove that calculating the MP distance is in general
NP-hard, and identify an interesting island of tractability in which the
distance can be calculated in polynomial time.
