A six-point condition for ordinal matrices.
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.
Kearney
P E
PE
Department of Computer Science, University of Toronto, Ontario, Canada.
D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D004330:Drosophila / Q000502:physiology; D016014:Linear Models; D008954:Models, Biological; D010802:Phylogeny