Measuring homoplasy I: comprehensive measures of maximum and minimum cost under parsimony across discrete cost matrix character types.

Here, we propose, prove mathematically and discuss maximum and minimum measures of maximum parsimony evolution across 12 discrete phylogenetic character types, classified across 4467 morphological and molecular datasets. Covered character types are: constant, binary symmetric, multistate unordered (non-additive) symmetric, multistate linear ordered symmetric, multistate non-linear ordered symmetric, binary irreversible, multistate irreversible, binary Dollo, multistate Dollo, multistate custom symmetric, binary custom asymmetric and multistate custom asymmetric characters. We summarize published solutions and provide and prove a range of new formulae for the algebraic calculation of minimum (m), maximum (g) and maximum possible (g_max) character cost for applicable character types. Algorithms for exhaustive calculation of m, g and g_max applicable to all classified character types (within computational limits on the numbers of taxa and states) are also provided. The general algorithmic solution for minimum steps (m) is identical to a minimum spanning tree on the state graph or minimum weight spanning arborescence on the state digraph. Algorithmic solutions for character g and g_max are based on matrix mathematics equivalent to optimization on the star tree, respectively for given state frequencies and all possible state frequencies meeting specified numbers of taxa and states. We show that maximizing possible cost (g_max) with given transition costs can be equivalent to maximizing, across all possible state frequency combinations, the lowest implied cost of state transitions if any one state is ancestral on the star tree, via the solution of systems of linear equations. The methods we present, implemented in the Claddis R package, extend to a comprehensive range, the fundamental character types for which homoplasy may be measured under parsimony using m, g and g_max, including extra cost (h), consistency index (ci), retention index (ri) or indices based thereon.