Reconstructing ancestral character states under Wagner parsimony (Q1121196)

Phylogenetic trees are used to describe (hypothetical) evolutionary relationships among taxa. Given a number of operational taxonomic units (OTUs) each of which comprises character states for several characters, the problem of assigning optimal character states to the hypothetical ancestors is examined. If character states are measured on an interval scale and no a priori restrictions about the nature of the evolutionary process are imposed, the Wagner parsimony criterion can be used in order to minimize the total amount of evolutionary change needed to explain the variation in the given set of data. Several algorithms have been developed for solving this problem under the Wagner criterion. In this paper the well-known, but previously presented without proof, algorithm of \textit{J. S. Farris} [Methods for computing Wagner trees. Syst. Zool. 19, 83-92 (1970)] is considered and is shown to be correct. Since Farris' method in general obtains only a subset of all possible solutions, algorithms that discover other solutions are developed and discussed. Most of the algorithms described in the paper are contained in a program named PAUP (Phylogenetic Analysis Using Parsimony) which is available from the authors.