A common problem in phylogeny is to reconstruct the ancestral states of a feature measured at the present time. The classic Fitch-Hartigan and Sankoff algorithms compute the most parsimonious or most likely reconstruction. However, these approaches do not readily extend to structured ancestral reconstruction problems, such as those encountered when inferring the routes of metastases in cancer, deriving the transmission history of viruses, or detecting horizontal gene transfer in phylogenetic networks. We develop a combinatorial optimization approach to ancestral reconstruction problems based on the tree-labeling polytope, a geometric object whose vertices represent the ancestral labelings of a tree. We derive algorithms for three structured ancestral reconstruction problems: parsimonious migration history, softwired small parsimony, and convex recoloring. We apply these algorithms to analyze routes of metastasis in a mouse model of lung adenocarcinoma using lineage-tracing data from thousands of single cells.
Abstract
Journal Article
eng
42225063
Schmidt, Henri, and Benjamin J. Raphael. "The Tree Labeling Polytope: a Unified Approach to Ancestral Reconstruction Problems." Cell Systems, 2026, p. 101615.
Schmidt H, Raphael BJ. The tree labeling polytope: A unified approach to ancestral reconstruction problems. Cell Syst. 2026.
Schmidt, H., & Raphael, B. J. (2026). The tree labeling polytope: A unified approach to ancestral reconstruction problems. Cell Systems, 101615. https://doi.org/10.1016/j.cels.2026.101615
Schmidt H, Raphael BJ. The Tree Labeling Polytope: a Unified Approach to Ancestral Reconstruction Problems. Cell Syst. 2026 Jun 1;101615. PubMed PMID: 42225063.
* Article titles in AMA citation format should be in sentence-case
TY - JOUR
T1 - The tree labeling polytope: A unified approach to ancestral reconstruction problems.
AU - Schmidt,Henri,
AU - Raphael,Benjamin J,
Y1 - 2026/06/01/
PY - 2025/04/08/received
PY - 2025/12/04/revised
PY - 2026/04/24/accepted
PY - 2026/6/2/medline
PY - 2026/6/2/pubmed
PY - 2026/6/1/entrez
KW - algorithms
KW - optimization
KW - phylogenetics
SP - 101615
EP - 101615
JF - Cell systems
JO - Cell Syst
N2 - A common problem in phylogeny is to reconstruct the ancestral states of a feature measured at the present time. The classic Fitch-Hartigan and Sankoff algorithms compute the most parsimonious or most likely reconstruction. However, these approaches do not readily extend to structured ancestral reconstruction problems, such as those encountered when inferring the routes of metastases in cancer, deriving the transmission history of viruses, or detecting horizontal gene transfer in phylogenetic networks. We develop a combinatorial optimization approach to ancestral reconstruction problems based on the tree-labeling polytope, a geometric object whose vertices represent the ancestral labelings of a tree. We derive algorithms for three structured ancestral reconstruction problems: parsimonious migration history, softwired small parsimony, and convex recoloring. We apply these algorithms to analyze routes of metastasis in a mouse model of lung adenocarcinoma using lineage-tracing data from thousands of single cells.
SN - 2405-4720
UR - https://www.unboundmedicine.com/prime/citation/42225063/The_tree_labeling_polytope:_A_unified_approach_to_ancestral_reconstruction_problems.
DB - PRIME
DP - Unbound Medicine
ER -
