{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T22:43:49Z","timestamp":1757630629964,"version":"3.44.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T00:00:00Z","timestamp":1753488000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T00:00:00Z","timestamp":1753488000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"H2020 Marie Sk\u0142odowska-Curie Actions,European Union","award":["872539","872539"],"award-info":[{"award-number":["872539","872539"]}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022YRB97K"],"award-info":[{"award-number":["2022YRB97K"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["CN_00000041"],"award-info":[{"award-number":["CN_00000041"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s11047-025-10039-4","type":"journal-article","created":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T14:49:16Z","timestamp":1753541356000},"page":"781-795","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On recognizing graphs representing persistent perfect phylogenies"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7289-4988","authenticated-orcid":false,"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5584-3089","authenticated-orcid":false,"given":"Gianluca","family":"Della Vedova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5977-9467","authenticated-orcid":false,"given":"Mauricio","family":"Soto Gomez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5904-0969","authenticated-orcid":false,"given":"Gabriella","family":"Trucco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Bernardini G, Bonizzoni P, Gawrychowski P (2021) Incomplete directed perfect phylogeny in linear time. In: Lubiw, A., Salavatipour, M., He, M. (eds.) Workshop on Algorithms and Data Structures. pp. 172\u2013185. No. 12808. https:\/\/doi.org\/10.1007\/978-3-030-83508-8_13","key":"10039_CR1","DOI":"10.1007\/978-3-030-83508-8_13"},{"issue":"3","key":"10039_CR2","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-0094-3","volume":"48","author":"P Bonizzoni","year":"2007","unstructured":"Bonizzoni P (2007) A linear-time algorithm for the perfect phylogeny haplotype problem. Algorithmica 48(3):267\u2013285. https:\/\/doi.org\/10.1007\/s00453-007-0094-3","journal-title":"Algorithmica"},{"key":"10039_CR3","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 (2012) The binary perfect phylogeny with persistent characters. Theoret Comput Sci 454:51\u201363. https:\/\/doi.org\/10.1016\/j.tcs.2012.05.035","journal-title":"Theoret Comput Sci"},{"doi-asserted-by":"publisher","unstructured":"Bonizzoni P, Carrieri AP, Della\u00a0Vedova G, Dondi R, Przytycka TM (2014) When and How the Perfect Phylogeny Model Explains Evolution. In: Discrete and Topological Models in Molecular Biology, pp. 67\u201383. Natural Computing Series, Springer Berlin Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-40193-0_4","key":"10039_CR4","DOI":"10.1007\/978-3-642-40193-0_4"},{"key":"10039_CR5","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 (2017) A colored graph approach to perfect phylogeny with persistent characters. Theoret Comput Sci 658:60\u201373. https:\/\/doi.org\/10.1016\/j.tcs.2016.08.015","journal-title":"Theoret Comput Sci"},{"issue":"6","key":"10039_CR6","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 (2014) Explaining evolution via constrained persistent perfect phylogeny. BMC Genomics 15(6):S10. https:\/\/doi.org\/10.1186\/1471-2164-15-S6-S10","journal-title":"BMC Genomics"},{"issue":"5","key":"10039_CR7","doi-asserted-by":"publisher","first-page":"1410","DOI":"10.1109\/tcbb.2018.2865729","volume":"16","author":"P Bonizzoni","year":"2018","unstructured":"Bonizzoni P, Ciccolella S, Della Vedova G, Soto Gomez M (2018) Does relaxing the infinite sites assumption give better tumor phylogenies? an ILP-based comparative approach. IEEE\/ACM Trans Comput Biol Bioinf 16(5):1410\u20131423. https:\/\/doi.org\/10.1109\/tcbb.2018.2865729","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"10039_CR8","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-020-03736-7","author":"S Ciccolella","year":"2020","unstructured":"Ciccolella S, Soto Gomez M, Patterson MD, Della Vedova G, Hajirasouliha I, Bonizzoni P (2020) gpps: an ILP-based approach for inferring cancer progression with mutation losses from single cell data. BMC Bioinf. https:\/\/doi.org\/10.1186\/s12859-020-03736-7","journal-title":"BMC Bioinf"},{"issue":"17","key":"10039_CR9","doi-asserted-by":"publisher","first-page":"i671","DOI":"10.1093\/bioinformatics\/bty589","volume":"34","author":"M El-Kebir","year":"2018","unstructured":"El-Kebir M (2018) SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error. Bioinformatics 34(17):i671\u2013i679. https:\/\/doi.org\/10.1093\/bioinformatics\/bty589","journal-title":"Bioinformatics"},{"issue":"1","key":"10039_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D Gusfield","year":"1991","unstructured":"Gusfield D (1991) Efficient algorithms for inferring evolutionary trees. Networks 21(1):19\u201328. https:\/\/doi.org\/10.1002\/net.3230210104","journal-title":"Networks"},{"doi-asserted-by":"publisher","unstructured":"Gusfield D (2015) Persistent phylogeny: a galled-tree and integer linear programming approach. In: Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics. pp. 443\u2013451. ACM, ACM. https:\/\/doi.org\/10.1145\/2808719.2808765","key":"10039_CR11","DOI":"10.1145\/2808719.2808765"},{"doi-asserted-by":"publisher","unstructured":"Gusfield D (2002) Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In: RECOMB 2002. pp. 166\u2013175. ACM. https:\/\/doi.org\/10.1145\/565196.565218","key":"10039_CR12","DOI":"10.1145\/565196.565218"},{"issue":"11","key":"10039_CR13","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1101\/gr.220707.117","volume":"27","author":"J Kuipers","year":"2017","unstructured":"Kuipers J, Jahn K, Raphael BJ, Beerenwinkel N (2017) Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors. Genome Res 27(11):1885\u20131894. https:\/\/doi.org\/10.1101\/gr.220707.117","journal-title":"Genome Res"},{"issue":"3","key":"10039_CR14","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1137\/s0097539702406510","volume":"33","author":"I Pe\u2019er","year":"2004","unstructured":"Pe\u2019er I, Pupko T, Shamir R, Sharan R (2004) Incomplete directed perfect phylogeny. SIAM J Comput 33(3):590\u2013607. https:\/\/doi.org\/10.1137\/s0097539702406510","journal-title":"SIAM J Comput"},{"key":"10039_CR15","volume-title":"Parsimony, Phylogeny, and Genomics","author":"IB Rogozin","year":"2006","unstructured":"Rogozin IB, Wolf YI, Babenko VN, Koonin EV (2006) Dollo parsimony and the reconstruction of genome evolution. In: Albert I (ed) Parsimony, Phylogeny, and Genomics. Oxford University Press, Oxford"},{"key":"10039_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2020.102046","volume":"119","author":"K Wicke","year":"2020","unstructured":"Wicke K, Fischer M (2020) Combinatorial views on persistent characters in phylogenetics. Adv Appl Math 119:102046. https:\/\/doi.org\/10.1016\/j.aam.2020.102046","journal-title":"Adv Appl Math"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10039-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10039-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10039-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T19:19:58Z","timestamp":1757531998000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10039-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10039"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10039-4","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"29 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}