Parametric parsimonious character-state reconstruction

In this paper (submitted), we give a formal study of the relationships between the transition cost parameters and the generalized maximum parsimonious reconstructions of unknown (ancestral) binary character states {0, 1} over a phylogenetic tree.

As a main result, we show there are two thresholds $\lambda^{1}_{n}$ and $\lambda^{0}_{n}$, generally confounded, associated to each node n of the phylogenetic tree and such that there exists a maximum parsimonious reconstruction associating state 1 to n (resp. state 0 to n) if the ratio ``10-cost''/``01-cost'' is smaller than $\lambda^{1}_{n}$ (resp. greater than $\lambda^{0}_{n}$). We propose a dynamic programming algorithm computing these thresholds in a time quadratic with the size of tree.

In particular, the thresholds provide a natural way to quantify the degree of support for states reconstructed as well as to determine what kind of evolutionary assumptions in terms of costs are necessary to a given reconstruction.

The C sources of the softwares computing the thresholds are freely available by this link (type "make recons" to build the software). Please contact me at didier(at) if you have any question, remark or suggestion.