{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"name":"bioRxiv"}],"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T02:00:09Z","timestamp":1785204009495,"version":"3.55.0"},"posted":{"date-parts":[[2026,7,23]]},"group-title":"Bioinformatics","reference-count":52,"publisher":"openRxiv","license":[{"start":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T00:00:00Z","timestamp":1784764800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"crossref","award":["P50 CA247749-01"],"award-info":[{"award-number":["P50 CA247749-01"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2026,7,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                <jats:p>The binary perfect phylogeny, in which each mutation arises exactly once on an evolutionary tree and is never lost, is a well-studied idealized phylogenetic model. When observed data has errors, a common approach to phylogeny inference is to seek a tree that minimizes the number of error corrections (\u201cflips\u201d) needed to fit a perfect phylogeny. These objectives draw on an intuitive justification: minimizing implied errors should prefer the true tree in expectation.<\/jats:p>\n                <jats:p>We test this assumption using a generative model with independent errors and prove that error-correction objectives are statistically inconsistent for all positive error rates: in expectation, the minimum-cost tree need not be the true tree. Our proof is constructive and yields counterexamples involving any tree topology and any positive error rates, demonstrating the ubiquity of the phenomenon. The core problem is that tree topologies can explain observed mutation patterns with fewer errors than actually occurred, and differ in their ability to do so, introducing systematic bias. This mechanism is distinct from previously identified sources of inconsistency such as homoplasy or incomplete lineage sorting, since the error-free setting is trivially consistent for perfect phylogenies.<\/jats:p>\n                <jats:p>We investigate how often this failure may occur in practice. Simulations calibrated to error rates from single-cell sequencing data show that an incorrect tree is preferred over the true tree in a substantial fraction of cases (over 50% in some settings) with rates increasing with tree size. Moreover, winning trees are not random but share specific topological features. Notably, at error rates typical of single-cell sequencing data, trees with deeper, more imbalanced topologies are consistently favored over more balanced ones. These results demonstrate that inconsistency is not a theoretical edge case, and that understanding when and how it arises is important when interpreting results in practice.<\/jats:p>\n                <jats:sec>\n                  <jats:title>Supplementary Material<\/jats:title>\n                  <jats:p>\n                    <jats:italic>Source code<\/jats:italic>\n                    :\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/shahcompbio\/phylo_inconsistency\">https:\/\/github.com\/shahcompbio\/phylo_inconsistency<\/jats:ext-link>\n                  <\/jats:p>\n                <\/jats:sec>\n                <jats:sec>\n                  <jats:title>Funding<\/jats:title>\n                  <jats:p>This research was supported in part by NCI SPORE (P50 CA247749-01)<\/jats:p>\n                <\/jats:sec>","DOI":"10.64898\/2026.07.20.739615","type":"posted-content","created":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T12:00:21Z","timestamp":1784894421000},"source":"Crossref","is-referenced-by-count":0,"title":["Statistical Inconsistency of Error-correction Objectives for Perfect Phylogenies"],"prefix":"10.64898","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3944-5018","authenticated-orcid":false,"given":"Gryte","family":"Satas","sequence":"first","affiliation":[{"name":"Halvorsen Center for Computational Oncology, Memorial Sloan Kettering Cancer Center, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9337-5180","authenticated-orcid":false,"given":"Matthew A.","family":"Myers","sequence":"additional","affiliation":[{"name":"Halvorsen Center for Computational Oncology, Memorial Sloan Kettering Cancer Center, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6402-523X","authenticated-orcid":false,"given":"Sohrab P.","family":"Shah","sequence":"additional","affiliation":[{"name":"Halvorsen Center for Computational Oncology, Memorial Sloan Kettering Cancer Center, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"54368","reference":[{"key":"2026072718450938000_2026.07.20.739615v1.1","doi-asserted-by":"crossref","unstructured":"Richa Agarwala and David Fern\u00e1ndez-Baca . A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 140\u2013147. IEEE, 1993.","DOI":"10.1109\/SFCS.1993.366873"},{"key":"2026072718450938000_2026.07.20.739615v1.2","doi-asserted-by":"crossref","unstructured":"Pranjal Awasthi , Avrim Blum , Jamie Morgenstern , and Or Sheffet . Additive approximation for near-perfect phylogeny construction. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 25\u201336. Springer, 2012.","DOI":"10.1007\/978-3-642-32512-0_3"},{"key":"2026072718450938000_2026.07.20.739615v1.3","doi-asserted-by":"crossref","unstructured":"Erfan Sadeqi Azer , Mohammad Haghir Ebrahimabadi , Salem Maliki\u0107 , Roni Khardon , and S Cenk Sahinalp . Tumor phylogeny topology inference via deep learning. Iscience, 23(11), 2020.","DOI":"10.1016\/j.isci.2020.101655"},{"key":"2026072718450938000_2026.07.20.739615v1.4","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syu081"},{"key":"2026072718450938000_2026.07.20.739615v1.5","article-title":"Intractability of the minimum-flip supertree problem and its variants","year":"2011","journal-title":"arXiv preprint"},{"key":"2026072718450938000_2026.07.20.739615v1.6","doi-asserted-by":"crossref","unstructured":"Sebastian B\u00f6cker , Quang Bao Anh Bui , and Anke Truss . An improved fixed-parameter algorithm for minimum-flip consensus trees. In International Workshop on Parameterized and Exact Computation, pages 43\u201354. Springer, 2008.","DOI":"10.1007\/978-3-540-79723-4_6"},{"key":"2026072718450938000_2026.07.20.739615v1.7","unstructured":"John D Bridgers , Jan Hoinka , S Cenk Sahinalp , Salem Malikic , Teresa M Przytycka , and Funda Ergun . Improved algorithms for bi-partition function computation. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025), pages 5\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2025."},{"issue":"2","key":"2026072718450938000_2026.07.20.739615v1.8","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/s00453-012-9698-3","article-title":"Flipcut supertrees: towards matrix representation accuracy in polynomial time","volume":"67","year":"2013","journal-title":"Algorithmica"},{"issue":"2","key":"2026072718450938000_2026.07.20.739615v1.9","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TCBB.2006.26","article-title":"Minimum-flip supertrees: complexity and algorithms","volume":"3","year":"2006","journal-title":"IEEE\/ACM transactions on computational biology and bioinformatics"},{"key":"2026072718450938000_2026.07.20.739615v1.10","doi-asserted-by":"crossref","unstructured":"Markus Chimani , Sven Rahmann , and Sebastian B\u00f6cker . Exact ilp solutions for phylogenetic minimum flip problems. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, pages 147\u2013153, 2010.","DOI":"10.1145\/1854776.1854800"},{"key":"2026072718450938000_2026.07.20.739615v1.11","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa722"},{"issue":"2","key":"2026072718450938000_2026.07.20.739615v1.12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1038\/nrclinonc.2017.166","article-title":"Tumour heterogeneity and resistance to cancer therapies","volume":"15","year":"2018","journal-title":"Nature reviews Clinical oncology"},{"issue":"2","key":"2026072718450938000_2026.07.20.739615v1.13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.bbcan.2017.01.003","article-title":"Tumor evolution: Linear, branching, neutral or punctuated?","volume":"1867","year":"2017","journal-title":"Biochimica et Biophysica Acta (BBA)-Reviews on Cancer"},{"key":"2026072718450938000_2026.07.20.739615v1.14","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syp008"},{"issue":"5","key":"2026072718450938000_2026.07.20.739615v1.15","doi-asserted-by":"crossref","first-page":"e68","DOI":"10.1371\/journal.pgen.0020068","article-title":"Discordance of species trees with their most likely gene trees","volume":"2","year":"2006","journal-title":"PLoS genetics"},{"key":"2026072718450938000_2026.07.20.739615v1.16","doi-asserted-by":"crossref","unstructured":"Mohammadamin Edrisi , Hamim Zafar , and Luay Nakhleh . A combinatorial approach for single-cell variant detection via phylogenetic inference. bioRxiv, page 693960, 2019.","DOI":"10.1101\/693960"},{"key":"2026072718450938000_2026.07.20.739615v1.17","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty589"},{"key":"2026072718450938000_2026.07.20.739615v1.18","doi-asserted-by":"crossref","unstructured":"Joseph Felsenstein . Cases in which parsimony or compatibility methods will be positively misleading. Systematic zoology, pages 401\u2013410, 1978.","DOI":"10.1093\/sysbio\/27.4.401"},{"key":"2026072718450938000_2026.07.20.739615v1.19","unstructured":"Joseph Felsenstein . Inferring phylogenies. In Inferring phylogenies, pages 664\u2013664. 2004."},{"key":"2026072718450938000_2026.07.20.739615v1.20","doi-asserted-by":"crossref","unstructured":"Daniel W Feng and Mohammed El-Kebir . Dolphyin: A combinatorial algorithm for identifying 1-dollo phylogenies in cancer. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025), pages 9\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2025.","DOI":"10.1186\/s13015-026-00303-2"},{"key":"2026072718450938000_2026.07.20.739615v1.21","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1922.0009"},{"key":"2026072718450938000_2026.07.20.739615v1.22","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/20.4.406"},{"issue":"1","key":"2026072718450938000_2026.07.20.739615v1.23","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary trees","volume":"21","year":"1991","journal-title":"Networks"},{"key":"2026072718450938000_2026.07.20.739615v1.24","doi-asserted-by":"publisher","DOI":"10.2307\/2992396"},{"key":"2026072718450938000_2026.07.20.739615v1.25","doi-asserted-by":"crossref","unstructured":"Akhil Jakatdar , Palash Sashittal , and Benjamin J Raphael . Deriving longitudinal tumor phylogenies from single-cell sequencing data. bioRxiv, pages 2025\u201308, 2025.","DOI":"10.1101\/2025.08.06.668977"},{"key":"2026072718450938000_2026.07.20.739615v1.26","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/45.3.363"},{"key":"2026072718450938000_2026.07.20.739615v1.27","doi-asserted-by":"publisher","DOI":"10.1093\/genetics\/61.4.893"},{"key":"2026072718450938000_2026.07.20.739615v1.28","doi-asserted-by":"publisher","DOI":"10.1080\/10635150601146041"},{"key":"2026072718450938000_2026.07.20.739615v1.29","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syp034"},{"key":"2026072718450938000_2026.07.20.739615v1.30","doi-asserted-by":"crossref","unstructured":"Adiesha Liyanage , Robyn Burger , Allison Shi , Braeden Sopp , Binhai Zhu , and Brendan Mumey . Essentcell: Discovering essential evolutionary relations in noisy single-cell data. bioRxiv, pages 2025\u201304, 2025.","DOI":"10.1101\/2025.04.12.648524"},{"key":"2026072718450938000_2026.07.20.739615v1.31","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0805217105"},{"issue":"1","key":"2026072718450938000_2026.07.20.739615v1.32","doi-asserted-by":"crossref","first-page":"2750","DOI":"10.1038\/s41467-019-10737-5","article-title":"Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data","volume":"10","year":"2019","journal-title":"Nature communications"},{"key":"2026072718450938000_2026.07.20.739615v1.33","doi-asserted-by":"publisher","DOI":"10.1101\/gr.234435.118"},{"key":"2026072718450938000_2026.07.20.739615v1.34","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syx063"},{"key":"2026072718450938000_2026.07.20.739615v1.35","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syy061"},{"key":"2026072718450938000_2026.07.20.739615v1.36","doi-asserted-by":"publisher","DOI":"10.1016\/j.tpb.2014.12.005"},{"key":"2026072718450938000_2026.07.20.739615v1.37","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-016-0929-9"},{"key":"2026072718450938000_2026.07.20.739615v1.38","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa464"},{"key":"2026072718450938000_2026.07.20.739615v1.39","doi-asserted-by":"crossref","unstructured":"Sohrab Salehi , Fatemeh Dorri , Kevin Chern , Farhia Kabeer , Nicole Rusk , Tyler Funnell , Marc J Williams , Daniel Lai , Mirela Andronescu , Kieran R Campbell , et al. Cancer phylogenetic tree inference at scale from 1000s of single cell genomes. Peer Community Journal, 3, 2023.","DOI":"10.24072\/pcjournal.292"},{"issue":"4","key":"2026072718450938000_2026.07.20.739615v1.40","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.cels.2020.04.001","article-title":"Scarlet: single-cell tumor phylogeny inference with copy-number constrained mutation losses","volume":"10","year":"2020","journal-title":"Cell systems"},{"key":"2026072718450938000_2026.07.20.739615v1.41","doi-asserted-by":"publisher","DOI":"10.1080\/10635150490445788"},{"issue":"4","key":"2026072718450938000_2026.07.20.739615v1.42","first-page":"581","volume":"42","year":"1993","journal-title":"Parsimony can be consistent! Systematic biology"},{"key":"2026072718450938000_2026.07.20.739615v1.43","doi-asserted-by":"publisher","DOI":"10.1080\/10635150117959"},{"issue":"2","key":"2026072718450938000_2026.07.20.739615v1.44","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/BF00163810","article-title":"Inconsistency of the maximum parsimony method when the rate of nucleotide substitution is constant","volume":"39","year":"1994","journal-title":"Journal of molecular evolution"},{"key":"2026072718450938000_2026.07.20.739615v1.45","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2010.0102"},{"key":"2026072718450938000_2026.07.20.739615v1.46","unstructured":"Aad W Van der Vaart . Asymptotic statistics, volume 3. Cambridge university press, 2000."},{"key":"2026072718450938000_2026.07.20.739615v1.47","doi-asserted-by":"publisher","DOI":"10.1016\/j.molcel.2015.05.005"},{"issue":"1","key":"2026072718450938000_2026.07.20.739615v1.48","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1186\/s13015-021-00194-5","article-title":"Distinguishing linear and branched evolution given single-cell dna sequencing data of tumors","volume":"16","year":"2021","journal-title":"Algorithms for Molecular Biology"},{"key":"2026072718450938000_2026.07.20.739615v1.49","doi-asserted-by":"publisher","DOI":"10.1101\/gr.161968.113"},{"key":"2026072718450938000_2026.07.20.739615v1.50","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz676"},{"key":"2026072718450938000_2026.07.20.739615v1.51","doi-asserted-by":"crossref","unstructured":"Qing Yang , Yuheng Liu , Jijian Yang , Xing Wu , Zhirui Yang , Yonghe Xia , Yunchao Zheng , Jinhong Lu , Mengdie Yao , Yiheng Du , et al. Phylosolid: Robust phylogeny reconstruction from single-cell data despite inherent error and sparsity. bioRxiv, pages 2026\u201302, 2026.","DOI":"10.64898\/2026.02.04.703905"},{"key":"2026072718450938000_2026.07.20.739615v1.52","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-017-1311-2"}],"container-title":[],"original-title":[],"link":[{"URL":"https:\/\/syndication.highwire.org\/content\/doi\/10.64898\/2026.07.20.739615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T01:45:19Z","timestamp":1785203119000},"score":1,"resource":{"primary":{"URL":"http:\/\/biorxiv.org\/lookup\/doi\/10.64898\/2026.07.20.739615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,23]]},"references-count":52,"URL":"https:\/\/doi.org\/10.64898\/2026.07.20.739615","relation":{},"subject":[],"published":{"date-parts":[[2026,7,23]]},"subtype":"preprint"}}