Institut de Mathématiques de Luminy CNRS-UMR 6206, Campus de Luminy, Marseille Cedex 9, France.
Bull Math Biol. 2011 Jul;73(7):1477-502. doi: 10.1007/s11538-010-9574-8. Epub 2010 Aug 25.
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.
我们对过渡成本参数与在系统发生树上对未知（祖先）二元字符状态{0,1}的广义最大简约重建之间的关系进行了正式研究。作为主要结果，我们表明，对于系统发生树的每个节点 n，存在两个通常混淆的阈值 λ¹n 和 λ⁰n，并且如果“10-成本”/“01-成本”的比值小于 λ¹n（或大于 λ⁰n），则存在将状态 1关联到 n（分别为状态 0 到 n）的最大简约重建。我们提出了一种动态规划算法，以树的大小计算这些阈值，时间复杂度为二次方。我们简要地在一个生物数据集上说明了这项工作的一些可能应用。特别是，这些阈值提供了一种量化重建状态的支持程度的自然方法，并确定了对于给定重建需要哪种成本方面的进化假设。
