The tree labeling polytope: A unified approach to ancestral reconstruction problems

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.