Approximating minimum-length-sequence metrics: a cautionary note

In numerical taxonomy one may wish to measure the dissimilarity of classifications S and T by computing the distance between them with an appropriate metric. A minimum-length-sequence (MLS) metric requires that the user identify a set X of meaningful transformations of classifications; the MLS metric μ_x is then defined by requiring that μ_x (S,T) be the length of a shortest sequence of transformations from X that carries S into T.For a given application it may be relatively easy to identify an appropriate set X of transformations, but it may be difficult or impossible to design an efficient algorithm to compute μ_x. In this case it is natural to restrict the definition to obtain an approximation ? to the original metric μ_x such that ? has an efficient algorithm for its computation. This restriction process must be performed carefully lest the approximation fail to satisfy the metric properties. We present a general result about this problem and apply it in two ways. First we prove that a published ‘metric’ on partitions of a set in fact violates the triangle inequality and so is merely a semimetric. Then we clarify the relationship between the nearest neighbor interchange metric on labeled binary trees and the closest partition distance measure proposed by Waterman and Smith (1978).