{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T16:05:04Z","timestamp":1784131504477,"version":"3.55.0"},"reference-count":94,"publisher":"Elsevier BV","issue":"7","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/100000054","name":"National Cancer Institute","doi-asserted-by":"publisher","award":["U24CA248453"],"award-info":[{"award-number":["U24CA248453"]}],"id":[{"id":"10.13039\/100000054","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000054","name":"National Cancer Institute","doi-asserted-by":"publisher","award":["U24CA264027"],"award-info":[{"award-number":["U24CA264027"]}],"id":[{"id":"10.13039\/100000054","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["cell.com","elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Cell Systems"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1016\/j.cels.2026.101615","type":"journal-article","created":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T14:47:36Z","timestamp":1780325256000},"page":"101615","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"title":["The tree labeling polytope: A unified approach to ancestral reconstruction problems"],"prefix":"10.1016","volume":"17","author":[{"given":"Henri","family":"Schmidt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1274-048X","authenticated-orcid":false,"given":"Benjamin J.","family":"Raphael","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.cels.2026.101615_bib1","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","article-title":"Toward defining the course of evolution: minimum change for a specific tree topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Syst. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/2529676","article-title":"Minimum mutation fits to a given tree","volume":"29","author":"Hartigan","year":"1973","journal-title":"Biometrics"},{"key":"10.1016\/j.cels.2026.101615_bib3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal mutation trees of sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/j.cels.2026.101615_bib4","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/BF01681346","article-title":"Locating the vertices of a Steiner tree in an arbitrary metric space","volume":"9","author":"Sankoff","year":"1975","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib5","series-title":"Comparative Genomics 72\u201386","author":"Cs\u0171r\u00f6s","year":"2008"},{"key":"10.1016\/j.cels.2026.101615_bib6","doi-asserted-by":"crossref","first-page":"S139","DOI":"10.1007\/PL00000067","article-title":"Accuracies of ancestral amino acid sequences inferred by the parsimony, likelihood, and distance methods","volume":"44","author":"Zhang","year":"1997","journal-title":"J. Mol. Evol."},{"key":"10.1016\/j.cels.2026.101615_bib7","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1038\/nrg1324","article-title":"Resurrecting ancient genes: experimental analysis of extinct molecules","volume":"5","author":"Thornton","year":"2004","journal-title":"Nat. Rev. Genet."},{"key":"10.1016\/j.cels.2026.101615_bib8","doi-asserted-by":"crossref","DOI":"10.1038\/ncomms12847","article-title":"An experimental phylogeny to benchmark ancestral sequence reconstruction","volume":"7","author":"Randall","year":"2016","journal-title":"Nat. Commun."},{"key":"10.1016\/j.cels.2026.101615_bib9","doi-asserted-by":"crossref","first-page":"3076","DOI":"10.1093\/annonc\/mdx517","article-title":"ClonEvol: clonal ordering and visualization in cancer sequencing","volume":"28","author":"Dang","year":"2017","journal-title":"Ann. Oncol."},{"key":"10.1016\/j.cels.2026.101615_bib10","doi-asserted-by":"crossref","DOI":"10.1038\/ncomms14114","article-title":"Reconstructing metastatic seeding patterns of human cancers","volume":"8","author":"Reiter","year":"2017","journal-title":"Nat. Commun."},{"key":"10.1016\/j.cels.2026.101615_bib11","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1038\/s41588-018-0106-z","article-title":"Inferring parsimonious migration histories for metastatic cancers","volume":"50","author":"El-Kebir","year":"2018","journal-title":"Nat. Genet."},{"key":"10.1016\/j.cels.2026.101615_bib12","doi-asserted-by":"crossref","DOI":"10.3390\/cancers11121880","article-title":"Delineation of tumor migration paths by using a bayesian biogeographic approach","volume":"11","author":"Chroni","year":"2019","journal-title":"Cancers"},{"key":"10.1016\/j.cels.2026.101615_bib13","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.ccell.2019.12.004","article-title":"Cancer genome evolutionary trajectories in metastasis","volume":"37","author":"Birkbak","year":"2020","journal-title":"Cancer Cell"},{"key":"10.1016\/j.cels.2026.101615_bib14","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1038\/s41592-025-02924-8","article-title":"Inferring cancer type-specific patterns of metastatic spread using Metient","volume":"23","author":"Koyyalagunta","year":"2026","journal-title":"Nat. Methods"},{"key":"10.1016\/j.cels.2026.101615_bib15","doi-asserted-by":"crossref","DOI":"10.1126\/science.abc1944","article-title":"Single-cell lineages reveal the rates, routes, and drivers of metastasis in cancer xenografts","volume":"371","author":"Quinn","year":"2021","journal-title":"Science"},{"key":"10.1016\/j.cels.2026.101615_bib16","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.1004613","article-title":"Epidemic Reconstruction in a Phylogenetics Framework: Transmission Trees as Partitions of the Node Set","volume":"11","author":"Hall","year":"2015","journal-title":"PLOS Comput. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib17","doi-asserted-by":"crossref","first-page":"1852","DOI":"10.1093\/bioinformatics\/bty921","article-title":"FAVITES: simultaneous simulation of transmission networks, phylogenetic trees and sequences","volume":"35","author":"Moshiri","year":"2019","journal-title":"Bioinformatics"},{"key":"10.1016\/j.cels.2026.101615_bib18","doi-asserted-by":"crossref","first-page":"2690","DOI":"10.1073\/pnas.1522930113","article-title":"Phylogenetically resolving epidemiologic linkage","volume":"113","author":"Romero-Severson","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10.1016\/j.cels.2026.101615_bib19","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1093\/molbev\/msx304","article-title":"PHYLOSCANNER: Inferring Transmission from Within- and Between-Host Pathogen Genetic Diversity","volume":"35","author":"Wymant","year":"2018","journal-title":"Mol. Biol. Evol."},{"key":"10.1016\/j.cels.2026.101615_bib20","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1093\/molbev\/msz058","article-title":"Transmission Trees on a Known Pathogen Phylogeny: Enumeration and Sampling","volume":"36","author":"Hall","year":"2019","journal-title":"Mol. Biol. Evol."},{"key":"10.1016\/j.cels.2026.101615_bib21","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1093\/bioinformatics\/btx402","article-title":"QUENTIN: Reconstruction of disease transmissions from viral quasispecies genomic data","volume":"34","author":"Skums","year":"2018","journal-title":"Bioinformatics"},{"key":"10.1016\/j.cels.2026.101615_bib22","article-title":"SharpTNI: Counting and Sampling Parsimonious Transmission Networks under a Weak Bottleneck","author":"Sashittal","year":"2019","journal-title":"bioRxiv"},{"key":"10.1016\/j.cels.2026.101615_bib23","doi-asserted-by":"crossref","first-page":"i362","DOI":"10.1093\/bioinformatics\/btaa438","article-title":"Sampling and summarizing transmission trees with multi-strain infections","volume":"36","author":"Sashittal","year":"2020","journal-title":"Bioinformatics"},{"key":"10.1016\/j.cels.2026.101615_bib24","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1109\/TCBB.2021.3096455","article-title":"TNet: Transmission Network Inference Using Within-Host Strain Diversity and its Application to Geographical Tracking of COVID-19 Spread","volume":"19","author":"Dhar","year":"2022","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"10.1016\/j.cels.2026.101615_bib25","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1016\/j.cels.2022.07.005","article-title":"SOPHIE: Viral outbreak investigation and transmission history reconstruction in a joint phylogenetic and network theory framework","volume":"13","author":"Skums","year":"2022","journal-title":"Cell Syst."},{"key":"10.1016\/j.cels.2026.101615_bib26","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1038\/s41592-025-02903-z","article-title":"Inferring cell differentiation maps from lineage tracing data","volume":"23","author":"Sashittal","year":"2026","journal-title":"Nat. Methods"},{"key":"10.1016\/j.cels.2026.101615_bib27","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0025-5564(90)90123-G","article-title":"Reconstructing evolution of sequences subject to recombination using parsimony","volume":"98","author":"Hein","year":"1990","journal-title":"Math. Biosci."},{"key":"10.1016\/j.cels.2026.101615_bib28","series-title":"2005 IEEE Computational Systems Bioinformatics Conference (CSB\u201905)","first-page":"93","article-title":"Reconstructing phylogenetic networks using maximum parsimony","author":"Nakhleh","year":"2005"},{"key":"10.1016\/j.cels.2026.101615_bib29","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.dam.2011.09.022","article-title":"The complexity of minimum convex coloring","volume":"160","author":"Kammer","year":"2012","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.cels.2026.101615_bib30","doi-asserted-by":"crossref","DOI":"10.1186\/s13015-022-00216-w","article-title":"Treewidth-based algorithms for the small parsimony problem on networks","volume":"17","author":"Scornavacca","year":"2022","journal-title":"Algorithms Mol. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib31","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/140959948","article-title":"On computing the maximum parsimony score of a phylogenetic network","volume":"29","author":"Fischer","year":"2015","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.cels.2026.101615_bib32","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s10107-015-0880-7","article-title":"The convex recoloring problem: polyhedra, facets and computational experiments","volume":"156","author":"Camp\u00ealo","year":"2016","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib33","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.ejor.2022.02.013","article-title":"Strong inequalities and a branch-and-price algorithm for the convex recoloring problem","volume":"303","author":"Camp\u00ealo","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib34","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1089\/cmb.2023.0352","article-title":"Enforcing Temporal Consistency in Migration History Inference","volume":"31","author":"Roddur","year":"2024","journal-title":"J. Comput. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib35","unstructured":"El-Kebir, M. (2018). Parsimonious Migration History Problem: Complexity and Algorithms in 18th International Workshop on Algorithms in Bioinformatics (WABI 2018) 113, 1\u201324. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2018.24."},{"key":"10.1016\/j.cels.2026.101615_bib36","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1093\/sysbio\/syx094","article-title":"Improved maximum parsimony models for phylogenetic networks","volume":"67","author":"Van Iersel","year":"2018","journal-title":"Syst. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib37","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10479-024-06452-0","article-title":"A 2-approximation algorithm for the softwired parsimony problem on binary, treechild phylogenetic networks","volume":"345","author":"Frohn","year":"2025","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib38","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01584082","article-title":"Matroids and the greedy algorithm","volume":"1","author":"Edmonds","year":"1971","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib39","series-title":"2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906)","first-page":"273","article-title":"Minimum Bounded Degree Spanning Trees","author":"Goemans","year":"2006"},{"key":"10.1016\/j.cels.2026.101615_bib40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2629366","article-title":"Approximating minimum bounded degree spanning trees to within one of optimal","volume":"62","author":"Singh","year":"2015","journal-title":"J. ACM"},{"key":"10.1016\/j.cels.2026.101615_bib41","series-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"1512","article-title":"Matroidal Degree-Bounded Minimum Spanning Trees","author":"Zenklusen","year":"2012"},{"key":"10.1016\/j.cels.2026.101615_bib42","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0377-2217(89)90169-0","article-title":"A Lagrangean approach to the degree-constrained minimum spanning tree problem","volume":"39","author":"Volgenant","year":"1989","journal-title":"Eur. J. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib43","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1007\/s10589-015-9788-7","article-title":"Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem","volume":"63","author":"Bicalho","year":"2016","journal-title":"Comput. Optim. Appl."},{"key":"10.1016\/j.cels.2026.101615_bib44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","article-title":"The Lagrangian relaxation method for solving integer programming problems","volume":"27","author":"Fisher","year":"1981","journal-title":"Manag. Sci."},{"key":"10.1016\/j.cels.2026.101615_bib45","series-title":"Integer Programming","author":"Wolsey","year":"2020"},{"key":"10.1016\/j.cels.2026.101615_bib46","series-title":"5th Scandinavian Workshop on Algorithm Theory Reykjav\u00edk, Iceland","first-page":"66","article-title":"The constrained minimum spanning tree problem in Algorithm Theory\u2014SWAT","author":"Ravi","year":"1996"},{"key":"10.1016\/j.cels.2026.101615_bib47","series-title":"Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing","first-page":"537","article-title":"A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees","author":"K\u00f6nemann","year":"2000"},{"key":"10.1016\/j.cels.2026.101615_bib48","series-title":"17th International Conference on Transparent Optical Networks (ICTON)","first-page":"1","article-title":"Constrained shortest path problems: state-of-the-art and recent advances","author":"Festa","year":"2015"},{"key":"10.1016\/j.cels.2026.101615_bib49","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.cor.2019.03.010","article-title":"The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach","volume":"107","author":"Di Puglia Pugliese","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib50","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","article-title":"Fast approximation algorithms for fractional packing and covering problems","volume":"20","author":"Plotkin","year":"1995","journal-title":"Math. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib51","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","article-title":"Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms","volume":"46","author":"Leighton","year":"1999","journal-title":"J. ACM"},{"key":"10.1016\/j.cels.2026.101615_bib52","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480199355754","article-title":"Approximating fractional multicommodity flowindependent of the number of commodities","volume":"13","author":"Fleischer","year":"2000","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.cels.2026.101615_bib53","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0196-8858(92)90017-Q","article-title":"Evolutionary trees: an integer multicommodity max-flow-min-cut theorem","volume":"13","author":"Erd\u00f6s","year":"1992","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/j.cels.2026.101615_bib54","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01581691","article-title":"On weighted multiway cuts in trees","volume":"65","author":"Erd\u0151s","year":"1994","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib55","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0166-218X(98)00049-3","article-title":"Minimum multiway cuts in trees","volume":"87","author":"Erd\u0151s","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.cels.2026.101615_bib56","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.1016\/j.cell.2022.04.015","article-title":"Lineage tracing reveals the phylodynamics, plasticity, and paths of tumor evolution","volume":"185","author":"Yang","year":"2022","journal-title":"Cell"},{"key":"10.1016\/j.cels.2026.101615_bib57","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.mrrev.2018.05.001","article-title":"Multiclonal tumor origin: Evidence and implications","volume":"777","author":"Parsons","year":"2018","journal-title":"Mutat. Res. Rev. Mutat. Res."},{"key":"10.1016\/j.cels.2026.101615_bib58","series-title":"An Introduction to Bioinformatics Algorithms","author":"Jones","year":"2004"},{"key":"10.1016\/j.cels.2026.101615_bib59","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1093\/oxfordjournals.molbev.a026369","article-title":"A fast algorithm for joint reconstruction of ancestral amino acid sequences","volume":"17","author":"Pupko","year":"2000","journal-title":"Mol. Biol. Evol."},{"key":"10.1016\/j.cels.2026.101615_bib94","series-title":"Computational Molecular Evolution","author":"Yang","year":"2006"},{"key":"10.1016\/j.cels.2026.101615_bib60","series-title":"ReCombinatorics: the Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks","author":"Gusfield","year":"2014"},{"key":"10.1016\/j.cels.2026.101615_bib61","doi-asserted-by":"crossref","DOI":"10.1186\/1748-7188-7-9","article-title":"Maximum parsimony on phylogenetic networks","volume":"7","author":"Kannan","year":"2012","journal-title":"Algorithms Mol. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib62","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0305-0548(82)90026-0","article-title":"Minimal spanning tree subject to a side constraint","volume":"9","author":"Aggarwal","year":"1982","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib63","series-title":"Facets of Combinatorial Optimization: Festschrift for Martin Gr\u00f6tschel","first-page":"449","article-title":"Mixed Integer Programming: Analyzing 12 Years of Progress","author":"Achterberg","year":"2013"},{"key":"10.1016\/j.cels.2026.101615_bib64","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"J. Oper. Res. Soc. Am."},{"key":"10.1016\/j.cels.2026.101615_bib65","first-page":"84","article-title":"On the solution of discrete programming problems","volume":"25","author":"Markowitz","year":"1957","journal-title":"Econ.: J. Econ. Soc."},{"key":"10.1016\/j.cels.2026.101615_bib89","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/s10107-016-1094-3","article-title":"An extended formulation of the convex recoloring problem on a tree","volume":"165","author":"Chopra","year":"2017","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib66","doi-asserted-by":"crossref","DOI":"10.21105\/joss.03173","article-title":"Ngesh: a Python library for synthetic phylogenetic data","volume":"6","author":"Tresoldi","year":"2021","journal-title":"J. Open Source Softw."},{"key":"10.1016\/j.cels.2026.101615_bib67","unstructured":"Gurobi Optimization, LLC. (2023) Gurobi Optimizer Reference Manual 2023. https:\/\/docs.gurobi.com\/current\/"},{"key":"10.1016\/j.cels.2026.101615_bib68","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1038\/s41586-019-1184-5","article-title":"Molecular recording of mammalian embryogenesis","volume":"570","author":"Chan","year":"2019","journal-title":"Nature"},{"key":"10.1016\/j.cels.2026.101615_bib69","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1016\/j.ccell.2021.05.005","article-title":"Single-cell lineage tracing of metastatic cancer reveals selection of hybrid EMT states","volume":"39","author":"Simeonov","year":"2021","journal-title":"Cancer Cell"},{"key":"10.1016\/j.cels.2026.101615_bib70","article-title":"Maximum Likelihood Inference of Time-scaled Cell Lineage Trees with Mixedtype Missing Data in International Conference on Research in Computational","volume":"360\u2013363","author":"Mai","year":"2024","journal-title":"Mol. Biol."},{"key":"10.1016\/j.cels.2026.101615_bib71","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1016\/j.cels.2023.11.005","article-title":"Startle: a star homoplasy approach for crispr-cas9 lineage tracing","volume":"14","author":"Sashittal","year":"2023","journal-title":"Cell Syst."},{"key":"10.1016\/j.cels.2026.101615_bib72","doi-asserted-by":"crossref","DOI":"10.3390\/ijms18010051","article-title":"Lymph nodes and cancer metastasis: new perspectives on the role of intranodal lymphatic sinuses","volume":"18","author":"Ji","year":"2016","journal-title":"Int. J. Mol. Sci."},{"key":"10.1016\/j.cels.2026.101615_bib73","article-title":"Lymph node metastasis in cancer progression: molecular mechanisms, clinical significance and therapeutic interventions","volume":"8","author":"Ji","year":"2023","journal-title":"Signal Transduct. Target. Ther."},{"key":"10.1016\/j.cels.2026.101615_bib74","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1016\/j.jcss.2007.10.003","article-title":"Convex recolorings of strings and trees: Definitions, hardness results and algorithms","volume":"74","author":"Moran","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.cels.2026.101615_bib75","first-page":"471","article-title":"Maximum-likelihood estimation of evolutionary trees from continuous characters","volume":"25","author":"Felsenstein","year":"1973","journal-title":"Am. J. Hum. Genet."},{"key":"10.1016\/j.cels.2026.101615_bib76","doi-asserted-by":"crossref","first-page":"e123","DOI":"10.1093\/bioinformatics\/btl313","article-title":"Efficient parsimony-based methods for phylogenetic network reconstruction","volume":"23","author":"Jin","year":"2007","journal-title":"Bioinformatics"},{"key":"10.1016\/j.cels.2026.101615_bib77","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1111\/cla.12552","article-title":"Parsimony optimization of phylogenetic networks","volume":"39","author":"Wheeler","year":"2023","journal-title":"Cladistics"},{"key":"10.1016\/j.cels.2026.101615_bib78","series-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1998"},{"key":"10.1016\/j.cels.2026.101615_bib79","series-title":"Progress in Combinatorial Optimization","first-page":"117","author":"Edmonds","year":"1984"},{"key":"10.1016\/j.cels.2026.101615_bib80","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","article-title":"Extended formulations in combinatorial optimization","volume":"8","author":"Conforti","year":"2010","journal-title":"4OR"},{"key":"10.1016\/j.cels.2026.101615_bib81","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0167-6377(83)90062-7","article-title":"Operations that preserve total dual integrality","volume":"2","author":"Cook","year":"1983","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.cels.2026.101615_bib82","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/BF01582009","article-title":"On the acyclic subgraph polytope","volume":"33","author":"Gr\u00f6tschel","year":"1985","journal-title":"Math. Program."},{"key":"10.1016\/j.cels.2026.101615_bib83","series-title":"Proceedings: 15th Annual International Conference, COCOON 2009 Niagara Falls, NY, USA","first-page":"388","article-title":"Convex recoloring revisited: Complexity and exact algorithms in Computing and Combinatorics","volume":"15","author":"Kanj","year":"2009"},{"key":"10.1016\/j.cels.2026.101615_bib84","first-page":"192","article-title":"Efficient approximation of convex recolorings in International Workshop on Approximation Algorithms for Combinatorial","author":"Moran","year":"2005","journal-title":"Optimization"},{"key":"10.1016\/j.cels.2026.101615_bib85","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00224-007-9069-7","article-title":"Improved approximation algorithm for convex recoloring of trees","volume":"43","author":"Bar-Yehuda","year":"2008","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.cels.2026.101615_bib86","series-title":"International Workshop on Combinatorial Algorithms","first-page":"299","article-title":"5-Approximation Algorithm for the 2-Convex Recoloring Problem","author":"Bar-Yehuda","year":"2015"},{"key":"10.1016\/j.cels.2026.101615_bib87","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.endm.2011.05.029","article-title":"Convex recoloring of paths","volume":"37","author":"Lima","year":"2011","journal-title":"Electron. Notes Discrete Math."},{"key":"10.1016\/j.cels.2026.101615_bib88","series-title":"Column Generation Approach to the Convex Recoloring Problem on a Tree in Modeling and Optimization: Theory and Applications","first-page":"39","author":"Chopra","year":"2017"},{"key":"10.1016\/j.cels.2026.101615_bib90","doi-asserted-by":"crossref","first-page":"1454","DOI":"10.1111\/itor.12896","article-title":"A heuristic for the convex recoloring problem in graphs","volume":"29","author":"Dantas","year":"2022","journal-title":"Int. Trans. Oper. Res."},{"key":"10.1016\/j.cels.2026.101615_bib91","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1137\/1016083","article-title":"On the assignment polytope","volume":"16","author":"Balinski","year":"1974","journal-title":"SIAM Rev."},{"key":"10.1016\/j.cels.2026.101615_bib92","series-title":"Proceedings: 25th International Conference, CAV 2013, Saint Petersburg, Russia","first-page":"101","article-title":"TTP: tool for tumor progression in Computer Aided Verification","volume":"25","author":"Reiter","year":"2013"},{"key":"10.1016\/j.cels.2026.101615_bib93","series-title":"Problem Solving Handbook in Computational Biology and Bioinformatics","first-page":"125","author":"Nakhleh","year":"2010"}],"container-title":["Cell Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2405471226000979?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2405471226000979?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T15:12:28Z","timestamp":1784128348000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S2405471226000979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":94,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2026,7]]}},"alternative-id":["S2405471226000979"],"URL":"https:\/\/doi.org\/10.1016\/j.cels.2026.101615","relation":{},"ISSN":["2405-4712"],"issn-type":[{"value":"2405-4712","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The tree labeling polytope: A unified approach to ancestral reconstruction problems","name":"articletitle","label":"Article Title"},{"value":"Cell Systems","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.cels.2026.101615","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Published by Elsevier Inc.","name":"copyright","label":"Copyright"}],"article-number":"101615"}}