{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T13:37:31Z","timestamp":1786628251772,"version":"build-2736575974"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T00:00:00Z","timestamp":1786579200000},"content-version":"vor","delay-in-days":66,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>\n                      Several recent cancer phylogeny inference methods have used the\n                      <jats:italic>k<\/jats:italic>\n                      -Dollo evolutionary model for single-nucleotide variants, which requires a phylogeny\n                      <jats:italic>T<\/jats:italic>\n                      on binary sequencing data matrix\n                      <jats:italic>B<\/jats:italic>\n                      such that each variant is gained once and lost at most\n                      <jats:italic>k<\/jats:italic>\n                      times. The 1-Dollo variant has been studied extensively but its hardness remains open.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      We prove that the\n                      <jats:sc>1-Dollo Linear Phylogeny<\/jats:sc>\n                      (1DLP) problem, where we additionally require the resulting 1-Dollo phylogeny\n                      <jats:italic>T<\/jats:italic>\n                      to be linear, is equivalent to verifying whether matrix\n                      <jats:italic>B<\/jats:italic>\n                      has the Consecutive Ones Property, which can be determined in polynomial time. We also show that some practical extensions of 1DLP, such as the minimization of false negatives, are NP-hard. We then show how to recursively decompose any 1-Dollo phylogeny\n                      <jats:italic>T<\/jats:italic>\n                      , not necessarily linear, into several 1-Dollo linear phylogenies and extend this characterization to all matrices\n                      <jats:italic>B<\/jats:italic>\n                      that admit 1-Dollo phylogenies. We use this characterization to develop Dolphyin, a new exponential-time algorithm for inferring 1-Dollo phylogenies. Dolphyin is runtime-competitive with integer linear programming-based algorithm SPhyR (El-Kebir 2018) on simulated datasets and infers 1-Dollo phylogenies with false negative sequencing error rates at or below simulated ground truth rates. We apply Dolphyin to acute myeloid leukemia datasets and find that the majority of the cancers can be explained by 1-Dollo phylogenies with error rates in line with the used sequencing technology.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>Our work develops a novel, combinatorial algorithm for practical inference of 1-Dollo phylogenies.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-026-00303-2","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T14:54:14Z","timestamp":1780930454000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer"],"prefix":"10.1186","volume":"21","author":[{"given":"Daniel W.","family":"Feng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"issue":"4260","key":"303_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1126\/science.959840","volume":"194","author":"PC Nowell","year":"1976","unstructured":"Nowell PC. The clonal evolution of tumor cell populations. Science. 1976;194(4260):23\u20138. https:\/\/doi.org\/10.1126\/science.959840.","journal-title":"Science"},{"key":"303_CR2","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1038\/nrc3971","volume":"15","author":"D Tabassum","year":"2015","unstructured":"Tabassum D, Polyak K. Tumorigenesis: it takes a village. Nat Rev Cancer. 2015;15:473\u201383. https:\/\/doi.org\/10.1038\/nrc3971.","journal-title":"Nat Rev Cancer"},{"issue":"4","key":"303_CR3","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1038\/nrg.2016.170","volume":"18","author":"R Schwartz","year":"2017","unstructured":"Schwartz R, Sch\u00e4ffer AA. The evolution of tumour phylogenetics: principles and practice. Nat Rev Genet. 2017;18(4):213\u201329.","journal-title":"Nat Rev Genet"},{"issue":"6","key":"303_CR4","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R Agarwala","year":"1994","unstructured":"Agarwala R, Fern\u00e1ndez-Baca D. A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM J Comput. 1994;23(6):1216\u201324. https:\/\/doi.org\/10.1137\/S0097539793244587.","journal-title":"SIAM J Comput"},{"key":"303_CR5","doi-asserted-by":"crossref","unstructured":"Habib M, Stacho J. Unique perfect phylogeny is NP-hard. In: Proceedings of the 22nd Annual Conference on Combinatorial Pattern Matching. CPM\u201911, 2011;132\u2013146. Springer, Berlin, Heidelberg","DOI":"10.1007\/978-3-642-21458-5_13"},{"key":"303_CR6","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-1-4613-0255-1_6","volume-title":"The Perfect Phylogeny Problem","author":"D Fern\u00e1ndez-Baca","year":"2001","unstructured":"Fern\u00e1ndez-Baca D. The Perfect Phylogeny Problem. Boston, MA: Springer; 2001. p. 203\u201334. https:\/\/doi.org\/10.1007\/978-1-4613-0255-1_6."},{"issue":"1","key":"303_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D Gusfield","year":"1991","unstructured":"Gusfield D. Efficient algorithms for inferring evolutionary trees. Networks. 1991;21(1):19\u201328. https:\/\/doi.org\/10.1002\/net.3230210104.","journal-title":"Networks"},{"key":"303_CR8","doi-asserted-by":"publisher","first-page":"S10","DOI":"10.1186\/1471-2164-15-S6-S10","volume":"15","author":"P Bonizzoni","year":"2014","unstructured":"Bonizzoni P, Carrieri AP, Della Vedova G, Trucco G. Explaining evolution via constrained persistent perfect phylogeny. BMC Genomics. 2014;15:S10. https:\/\/doi.org\/10.1186\/1471-2164-15-S6-S10.","journal-title":"BMC Genomics"},{"issue":"1","key":"303_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","volume":"3","author":"M El-Kebir","year":"2016","unstructured":"El-Kebir M, Satas G, Oesper L, Raphael BJ. Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Syst. 2016;3(1):43\u201353. https:\/\/doi.org\/10.1016\/j.cels.2016.07.004.","journal-title":"Cell Syst"},{"key":"303_CR10","doi-asserted-by":"publisher","unstructured":"Dai J, Rubel T, Han Y, Molloy E. Dollo-CDP: a polynomial-time algorithm for the clade-constrained large dollo parsimony problem. Algorithms for Molecular Biology. 2024;19:https:\/\/doi.org\/10.1186\/s13015-023-00249-9.","DOI":"10.1186\/s13015-023-00249-9"},{"issue":"1","key":"303_CR11","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1186\/s13059-023-03106-5","volume":"24","author":"P Sashittal","year":"2023","unstructured":"Sashittal P, Zhang H, Iacobuzio-Donahue CA, Raphael BJ. ConDoR: tumor phylogeny inference with a copy-number constrained mutation loss model. Genome Biol. 2023;24(1):272\u201323.","journal-title":"Genome Biol"},{"issue":"17","key":"303_CR12","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1093\/bioinformatics\/bty589","volume":"34","author":"M El-Kebir","year":"2018","unstructured":"El-Kebir M. SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error. Bioinformatics. 2018;34(17):671\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/bty589.","journal-title":"Bioinformatics"},{"key":"303_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2021.102252","volume":"131","author":"R Bouckaert","year":"2021","unstructured":"Bouckaert R, Fischer M, Wicke K. Combinatorial perspectives on Dollo-$$k$$ characters in phylogenetics. Adv Appl Math. 2021;131:102252. https:\/\/doi.org\/10.1016\/j.aam.2021.102252.","journal-title":"Adv Appl Math"},{"issue":"1","key":"303_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0025-5564(86)90161-6","volume":"81","author":"WHE Day","year":"1986","unstructured":"Day WHE, Johnson DS, Sankoff D. The computational complexity of inferring rooted phylogenies by parsimony. Math Biosci. 1986;81(1):33\u201342. https:\/\/doi.org\/10.1016\/0025-5564(86)90161-6.","journal-title":"Math Biosci"},{"issue":"2","key":"303_CR15","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1089\/cmb.2006.13.351","volume":"13","author":"T Przytycka","year":"2006","unstructured":"Przytycka T, Davis G, Song N, Durand D. Graph theoretical insights into evolution of multidomain proteins. J Comput Biol. 2006;13(2):351\u201363. https:\/\/doi.org\/10.1089\/cmb.2006.13.351. (PMID: 16597245).","journal-title":"J Comput Biol"},{"issue":"1","key":"303_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0166-218X(96)00060-1","volume":"71","author":"LA Goldberg","year":"1996","unstructured":"Goldberg LA, Goldberg PW, Phillips CA, Sweedyk E, Warnow T. Minimizing phylogenetic number to find good evolutionary trees. Discret Appl Math. 1996;71(1):111\u201336. https:\/\/doi.org\/10.1016\/S0166-218X(96)00060-1.","journal-title":"Discret Appl Math"},{"key":"303_CR17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2012.05.035","volume":"454","author":"P Bonizzoni","year":"2012","unstructured":"Bonizzoni P, Braghin C, Dondi R, Trucco G. The binary perfect phylogeny with persistent characters. Theoret Comput Sci. 2012;454:51\u201363. https:\/\/doi.org\/10.1016\/j.tcs.2012.05.035.","journal-title":"Theoret Comput Sci"},{"key":"303_CR18","doi-asserted-by":"publisher","unstructured":"Gusfield D. Persistent phylogeny: a galled-tree and integer linear programming approach. In: Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics. BCB \u201915. New York, NY, USA: Association for Computing Machinery; 2015. p. 443\u201351. https:\/\/doi.org\/10.1145\/2808719.2808765.","DOI":"10.1145\/2808719.2808765"},{"key":"303_CR19","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2016.08.015","volume":"658","author":"P Bonizzoni","year":"2017","unstructured":"Bonizzoni P, Carrieri AP, Della Vedova G, Rizzi R, Trucco G. A colored graph approach to perfect phylogeny with persistent characters. Theoret Comput Sci. 2017;658:60\u201373. https:\/\/doi.org\/10.1016\/j.tcs.2016.08.015. (Formal Languages and Automata: Models, Methods and Application In honour of the 70th birthday of Antonio Restivo).","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"303_CR20","doi-asserted-by":"publisher","first-page":"5327","DOI":"10.1038\/s41467-020-19119-8","volume":"11","author":"K Morita","year":"2020","unstructured":"Morita K, Wang F, Jahn K, Hu T, Tanaka T, Sasaki Y, et al. Clonal evolution of acute myeloid leukemia revealed by high-throughput single-cell genomics. Nat Commun. 2020;11(1):5327\u201317.","journal-title":"Nat Commun"},{"issue":"2","key":"303_CR21","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.bbcan.2017.01.003","volume":"1867","author":"A Davis","year":"2017","unstructured":"Davis A, Gao R, Navin N. Tumor evolution: linear, branching, neutral or punctuated? Biochim Biophys Acta (BBA). 2017;1867(2):151\u201361. https:\/\/doi.org\/10.1016\/j.bbcan.2017.01.003. (Evolutionary principles - heterogeneity in cancer?).","journal-title":"Biochim Biophys Acta (BBA)"},{"issue":"11","key":"303_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2020.101655","volume":"23","author":"E Sadeqi Azer","year":"2020","unstructured":"Sadeqi Azer E, Haghir Ebrahimabadi M, Maliki\u0107 S, Khardon R, Sahinalp SC. Tumor phylogeny topology inference via deep learning. iScience. 2020;23(11):101655. https:\/\/doi.org\/10.1016\/j.isci.2020.101655.","journal-title":"iScience"},{"key":"303_CR23","doi-asserted-by":"publisher","unstructured":"Weber LL, El-Kebir M. Phyolin: Identifying a Linear Perfect Phylogeny in Single-Cell DNA Sequencing Data of Tumors. In: Kingsford C, Pisanti N. (eds.) 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 172, pp. 5\u20131514. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2020. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2020.5 .","DOI":"10.4230\/LIPIcs.WABI.2020.5"},{"issue":"3","key":"303_CR24","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson D, Gross O. Incidence matrices and interval graphs. Pac J Math. 1965;15(3):835\u201355. https:\/\/doi.org\/10.2140\/pjm.1965.15.835.","journal-title":"Pac J Math"},{"issue":"3","key":"303_CR25","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth KS, Lueker GS. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci. 1976;13(3):335\u201379. https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1.","journal-title":"J Comput Syst Sci"},{"issue":"7341","key":"303_CR26","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1038\/nature09807","volume":"472","author":"N Navin","year":"2011","unstructured":"Navin N, Kendall J, Troge J, Andrews P, Rodgers L, McIndoo J, et al. Tumour evolution inferred by single-cell sequencing. Nature. 2011;472(7341):90\u20134.","journal-title":"Nature"},{"key":"303_CR27","unstructured":"Booth KS. PhD thesis, University of California, Berkeley, 1975. AAI7615117"},{"key":"303_CR28","doi-asserted-by":"publisher","unstructured":"Ma\u0148uch J, Patterson M, Chauve C. Hardness results on the gapped consecutive-ones property problem. Discrete Applied Mathematics 2012;160(18), 2760\u20132768. https:\/\/doi.org\/10.1016\/j.dam.2012.03.019 . V Latin American Algorithms, Graphs, and Optimization Symposium \u2014 Gramado, Brazil, 2009","DOI":"10.1016\/j.dam.2012.03.019"},{"issue":"2","key":"303_CR29","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","volume":"18","author":"RR Hudson","year":"2002","unstructured":"Hudson RR. Generating samples under a Wright-Fisher neutral model of genetic variation. Bioinformatics. 2002;18(2):337\u20138. https:\/\/doi.org\/10.1093\/bioinformatics\/18.2.337.","journal-title":"Bioinformatics"},{"key":"303_CR30","unstructured":"Xie S. Towards characterizing the solution space of the 1-Dollo phylogeny problem. University of Illinois Urbana-Champaign; 2019."},{"issue":"1","key":"303_CR31","doi-asserted-by":"publisher","first-page":"53","DOI":"10.3233\/FI-1983-6104","volume":"6","author":"W Lipski Jr","year":"1983","unstructured":"Lipski W Jr. Generalizations of the consecutive ones property and related NP-Complete problems. Fund Inform. 1983;6(1):53\u201369. https:\/\/doi.org\/10.3233\/FI-1983-6104.","journal-title":"Fund Inform"},{"key":"303_CR32","doi-asserted-by":"publisher","unstructured":"Chimani M, Rahmann S, B\u00f6cker S. Exact ILP solutions for phylogenetic minimum flip problems. In: Zhang A, Borodovsky M, \u00d6zsoyoglu G, Mikler AR (eds.) Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, BCB 2010, Niagara Falls, NY, USA, August 2-4, 2010, pp. 147\u2013153. ACM, 2010. https:\/\/doi.org\/10.1145\/1854776.1854800 .","DOI":"10.1145\/1854776.1854800"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-026-00303-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-026-00303-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-026-00303-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T13:03:25Z","timestamp":1786626205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s13015-026-00303-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["303"],"URL":"https:\/\/doi.org\/10.1186\/s13015-026-00303-2","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"28 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","label":"Ethical approval and consent to participate","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors consent for publication.","order":2,"name":"Ethics","label":"Consent for publication","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"11"}}