Parsimony Reconstructions of Ancestral States do not Depend on the Relative Distances Between Linearly-Ordered Character States

Parsimony-based algorithms for reconstructing character evolution on cladograms or phylogenetic trees have been described by various authors (e.g., Farris, 1970; Fitch, 1971; Hartigan, 1973; Moore et al., 1973; Sankoff and Rousseau, 1975; Sankoff and Cedergren, 1983; Swofford and Berlocher, 1987; Swofford and Maddison, 1987; Maddison, 1989). The algorithms of Farris (1970) and Swofford and Maddison (1987) assume that the distances between states of a character are such that the states can be linearly ordered. For example, states 0, 1 and 2 would be ordered so that state 1 is between states 0 and 2, and thus the distance between states 0 and 1 would be 1, the distance between states 1 and 2 would be 1, and the distance between 0 and 2 would be the sum of the distances between 0 and 1 and between 1 and 2, namely 2. Such a linear ordering could apply whether the character was discrete valued or continuous valued. Given such an assumption about state to state distances, a parsimony algorithm would then reconstruct the states at ancestral nodes in the cladogram so as to minimize the amount of change. We would here like to point out a simple but useful fact: for the purposes of reconstructing character evolution on a cladogram using such a parsimony algorithm, only the ordering of the states is important; the exact distances between the states are not. Thus, the same ancestral state reconstructions would be obtained for a character with three states ordered a, b and then c whether the distances between a and b and between b and c were both 1, or whether they were 0.1 and 1,000 respectively. One might expect it important to consider the difference in the size of the gap, since perhaps by suffering a little change of 0.1 between a and b in one section of the cladogram one could save distance by avoiding a large change of 1,000 between b and c in another part of the cladogram. In fact, however, a knowledge of the size of the gaps cannot help us to make a more parsimonious reconstruction: all that matters is the ordering of the states. This invariance principle arises quite naturally from the proofs for the ordered character parsimony algorithm. The algorithm for reconstructing ancestral states by parsimony operates recursively, starting at the terminal taxa and proceeding to any internal node of interest, at each stage combining information from nodes further away from the node of interest into information at the next node closer (Farris, 1970; Swofford and Maddison, 1987). The following description is a paraphrase of the algorithm of Swofford and Maddison (1987). For ease of description, imagine that we have rerooted the tree so that the node of interest is the root (this will make no difference since increases and decreases in character state cost equally). The information stored at each node is a range of contiguous states (e.g., {1, 2, 3} for a discrete-valued character or [2.3, 4.1] for a continuous-valued character). If the tree was originally dichotomous, then at each stage in the recursion the information at two nodes will be combined into information at their immediate ancestor, until we reach the node of interest, where the information from its three descendants needs to be combined (the node of interest will be trichotomous after rerooting there). To combine the state ranges of two descendant nodes into the state range of their