A Six-Point Condition for Ordinal Matrices

Abstract

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 c _xy of M is defined by c _xy (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 phytogenies 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 0(n²) 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.

Key words:

addictive, algorithm, evolution, ordinal, phylogeny.