A six-point condition for ordinal matrices.

Abstract

Ordinal assertions in an evolutionary context are of the form "species s is more similar to species x than the species y" and can be deduced from a distance matrix M of interspecies dissimilarities (M[s, x] < M[s, y]). Given species x and y, the ordinal binary character cxy of M is defined by cxy(s) = 1 if and only if M[s,x] < M[s, y], for all species s. In this paper we present several results concerning the inference of evolutionary trees or phylogenies from ordinal assertions. In particular, we present. A six-point condition that characterizes those distance matrices whose ordinal binary characters are pairwise compatible. This characterization is analogous to the four-point condition for additive matrices. An optimal O(n2) algorithm, where n is the number of species, for recovering a phylogeny that realizes the ordinal binary characters of a distance matrix that satisfies the six-point condition. An NP-completeness result on determining if there is a phylogeny that realizes k or more of the ordinary binary characters of a given distance matrix.