Reconstructing ancestral character states under Wagner parsimony

The problem of assigning optimal character states to the hypothetical ancestors of an evolutionary tree under the Wagner parsimony criterion is examined. A proof is provided for the correctness of Farris's well-known, but previously unproven, algorithm for solving this problem. However, the solution is not, in general, unique, and Farris's method obtains only a subset (generally only one) of the possible solutions. Algorithms that discover other solutions and that resolve ambiguities through the imposition of ancillary criteria are developed and discussed. A method for determining the optimal length of a given tree without actually assigning character states to hypothetical ancestors is described.