Accuracy of parsimony reconstruction under a molecular clock
Let $r \ge 5$ and let $T$ be a finite rooted binary tree (every internal vertex has exactly two children) with root $\rho$ and at least two leaves. Give each edge $e$ a length $\ell_e \ge 0$ such that every path from $\rho$ to a leaf has the same total length $H$ (a molecular clock). Generate states $\sigma_v \in \{1, \dots, r\}$ at the vertices by the symmetric (Neyman) $r$-state model: $\sigma_\rho$ is uniform, and along an edge of length $\ell$ the state evolves for time $\ell$ as the continuous-time Markov chain that jumps at rate $1$ to a uniformly chosen different state, independently on different edges given the parent states. Every leaf then has the root's state with probability $$q_r(H) = \frac{1}{r} + \frac{r-1}{r} \exp\!\left(-\frac{rH}{r-1}\right).$$ From the leaf states, the Fitch algorithm computes sets $S_v$: $S_x = \{\sigma_x\}$ at a leaf $x$, and $S_v = S_u \cap S_w$ if this is nonempty and $S_v = S_u \cup S_w$ otherwise, at an internal vertex $v$ with children $u$ and $w$. Let $\widehat\sigma_\rho$ be chosen uniformly from $S_\rho$. Li, Steel and Zhang conjectured that, under a molecular clock and a symmetric model, Fitch parsimony using all the leaves is at least as accurate for the root state as using any single leaf. Fischer and Thatte proved this for two states, and Herbst and Fischer for three and four states.
Problem. Is $$\Pr\{\widehat\sigma_\rho = \sigma_\rho\} \ge q_r(H)$$ for every $r \ge 5$, every such tree and every such length assignment, the probability being over both the states and the final uniform choice?
Source: Li, Steel and Zhang (2008), the conjecture closing their paper, for symmetric models; for the symmetric r-state model, see Herbst and Fischer (2018), Section 5. Stated by AIM — Open Applied Problems for r ≥ 5.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, ST
- Keywords
- AIM Open Applied Problems, ancestral state reconstruction, maximum parsimony, phylogenetic trees
References
@article{li2008,
author = {Li, Guoliang and Steel, Mike and Zhang, Louxin},
title = {More taxa are not necessarily better for the reconstruction of ancestral character states},
journal = {Syst. Biol.},
volume = {57},
number = {4},
year = {2008},
pages = {647--653},
doi = {10.1080/10635150802203898},
}
@article{fischer2009,
author = {Fischer, Mareike and Thatte, Bhalchandra D.},
title = {Maximum parsimony on subsets of taxa},
journal = {J. Theoret. Biol.},
volume = {260},
number = {2},
year = {2009},
pages = {290--293},
doi = {10.1016/j.jtbi.2009.06.010},
eprint = {0809.3653},
archivePrefix = {arXiv},
}
@article{herbst2018,
author = {Herbst, Lina and Fischer, Mareike},
title = {On the accuracy of ancestral sequence reconstruction for ultrametric trees with parsimony},
journal = {Bull. Math. Biol.},
volume = {80},
number = {4},
year = {2018},
pages = {864--879},
doi = {10.1007/s11538-018-0407-5},
eprint = {1706.06085},
archivePrefix = {arXiv},
}
@misc{aim-fitch-ultrametric-ancestral-accuracy,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Accuracy of parsimony reconstruction under a molecular clock}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/328-fitch-ultrametric-ancestral-accuracy.md},
note = {Entry 328 at commit a153f46, 2026-10-13},
}
Resolution claims
Does Fitch parsimony on a tree whose leaves are all the same distance from the root reconstruct the root state at least as accurately as any single leaf? We give a negative answer for the symmetric twenty-state model. A rooted binary tree with three leaves and strictly positive edge lengths has Fitch accuracy $38829/400000$, whereas each leaf agrees with the …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Open → Solution claimed | The registry's curators | A three-leaf counterexample for Fitch reconstruction under a molecular clock v1 recorded from AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00432, "Accuracy of parsimony reconstruction under a molecular clock", clopen.solutions.