{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T18:23:35Z","timestamp":1777055015640,"version":"3.51.4"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"UIUC Center for Computational Biotechnology and Genomic Medicine","award":["CSN 1624790"],"award-info":[{"award-number":["CSN 1624790"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1850502"],"award-info":[{"award-number":["1850502"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Cancer phylogenies are key to studying tumorigenesis and have clinical implications. Due to the heterogeneous nature of cancer and limitations in current sequencing technology, current cancer phylogeny inference methods identify a large solution space of plausible phylogenies. To facilitate further downstream analyses, methods that accurately summarize such a set T of cancer phylogenies are imperative. However, current summary methods are limited to a single consensus tree or graph and may miss important topological features that are present in different subsets of candidate trees.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We introduce the Multiple Consensus Tree (MCT) problem to simultaneously cluster T and infer a consensus tree for each cluster. We show that MCT is NP-hard, and present an exact algorithm based on mixed integer linear programming (MILP). In addition, we introduce a heuristic algorithm that efficiently identifies high-quality consensus trees, recovering all optimal solutions identified by the MILP in simulated data at a fraction of the time. We demonstrate the applicability of our methods on both simulated and real data, showing that our approach selects the number of clusters depending on the complexity of the solution space T.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/elkebir-group\/MCT.<\/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\/btz312","type":"journal-article","created":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T03:18:35Z","timestamp":1557976715000},"page":"i408-i416","source":"Crossref","is-referenced-by-count":35,"title":["Summarizing the solution space in tumor phylogeny inference by multiple consensus trees"],"prefix":"10.1093","volume":"35","author":[{"given":"Nuraini","family":"Aguse","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanyuan","family":"Qi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,7,5]]},"reference":[{"key":"2023062712364404200_btz312-B1","author":"Bonizzoni","year":"2017"},{"key":"2023062712364404200_btz312-B2","first-page":"3076","author":"Dang","year":"2017"},{"key":"2023062712364404200_btz312-B3","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":"2023062712364404200_btz312-B4","first-page":"37","article-title":"Inferring tree models for oncogenesis from comparative genome hybridization data","volume":"6","author":"Desper","year":"1999","journal-title":"JCB"},{"key":"2023062712364404200_btz312-B5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-319-31957-5_6","volume-title":"Research in Computational Molecular Biology","author":"Donmez","year":"2016"},{"key":"2023062712364404200_btz312-B6","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":"2023062712364404200_btz312-B7","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":"2023062712364404200_btz312-B8","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":"2023062712364404200_btz312-B9","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":"2023062712364404200_btz312-B10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","article-title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","volume":"6","author":"Gabow","year":"1986","journal-title":"Combinatorica"},{"key":"2023062712364404200_btz312-B11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2023062712364404200_btz312-B12","doi-asserted-by":"crossref","DOI":"10.1145\/3233547.3233584","article-title":"A consensus approach to infer tumor evolutionary histories","author":"Govek","year":"2018"},{"key":"2023062712364404200_btz312-B13","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":"2023062712364404200_btz312-B14","doi-asserted-by":"crossref","first-page":"2109","DOI":"10.1056\/NEJMoa1616288","article-title":"Tracking the evolution of non\u2013small-cell lung cancer","volume":"376","author":"Jamal-Hanjani","year":"2017","journal-title":"N. Engl. J. Med"},{"key":"2023062712364404200_btz312-B15","doi-asserted-by":"crossref","first-page":"E5528","DOI":"10.1073\/pnas.1522203113","article-title":"Assessing intratumor heterogeneity and tracking longitudinal and spatial clonal evolutionary history by next-generation sequencing","volume":"113","author":"Jiang","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023062712364404200_btz312-B16","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 Bioinformatics"},{"key":"2023062712364404200_btz312-B17","first-page":"22:1","author":"Karpov","year":"2018"},{"key":"2023062712364404200_btz312-B18","volume-title":"The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms.","author":"Knuth","year":"1997"},{"key":"2023062712364404200_btz312-B19","doi-asserted-by":"crossref","first-page":"517.","DOI":"10.1038\/nature24473","article-title":"A neoantigen fitness model predicts tumour response to checkpoint blockade immunotherapy","volume":"551","author":"\u0141uksza","year":"2017","journal-title":"Nature"},{"key":"2023062712364404200_btz312-B20","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":"2023062712364404200_btz312-B21","doi-asserted-by":"crossref","first-page":"283ra54","DOI":"10.1126\/scitranslmed.aaa1408","article-title":"Clonal status of actionable driver events and the timing of mutational processes in cancer evolution","volume":"7","author":"McGranahan","year":"2015","journal-title":"Sci. Transl. Med"},{"key":"2023062712364404200_btz312-B22","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":"2023062712364404200_btz312-B23","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":"2023062712364404200_btz312-B24","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":"2023062712364404200_btz312-B25","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":"2023062712364404200_btz312-B26","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/nmeth.2883","article-title":"PyClone: statistical inference of clonal population structure in cancer","volume":"11","author":"Roth","year":"2014","journal-title":"Nat. Methods"},{"key":"2023062712364404200_btz312-B27","volume-title":"Combinatorial Optimization \u2013 Polyhedra and Efficiency","author":"Schrijver","year":"2003"},{"key":"2023062712364404200_btz312-B28","first-page":"126","article-title":"Distributions of tree comparison metrics\u2014some new results","volume":"42","author":"Steel","year":"1993","journal-title":"Syst. Biol"},{"key":"2023062712364404200_btz312-B29","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":"2023062712364404200_btz312-B30","author":"Turajlic","year":"2018"},{"key":"2023062712364404200_btz312-B31","doi-asserted-by":"crossref","DOI":"10.1016\/j.cell.2018.03.057","article-title":"Tracking cancer evolution reveals constrained routes to metastases: TRACERx renal","author":"Turajlic","year":"2018","journal-title":"Cell"},{"key":"2023062712364404200_btz312-B32","doi-asserted-by":"crossref","DOI":"10.1017\/9781316882313","volume-title":"Computational Phylogenetics: An Introduction to Designing Methods for Phylogeny Estimation","author":"Warnow","year":"2017","edition":"1"},{"key":"2023062712364404200_btz312-B33","volume-title":"Integer Programming. Wiley Series in Discrete Mathematics and Optimization","author":"Wolsey","year":"1998"},{"key":"2023062712364404200_btz312-B34","doi-asserted-by":"crossref","first-page":"1","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":"2023062712364404200_btz312-B35","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":"2023062712364404200_btz312-B36","doi-asserted-by":"crossref","first-page":"1755","DOI":"10.1016\/j.cell.2018.03.073","article-title":"Interfaces of malignant and immunologic clonal dynamics in ovarian cancer","volume":"173","author":"Zhang","year":"2018","journal-title":"Cell"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i408\/50721502\/bioinformatics_35_14_i408.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i408\/50721502\/bioinformatics_35_14_i408.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T12:37:32Z","timestamp":1687869452000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/14\/i408\/5529140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":36,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2019,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz312","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,7]]},"published":{"date-parts":[[2019,7]]}}}