  In this paper we introduce and study three new measures for efficient
discriminative comparison of phylogenetic trees. The NNI navigation
dissimilarity $d_{nav}$ counts the steps along a "combing" of the Nearest
Neighbor Interchange (NNI) graph of binary hierarchies, providing an efficient
approximation to the (NP-hard) NNI distance in terms of "edit length". At the
same time, a closed form formula for $d_{nav}$ presents it as a weighted count
of pairwise incompatibilities between clusters, lending it the character of an
edge dissimilarity measure as well. A relaxation of this formula to a simple
count yields another measure on all trees --- the crossing dissimilarity
$d_{CM}$. Both dissimilarities are symmetric and positive definite (vanish only
between identical trees) on binary hierarchies but they fail to satisfy the
triangle inequality. Nevertheless, both are bounded below by the widely used
Robinson-Foulds metric and bounded above by a closely related true metric, the
cluster-cardinality metric $d_{CC}$. We show that each of the three proposed
new dissimilarities is computable in time $O(n^2)$ in the number of leaves $n$,
and conclude the paper with a brief numerical exploration of the distribution
over tree space of these dissimilarities in comparison with the Robinson-Foulds
metric and the more recently introduced matching-split distance.
