Quasi-median hulls in Hamming space are Steiner hulls

A Hamming space ΛnΛn consists of all sequences of length nn over an alphabet ΛΛ and is endowed with the Hamming distance. In particular, any set of aligned DNA sequences of fixed length constitutes a subspace of a Hamming space with respect to mismatch distance. The quasi-median operation returns for any three sequences u,v,wu,v,w the sequence which in each coordinate attains either the majority coordinate from u,v,wu,v,w or else (in the case of a tie) the coordinate of the first entry, uu; for a subset of ΛnΛn the iterative application of this operation stabilizes in its quasi-median hull. We show that for every finite tree interconnecting a given subset XX of ΛnΛn there exists a shortest realization within ΛnΛn for which all interior nodes belong to the quasi-median hull of XX. Hence the quasi-median hull serves as a Steiner hull for the Steiner problem in Hamming space.