QUADRATIC TREE INVARIANTS FOR MULTIVALUED CHARACTERS

Studying Markov models for binary character evolution along the branches of unrooted four-trees, Cavender & Felsenstein found a set of branch-length invariants in the case of symmetric transition probabilities. This involved three expressions, K1, K2 and K3, quadratic in the predicted frequencies of occurrence of each possible configuration of character values on the four-tree: f(0000), f(1000), .... Denoting by 1, 2 and 3 the three possible completely resolved unrooted four-trees, Ki is predicted to be always zero (invariant) only if tree i generated the data, independent of the branch length of the tree. Generalization to characters other than binary is difficult because of the computational size of the problem-when the Cavender-Felsenstein method is applied directly to the case of three-valued characters, a quartic polynomial involving 22 050 terms results. Algebraic manipulation with the help of MACSYMA, however, shows that there are quadratic branch-length invariants in this case as well. Similarities in the form of the binary and trinary character invariants suggests a form for the case of four-valued characters and numerous tests confirm this. It is this case which will be of use in phylogenetic reconstruction based on nucleotide sequence data. We discuss quadratic invariants produced by other methods as well as linear invariants such as those of Lake. Generalizations to larger numbers of character values, larger trees, and wider classes of transition matrices are discussed. © 1990 Academic Press Limited All rights reserved.