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)iml.univ-mrs.fr if you have any question, remark or suggestion.