{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T07:02:28Z","timestamp":1776322948055,"version":"3.50.1"},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2018,9,9]],"date-time":"2018-09-09T00:00:00Z","timestamp":1536451200000},"content-version":"vor","delay-in-days":8,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["OCI-0725070"],"award-info":[{"award-number":["OCI-0725070"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1238993"],"award-info":[{"award-number":["ACI-1238993"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010443","name":"University of Illinois","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010443","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Urbana-Champaign and its National Center for Supercomputing Applications"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Cancer is characterized by intra-tumor heterogeneity, the presence of distinct cell populations with distinct complements of somatic mutations, which include single-nucleotide variants (SNVs) and copy-number aberrations (CNAs). Single-cell sequencing technology enables one to study these cell populations at single-cell resolution. Phylogeny estimation algorithms that employ appropriate evolutionary models are key to understanding the evolutionary mechanisms behind intra-tumor heterogeneity.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We introduce Single-cell Phylogeny Reconstruction (SPhyR), a method for tumor phylogeny estimation from single-cell sequencing data. In light of frequent loss of SNVs due to CNAs in cancer, SPhyR employs the k-Dollo evolutionary model, where a mutation can only be gained once but lost k times. Underlying SPhyR is a novel combinatorial characterization of solutions as constrained integer matrix completions, based on a connection to the cladistic multi-state perfect phylogeny problem. SPhyR outperforms existing methods on simulated data and on a metastatic colorectal cancer.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>SPhyR is available on https:\/\/github.com\/elkebir-group\/SPhyR.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty589","type":"journal-article","created":{"date-parts":[[2018,7,6]],"date-time":"2018-07-06T01:20:56Z","timestamp":1530840056000},"page":"i671-i679","source":"Crossref","is-referenced-by-count":130,"title":["SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error"],"prefix":"10.1093","volume":"34","author":[{"given":"Mohammed","family":"El-Kebir","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA"}]}],"member":"286","published-online":{"date-parts":[[2018,9,8]]},"reference":[{"key":"2023061313510496700_bty589-B1","doi-asserted-by":"crossref","first-page":"1216","DOI":"10.1137\/S0097539793244587","article-title":"A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed","volume":"23","author":"Agarwala","year":"1994","journal-title":"SIAM J. Comput."},{"key":"2023061313510496700_bty589-B2","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55719-9_80","article-title":"Two strikes against perfect phylogeny","volume-title":"Automata, Languages and Programming","author":"Bodlaender","year":"1992"},{"key":"2023061313510496700_bty589-B3","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2012.05.035","article-title":"The binary perfect phylogeny with persistent characters","volume":"454","author":"Bonizzoni","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"2023061313510496700_bty589-B4","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2016.08.015","article-title":"A colored graph approach to perfect phylogeny with persistent characters","volume":"658","author":"Bonizzoni","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"2023061313510496700_bty589-B5","doi-asserted-by":"crossref","DOI":"10.1145\/3107411.3107441","article-title":"Beyond perfect phylogeny: multisample phylogeny reconstruction via ilp","volume-title":"Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics","author":"Bonizzoni","year":"2017"},{"key":"2023061313510496700_bty589-B6","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45655-4_42","article-title":"Supertrees by Flipping","volume-title":"Computing and Combinatorics","author":"Chen","year":"2002"},{"key":"2023061313510496700_bty589-B7","doi-asserted-by":"crossref","DOI":"10.1145\/1854776.1854800","article-title":"Exact ILP solutions for phylogenetic minimum flip problems","volume-title":"Proceedings of the First ACM BCB","author":"Chimani","year":"2010"},{"key":"2023061313510496700_bty589-B8","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":"2023061313510496700_bty589-B9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/s13059-015-0602-8","article-title":"PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors","volume":"16","author":"Deshwar","year":"2015","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B10","first-page":"164","article-title":"Le lois de l\u2019\u00e9volution","volume":"VII","author":"Dollo","year":"1893","journal-title":"Bull. Soc. Belge G\u00e9ol. Pal\u00e9ontol.Hydrol."},{"key":"2023061313510496700_bty589-B11","doi-asserted-by":"crossref","first-page":"i62","DOI":"10.1093\/bioinformatics\/btv261","article-title":"Reconstruction of clonal trees and tumor composition from multi-sample sequencing data","volume":"31","author":"El-Kebir","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061313510496700_bty589-B12","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":"2023061313510496700_bty589-B13","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0025-5564(75)90040-1","article-title":"An idealized concept of the true cladistic character","volume":"23","author":"Estabrook","year":"1975","journal-title":"Math. Biosci."},{"key":"2023061313510496700_bty589-B14","article-title":"The perfect phylogeny problem","volume-title":"Steiner Trees in Industries","author":"Fern\u00e1ndez-Baca","year":"2000"},{"key":"2023061313510496700_bty589-B15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary trees","volume":"21","author":"Gusfield","year":"1991","journal-title":"Networks"},{"key":"2023061313510496700_bty589-B16","doi-asserted-by":"crossref","DOI":"10.1145\/2808719.2808765","article-title":"Persistent phylogeny: a galled-tree and integer linear programming approach","volume-title":"BCB 2015\u20146th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics","author":"Gusfield","year":"2015"},{"key":"2023061313510496700_bty589-B17","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under a Wright\u2013Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023061313510496700_bty589-B18","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1186\/s13059-016-0936-x","article-title":"Tree inference for single-cell data","volume":"17","author":"Jahn","year":"2016","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B19","doi-asserted-by":"crossref","first-page":"1749","DOI":"10.1137\/S0097539794279067","article-title":"A fast algorithm for the computation and enumeration of perfect phylogenies","volume":"26","author":"Kannan","year":"1997","journal-title":"SIAM J. Comput."},{"key":"2023061313510496700_bty589-B20","doi-asserted-by":"crossref","first-page":"1885","DOI":"10.1101\/gr.220707.117","article-title":"Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors","volume":"27","author":"Kuipers","year":"2017","journal-title":"Genome Res."},{"key":"2023061313510496700_bty589-B21","doi-asserted-by":"crossref","first-page":"1287","DOI":"10.1101\/gr.209973.116","article-title":"Single cell DNA sequencing reveals a late-dissemination model in metastatic colorectal cancer","volume":"27","author":"Leung","year":"2017","journal-title":"Genome Res."},{"key":"2023061313510496700_bty589-B22","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","article-title":"Clonality inference in multiple tumor samples using phylogeny","volume":"31","author":"Malikic","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061313510496700_bty589-B23","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1186\/s13059-014-0452-9","article-title":"Cancer genomics: one cell at a time","volume":"15","author":"Navin","year":"2014","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B24","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1016\/j.cell.2012.04.023","article-title":"The life history of 21 breast cancers","volume":"149","author":"Nik-Zainal","year":"2012","journal-title":"Cell"},{"key":"2023061313510496700_bty589-B25","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1126\/science.959840","article-title":"The clonal evolution of tumor cell populations","volume":"194","author":"Nowell","year":"1976","journal-title":"Science"},{"key":"2023061313510496700_bty589-B26","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/S0097539702406510","article-title":"Incomplete directed perfect phylogeny","volume":"33","author":"Pe\u2019er","year":"2004","journal-title":"SIAM J. Comput."},{"key":"2023061313510496700_bty589-B27","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1186\/s13059-015-0647-8","article-title":"Fast and scalable inference of multi-sample cancer lineages","volume":"16","author":"Popic","year":"2015","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B28","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1186\/s13059-016-0929-9","article-title":"OncoNEM: inferring tumor evolution from single-cell sequencing data","volume":"17","author":"Ross","year":"2016","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B29","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1038\/nrc3971","article-title":"Tumorigenesis: it takes a village","volume":"15","author":"Tabassum","year":"2015","journal-title":"Nat. Rev. Cancer"},{"key":"2023061313510496700_bty589-B30","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1186\/s13059-015-0592-6","article-title":"BitPhylogeny: a probabilistic framework for reconstructing intra-tumor phylogenies","volume":"16","author":"Yuan","year":"2015","journal-title":"Genome Biol."},{"key":"2023061313510496700_bty589-B31","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1186\/s13059-017-1311-2","article-title":"SiFit: inferring tumor trees from single-cell sequencing data under finite-sites models","volume":"18","author":"Zafar","year":"2017","journal-title":"Genome Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i671\/50582515\/bioinformatics_34_17_i671.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i671\/50582515\/bioinformatics_34_17_i671.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T13:53:29Z","timestamp":1686664409000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/17\/i671\/5093218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,1]]},"references-count":31,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2018,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty589","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,9,1]]},"published":{"date-parts":[[2018,9,1]]}}}