Parametric maximum parsimonious reconstruction on trees.
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 λ¹n and λ⁰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 λ¹n (resp. greater than λ⁰n). We propose a dynamic programming algorithm computing these thresholds in a quadratic time with the size of tree.We briefly illustrate some possible applications of this work over a biological dataset. 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.
Didier
Gilles
G
Institut de Mathématiques de Luminy CNRS-UMR 6206, Campus de Luminy, Marseille Cedex 9, France. didier@iml.univ-mrs.fr
D000465:Algorithms; D009716:Numerical Analysis, Computer-Assisted; D010802:Phylogeny