{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T23:51:42Z","timestamp":1778543502322,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 1850502"],"award-info":[{"award-number":["CCF 1850502"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 2046488"],"award-info":[{"award-number":["CCF 2046488"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Cancer arises from an evolutionary process where somatic mutations give rise to clonal expansions. Reconstructing this evolutionary process is useful for treatment decision-making as well as understanding evolutionary patterns across patients and cancer types. In particular, classifying a tumor\u2019s evolutionary process as either linear or branched and understanding what cancer types and which patients have each of these trajectories could provide useful insights for both clinicians and researchers. While comprehensive cancer phylogeny inference from single-cell DNA sequencing data is challenging due to limitations with current sequencing technology and the complexity of the resulting problem, current data might provide sufficient signal to accurately classify a tumor\u2019s evolutionary history as either linear or branched.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We introduce the Linear Perfect Phylogeny Flipping (LPPF) problem as a means of testing two alternative hypotheses for the pattern of evolution, which we prove to be NP-hard. We develop Phyolin, which uses constraint programming to solve the LPPF problem. Through both in silico experiments and real data application, we demonstrate the performance of our method, outperforming a competing machine learning approach.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>Phyolin is an accurate, easy to use and fast method for classifying an evolutionary trajectory as linear or branched given a tumor\u2019s single-cell DNA sequencing data.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-021-00194-5","type":"journal-article","created":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T11:11:06Z","timestamp":1625569866000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Distinguishing linear and branched evolution given single-cell DNA sequencing data of tumors"],"prefix":"10.1186","volume":"16","author":[{"given":"Leah L.","family":"Weber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1468-2407","authenticated-orcid":false,"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"issue":"4260","key":"194_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.","journal-title":"Science"},{"issue":"1","key":"194_CR2","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1186\/s13059-016-0936-x","volume":"17","author":"K Jahn","year":"2016","unstructured":"Jahn K, Kuipers J, Beerenwinkel N. Tree inference for single-cell data. Genome Biol. 2016;17(1):86.","journal-title":"Genome Biol"},{"issue":"17","key":"194_CR3","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.","journal-title":"Bioinformatics"},{"issue":"1","key":"194_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-016-0929-9","volume":"17","author":"EM Ross","year":"2016","unstructured":"Ross EM, Markowetz F. OncoNEM: inferring tumor evolution from single-cell sequencing data. Genome Biol. 2016;17(1):1\u201314.","journal-title":"Genome Biol"},{"issue":"12","key":"194_CR5","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1093\/bioinformatics\/btv261","volume":"31","author":"M El-Kebir","year":"2015","unstructured":"El-Kebir M, Oesper L, Acheson-Field H, Raphael BJ. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics. 2015;31(12):62\u201370.","journal-title":"Bioinformatics"},{"issue":"1","key":"194_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1186\/s13059-015-0602-8","volume":"16","author":"AG Deshwar","year":"2015","unstructured":"Deshwar AG, Vembu S, Yung CK, Jang GH, Stein L, Morris Q. PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 2015;16(1):35.","journal-title":"Genome Biol"},{"issue":"1","key":"194_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-019-10737-5","volume":"10","author":"S Malikic","year":"2019","unstructured":"Malikic S, Jahn K, Kuipers J, Sahinalp SC, Beerenwinkel N. Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data. Nat Commun. 2019;10(1):1\u201312.","journal-title":"Nat Commun"},{"issue":"11","key":"194_CR8","doi-asserted-by":"publisher","first-page":"1847","DOI":"10.1101\/gr.243121.118","volume":"29","author":"H Zafar","year":"2019","unstructured":"Zafar H, Navin N, Chen K, Nakhleh L. SiCloneFit: Bayesian inference of population structure, genotype, and phylogeny of tumor clones from single-cell genome sequencing data. Genome Res. 2019;29(11):1847\u201359.","journal-title":"Genome Res"},{"issue":"11","key":"194_CR9","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1101\/gr.234435.118","volume":"29","author":"S Malikic","year":"2019","unstructured":"Malikic S, Mehrabadi FR, Ciccolella S, Rahman MK, Ricketts C, Haghshenas E, Seidman D, Hach F, Hajirasouliha I, Sahinalp SC. PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data. Genome Res. 2019;29(11):1860\u201377.","journal-title":"Genome Res"},{"issue":"1","key":"194_CR10","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.","journal-title":"Cell Syst"},{"issue":"1","key":"194_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1186\/s13015-019-0155-6","volume":"14","author":"Y Qi","year":"2019","unstructured":"Qi Y, Pradhan D, El-Kebir M. Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors. Algorithms Mol Biol. 2019;14(1):19.","journal-title":"Algorithms Mol Biol"},{"issue":"38","key":"194_CR12","doi-asserted-by":"publisher","first-page":"11923","DOI":"10.1073\/pnas.1513988112","volume":"112","author":"Y Fu","year":"2015","unstructured":"Fu Y, Li C, Lu S, Zhou W, Tang F, Xie XS, Huang Y. Uniform and accurate single-cell sequencing based on emulsion whole-genome amplification. Proc Natl Acad Sci. 2015;112(38):11923\u20138.","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"194_CR13","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) Rev Cancer. 2017;1867(2):151\u201361.","journal-title":"Biochim Biophys Acta (BBA) Rev Cancer"},{"issue":"11","key":"194_CR14","doi-asserted-by":"publisher","first-page":"101655","DOI":"10.1016\/j.isci.2020.101655","volume":"23","author":"ES Azer","year":"2020","unstructured":"Azer ES, Ebrahimabadi MH, Maliki\u0107 S, Khardon R, Sahinalp SC. Tumor phylogeny topology inference via deep learning. iScience. 2020;23(11):101655.","journal-title":"iScience"},{"key":"194_CR15","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9432.001.0001","volume-title":"ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks","author":"D Gusfield","year":"2014","unstructured":"Gusfield D. ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks. London: MIT Press; 2014."},{"key":"194_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge: Cambridge University Press; 1997. https:\/\/doi.org\/10.1017\/CBO9780511574931."},{"issue":"38","key":"194_CR17","doi-asserted-by":"publisher","first-page":"11923","DOI":"10.1073\/pnas.1513988112","volume":"112","author":"Y Fu","year":"2015","unstructured":"Fu Y, Li C, Lu S, Zhou W, Tang F, Xie XS, Huang Y. Uniform and accurate single-cell sequencing based on emulsion whole-genome amplification. Proc Natl Acad Sci USA. 2015;112(38):11923\u20138.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"2","key":"194_CR18","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/TCBB.2006.26","volume":"3","author":"D Chen","year":"2006","unstructured":"Chen D, Eulenstein O, Fernandez-Baca D, Sanderson M. Minimum-flip supertrees: complexity and algorithms. IEEE\/ACM Trans Comput Biol Bioinform. 2006;3(2):165\u201373.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"1","key":"194_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis M. Computing the minimum fill-in is NP-complete. SIAM J Algebraic Discret Methods. 1981;2(1):77\u20139.","journal-title":"SIAM J Algebraic Discret Methods"},{"key":"194_CR20","volume-title":"Artificial intelligence: a modern approach","author":"S Russell","year":"2010","unstructured":"Russell S, Norvig P. Artificial intelligence: a modern approach. 3rd ed. Harlow: Pearson; 2010.","edition":"3"},{"issue":"1","key":"194_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-019-13993-7","volume":"11","author":"K Morita","year":"2020","unstructured":"Morita K, Wang F, Jahn K, Hu T, Tanaka T, Sasaki Y, Kuipers J, Loghavi S, Wang SA, Yan Y, et al. Clonal evolution of acute myeloid leukemia revealed by high-throughput single-cell genomics. Nat Commun. 2020;11(1):1\u201317.","journal-title":"Nat Commun"},{"issue":"50","key":"194_CR22","doi-asserted-by":"publisher","first-page":"17947","DOI":"10.1073\/pnas.1420822111","volume":"111","author":"C Gawad","year":"2014","unstructured":"Gawad C, Koh W, Quake SR. Dissecting the clonal origins of childhood acute lymphoblastic leukemia by single-cell genomics. Proc Natl Acad Sci. 2014;111(50):17947\u201352.","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"194_CR23","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\u2013Fisher neutral model of genetic variation. Bioinformatics. 2002;18(2):337\u20138.","journal-title":"Bioinformatics"},{"issue":"20","key":"194_CR24","first-page":"4191","volume":"120","author":"A Schuh","year":"2012","unstructured":"Schuh A, Becq J, Humphray S, Alexa A, Burns A, Clifford R, Feller SM, Grocock R, Henderson S, Khrebtukova I, et al. Monitoring chronic lymphocytic leukemia progression by whole genome sequencing reveals heterogeneous clonal evolution patterns. Blood J Am Soc Hematol. 2012;120(20):4191\u20136.","journal-title":"Blood J Am Soc Hematol"},{"issue":"10","key":"194_CR25","doi-asserted-by":"publisher","first-page":"1008240","DOI":"10.1371\/journal.pcbi.1008240","volume":"16","author":"LL Weber","year":"2020","unstructured":"Weber LL, Aguse N, Chia N, El-Kebir M. PhyDOSE: design of follow-up single-cell sequencing experiments of tumors. PLoS Comput Biol. 2020;16(10):1008240. https:\/\/doi.org\/10.1371\/journal.pcbi.1008240.","journal-title":"PLoS Comput Biol"},{"issue":"11","key":"194_CR26","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. Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors. Genome Res. 2017;27(11):1885\u201394.","journal-title":"Genome Res"},{"key":"194_CR27","doi-asserted-by":"publisher","DOI":"10.1101\/2020.02.07.925743","author":"K Morita","year":"2020","unstructured":"Morita K, Wang F, Jahn K, Kuipers J, Yan Y, Matthews J, Little L, Gumbs C, Chen S, Zhang J, Song X, Thompson E, Patel K, Bueso-Ramos C, DiNardo CD, Ravandi F, Jabbour E, Andreeff M, Cortes J. MKonopleva, K Bhalla, G Garcia-Manero, H Kantarjian, N Beerenwinkel, N Navin, PA Futreal, K Takahashi. Clonal Evolution of Acute Myeloid Leukemia Revealed by High-Throughput Single-Cell Genomics. bioRxiv. 2020. https:\/\/doi.org\/10.1101\/2020.02.07.925743.","journal-title":"Clonal Evolution of Acute Myeloid Leukemia Revealed by High-Throughput Single-Cell GenomicsbioRxiv"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00194-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00194-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00194-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T11:11:10Z","timestamp":1625569870000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00194-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["194"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00194-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,6]]},"assertion":[{"value":"2 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"14"}}