{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:24:09Z","timestamp":1773275049973,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","funder":[{"DOI":"10.13039\/100030692","name":"Intramural Research Program","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100030692","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000054","name":"National Cancer Institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000054","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["AF-1619081"],"award-info":[{"award-number":["AF-1619081"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Indiana U. Grand Challenges Precision Health Initiative"},{"DOI":"10.13039\/100010663","name":"ERC","doi-asserted-by":"publisher","award":["CoG-770854"],"award-info":[{"award-number":["CoG-770854"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2019s Horizon 2020","award":["#754282"],"award-info":[{"award-number":["#754282"]}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["#712977"],"award-info":[{"award-number":["#712977"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["#696\/17"],"award-info":[{"award-number":["#696\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005190","name":"MRA","doi-asserted-by":"publisher","award":["#622106"],"award-info":[{"award-number":["#622106"]}],"id":[{"id":"10.13039\/100005190","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Recent advances in single-cell sequencing (SCS) offer an unprecedented insight into tumor emergence and evolution. Principled approaches to tumor phylogeny reconstruction via SCS data are typically based on general computational methods for solving an integer linear program, or a constraint satisfaction program, which, although guaranteeing convergence to the most likely solution, are very slow. Others based on Monte Carlo Markov Chain or alternative heuristics not only offer no such guarantee, but also are not faster in practice. As a result, novel methods that can scale up to handle the size and noise characteristics of emerging SCS data are highly desirable to fully utilize this technology.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We introduce PhISCS-BnB (phylogeny inference using SCS via branch and bound), a branch and bound algorithm to compute the most likely perfect phylogeny on an input genotype matrix extracted from an SCS dataset. PhISCS-BnB not only offers an optimality guarantee, but is also 10\u2013100 times faster than the best available methods on simulated tumor SCS data. We also applied PhISCS-BnB on a recently published large melanoma dataset derived from the sublineages of a cell line involving 20 clones with 2367 mutations, which returned the optimal tumor phylogeny in &amp;lt;4\u2009h. The resulting phylogeny agrees with and extends the published results by providing a more detailed picture on the clonal evolution of the tumor.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>https:\/\/github.com\/algo-cancer\/PhISCS-BnB.<\/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\/btaa464","type":"journal-article","created":{"date-parts":[[2020,7,10]],"date-time":"2020-07-10T15:11:36Z","timestamp":1594393896000},"page":"i169-i176","source":"Crossref","is-referenced-by-count":20,"title":["PhISCS-BnB: a fast branch and bound algorithm for the perfect tumor phylogeny reconstruction problem"],"prefix":"10.1093","volume":"36","author":[{"given":"Erfan","family":"Sadeqi Azer","sequence":"first","affiliation":[{"name":"Indiana University Department of Computer Science, , Bloomington, IN 47408, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farid","family":"Rashidi Mehrabadi","sequence":"additional","affiliation":[{"name":"Indiana University Department of Computer Science, , Bloomington, IN 47408, USA"},{"name":"Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salem","family":"Maliki\u0107","sequence":"additional","affiliation":[{"name":"Indiana University Department of Computer Science, , Bloomington, IN 47408, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuan Cindy","family":"Li","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"},{"name":"University of Maryland Program in Computational Biology, Bioinformatics and Genomics, , College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osnat","family":"Bartok","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science Department of Molecular Cell Biology, , Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Litchfield","sequence":"additional","affiliation":[{"name":"Cancer Evolution and Genome Instability Laboratory, Francis Crick Institute , London NW1 1AT, UK"},{"name":"Cancer Research UK Lung Cancer Centre of Excellence London, University College London Cancer Institute , London WC1E 6DD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronen","family":"Levy","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science Department of Molecular Cell Biology, , Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yardena","family":"Samuels","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science Department of Molecular Cell Biology, , Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro A","family":"Sch\u00e4ffer","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E Michael","family":"Gertz","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chi-Ping","family":"Day","sequence":"additional","affiliation":[{"name":"Laboratory of Cancer Biology and Genetics, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eva","family":"P\u00e9rez-Guijarro","sequence":"additional","affiliation":[{"name":"Laboratory of Cancer Biology and Genetics, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kerrie","family":"Marie","sequence":"additional","affiliation":[{"name":"Laboratory of Cancer Biology and Genetics, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxwell P","family":"Lee","sequence":"additional","affiliation":[{"name":"Laboratory of Cancer Biology and Genetics, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Glenn","family":"Merlino","sequence":"additional","affiliation":[{"name":"Laboratory of Cancer Biology and Genetics, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Funda","family":"Ergun","sequence":"additional","affiliation":[{"name":"Indiana University Department of Computer Science, , Bloomington, IN 47408, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health , Bethesda, MD 20892, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"2024022912015656400_btaa464-B1","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1038\/nm.3915","article-title":"Toward understanding and exploiting tumor heterogeneity","volume":"21","author":"Alizadeh","year":"2015","journal-title":"Nat. Med"},{"key":"2024022912015656400_btaa464-B2","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"Applegate","year":"2006"},{"key":"2024022912015656400_btaa464-B3","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","article-title":"Fixed-parameter tractability of graph modification problems for hereditary properties","volume":"58","author":"Cai","year":"1996","journal-title":"Inf. Process. Lett"},{"key":"2024022912015656400_btaa464-B4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TCBB.2006.26","article-title":"Minimum-flip supertrees: complexity and algorithms","volume":"3","author":"Chen","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2024022912015656400_btaa464-B5","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009"},{"key":"2024022912015656400_btaa464-B6","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":"2024022912015656400_btaa464-B7","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":"2024022912015656400_btaa464-B8","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1089\/cmb.2016.0148","article-title":"Clonality inference from single tumor samples using low-coverage sequence data","volume":"24","author":"Donmez","year":"2017","journal-title":"J. Comput. Biol"},{"key":"2024022912015656400_btaa464-B9","first-page":"1","author":"Edrisi","year":"2019"},{"key":"2024022912015656400_btaa464-B10","doi-asserted-by":"crossref","first-page":"i671","DOI":"10.1093\/bioinformatics\/bty589","article-title":"Sphyr: tumor phylogeny estimation from single-cell sequencing data under loss and error","volume":"34","author":"El-Kebir","year":"2018","journal-title":"Bioinformatics"},{"key":"2024022912015656400_btaa464-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":"2024022912015656400_btaa464-B12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","article-title":"Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures","volume":"3","author":"El-Kebir","year":"2016","journal-title":"Cell Syst"},{"key":"2024022912015656400_btaa464-B13","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/6462.6502","article-title":"Efficient algorithms for finding maximum matching in graphs","volume":"18","author":"Galil","year":"1986","journal-title":"ACM Comput. Surv"},{"key":"2024022912015656400_btaa464-B14","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":"2024022912015656400_btaa464-B15","doi-asserted-by":"crossref","DOI":"10.1017\/9781108377737","volume-title":"Integer Linear Programming in Computational and Systems Biology: An Entry-Level Text and Course","author":"Gusfield","year":"2019"},{"key":"2024022912015656400_btaa464-B17","doi-asserted-by":"crossref","first-page":"i78","DOI":"10.1093\/bioinformatics\/btu284","article-title":"A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data","volume":"30","author":"Hajirasouliha","year":"2014","journal-title":"Bioinformatics"},{"key":"2024022912015656400_btaa464-B19","first-page":"53","article-title":"Rc2: an efficient MaxSAT solver","volume":"11","author":"Ignatiev","year":"2019","journal-title":"J. Stat. Boolean Model. Comput"},{"key":"2024022912015656400_btaa464-B20","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":"2024022912015656400_btaa464-B21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/1471-2105-15-35","article-title":"Inferring clonal evolution of tumors from single nucleotide somatic mutations","volume":"15","author":"Jiao","year":"2014","journal-title":"BMC Bioinform"},{"key":"2024022912015656400_btaa464-B22","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1186\/s13015-019-0152-9","article-title":"A multi-labeled tree dissimilarity measure for comparing \u201cclonal trees\u201d of tumor progression","volume":"14","author":"Karpov","year":"2019","journal-title":"Algor. Mol. Biol"},{"key":"2024022912015656400_btaa464-B23","first-page":"127","article-title":"Advances in understanding tumour evolution through single-cell sequencing","volume":"1867","author":"Kuipers","year":"2017","journal-title":"Biochim. Biophys. Acta"},{"key":"2024022912015656400_btaa464-B24","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1016\/j.cell.2019.10.026","article-title":"Clonal decomposition and DNA replication states defined by scaled single-cell genome sequencing","volume":"179","author":"Laks","year":"2019","journal-title":"Cell"},{"key":"2024022912015656400_btaa464-B25","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":"2024022912015656400_btaa464-B26","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","author":"Malikic","year":"2019","journal-title":"Nat. Commun"},{"key":"2024022912015656400_btaa464-B27","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1101\/gr.234435.118","article-title":"PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data","volume":"29","author":"Malikic","year":"2019","journal-title":"Genome Res"},{"key":"2024022912015656400_btaa464-B28","doi-asserted-by":"crossref","first-page":"2377","DOI":"10.1214\/16-AOAS986","article-title":"A phylogenetic latent feature model for clonal deconvolution","volume":"10","author":"Marass","year":"2016","journal-title":"Ann. Appl. Stat"},{"key":"2024022912015656400_btaa464-B29","first-page":"438","author":"Martins","year":"2014"},{"key":"2024022912015656400_btaa464-B30","doi-asserted-by":"crossref","first-page":"e1003665","DOI":"10.1371\/journal.pcbi.1003665","article-title":"Sciclone: inferring clonal architecture and tracking the spatial and temporal patterns of tumor evolution","volume":"10","author":"Miller","year":"2014","journal-title":"PLoS Comput. Biol"},{"key":"2024022912015656400_btaa464-B31","doi-asserted-by":"crossref","first-page":"1889","DOI":"10.1002\/ijc.32258","article-title":"A pilot precision medicine trial for children with diffuse intrinsic pontine glioma\u2014pnoc003: a report from the pacific pediatric neuro-oncology consortium","volume":"145","author":"Mueller","year":"2019","journal-title":"Int. J. Cancer"},{"key":"2024022912015656400_btaa464-B32","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":"2024022912015656400_btaa464-B33","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":"2024022912015656400_btaa464-B34","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1038\/nmeth.3867","article-title":"Clonal genotype and population structure inference from single-cell tumor sequencing","volume":"13","author":"Roth","year":"2016","journal-title":"Nat. Methods"},{"key":"2024022912015656400_btaa464-B35","doi-asserted-by":"crossref","first-page":"i152","DOI":"10.1093\/bioinformatics\/btx270","article-title":"Tumor phylogeny inference using tree-constrained importance sampling","volume":"33","author":"Satas","year":"2017","journal-title":"Bioinformatics"},{"key":"2024022912015656400_btaa464-B36","doi-asserted-by":"crossref","first-page":"5144","DOI":"10.1038\/s41467-018-07627-7","article-title":"Single-cell mutation identification via phylogenetic inference","volume":"9","author":"Singer","year":"2018","journal-title":"Nat. Commun"},{"key":"2024022912015656400_btaa464-B37","author":"Stewart","year":"2017"},{"key":"2024022912015656400_btaa464-B38","doi-asserted-by":"crossref","first-page":"e165","DOI":"10.1093\/nar\/gkt641","article-title":"Trap: a tree approach for fingerprinting subclonal tumor composition","volume":"41","author":"Strino","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2024022912015656400_btaa464-B39","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.cell.2019.08.032","article-title":"Uvb-induced tumor heterogeneity diminishes immune response in melanoma","volume":"179","author":"Wolf","year":"2019","journal-title":"Cell"},{"key":"2024022912015656400_btaa464-B40","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1093\/bioinformatics\/btz676","article-title":"Accurate and efficient cell lineage tree inference from noisy single cell data: the maximum likelihood perfect phylogeny approach","volume":"36","author":"Wu","year":"2019","journal-title":"Bioinformatics"},{"key":"2024022912015656400_btaa464-B41","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"},{"key":"2024022912015656400_btaa464-B42","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.coisb.2017.11.008","article-title":"Computational approaches for inferring tumor evolution from single-cell genomic data","volume":"7","author":"Zafar","year":"2018","journal-title":"Curr. Opin. Syst. Biol"},{"key":"2024022912015656400_btaa464-B43","doi-asserted-by":"crossref","first-page":"1847","DOI":"10.1101\/gr.243121.118","article-title":"SiCloneFit: Bayesian inference of population structure, genotype, and phylogeny of tumor clones from single-cell genome sequencing data","volume":"29","author":"Zafar","year":"2019","journal-title":"Genome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i169\/56795552\/bioinformatics_36_supplement1_i169.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i169\/56795552\/bioinformatics_36_supplement1_i169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T07:02:40Z","timestamp":1709190160000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_1\/i169\/5870466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":41,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa464","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.02.06.938043","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,7]]},"published":{"date-parts":[[2020,7,1]]}}}