{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T07:00:46Z","timestamp":1772521246303,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"Supplement_2","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":30,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 18-50502"],"award-info":[{"award-number":["CCF 18-50502"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,30]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>While each cancer is the result of an isolated evolutionary process, there are repeated patterns in tumorigenesis defined by recurrent driver mutations and their temporal ordering. Such repeated evolutionary trajectories hold the potential to improve stratification of cancer patients into subtypes with distinct survival and therapy response profiles. However, current cancer phylogeny methods infer large solution spaces of plausible evolutionary histories from the same sequencing data, obfuscating repeated evolutionary patterns.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>To simultaneously resolve ambiguities in sequencing data and identify cancer subtypes, we propose to leverage common patterns of evolution found in patient cohorts. We first formulate the Multiple Choice Consensus Tree problem, which seeks to select a tumor tree for each patient and assign patients into clusters in such a way that maximizes consistency within each cluster of patient trees. We prove that this problem is NP-hard and develop a heuristic algorithm, Revealing Evolutionary Consensus Across Patients (RECAP), to solve this problem in practice. Finally, on simulated data, we show RECAP outperforms existing methods that do not account for patient subtypes. We then use RECAP to resolve ambiguities in patient trees and find repeated evolutionary trajectories in lung and breast cancer cohorts.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/elkebir-group\/RECAP.<\/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\/btaa801","type":"journal-article","created":{"date-parts":[[2020,9,7]],"date-time":"2020-09-07T19:14:50Z","timestamp":1599506090000},"page":"i684-i691","source":"Crossref","is-referenced-by-count":17,"title":["Detecting evolutionary patterns of cancers using consensus trees"],"prefix":"10.1093","volume":"36","author":[{"given":"Sarah","family":"Christensen","sequence":"first","affiliation":[{"name":"Department of Computer Science"}]},{"given":"Juho","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign , Urbana, IL 61801, USA"}]},{"given":"Nicholas","family":"Chia","sequence":"additional","affiliation":[{"name":"Microbiome Program, Center for Individualized Medicine"},{"name":"Division of Surgical Research, Department of Surgery, Mayo Clinic , Rochester, MN, 55905, USA"}]},{"given":"Oluwasanmi","family":"Koyejo","sequence":"additional","affiliation":[{"name":"Department of Computer Science"}]},{"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[{"name":"Department of Computer Science"}]}],"member":"286","published-online":{"date-parts":[[2020,12,29]]},"reference":[{"key":"2023062504244449600_btaa801-B1","doi-asserted-by":"crossref","first-page":"i408","DOI":"10.1093\/bioinformatics\/btz312","article-title":"Summarizing the solution space in tumor phylogeny inference by multiple consensus trees","volume":"35","author":"Aguse","year":"2019","journal-title":"Bioinformatics"},{"key":"2023062504244449600_btaa801-B2","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1038\/s41592-018-0108-x","article-title":"Detecting repeated cancer evolution from multi-region tumor sequencing data","volume":"15","author":"Caravagna","year":"2018","journal-title":"Nat. Methods"},{"key":"2023062504244449600_btaa801-B3","first-page":"226","author":"Christensen","year":"2020"},{"key":"2023062504244449600_btaa801-B4","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1038\/nature10983","article-title":"Dynamics of breast cancer relapse reveal late recurring ER-positive genomic subgroups","volume":"486","author":"Curtis","year":"2012","journal-title":"Nature"},{"key":"2023062504244449600_btaa801-B5","first-page":"2090","article-title":"Distance measures for tumor evolutionary trees","volume":"36","author":"DiNardo","year":"2019"},{"key":"2023062504244449600_btaa801-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":"2023062504244449600_btaa801-B7","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":"2023062504244449600_btaa801-B8","first-page":"63","author":"Govek","year":"2018"},{"key":"2023062504244449600_btaa801-B9","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0092-8674(00)81683-9","article-title":"The hallmarks of cancer","volume":"100","author":"Hanahan","year":"2000","journal-title":"Cell"},{"key":"2023062504244449600_btaa801-B10","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1016\/j.cell.2011.02.013","article-title":"Hallmarks of cancer: the next generation","volume":"144","author":"Hanahan","year":"2011","journal-title":"Cell"},{"key":"2023062504244449600_btaa801-B11","doi-asserted-by":"crossref","first-page":"2109","DOI":"10.1056\/NEJMoa1616288","article-title":"Tracking the evolution of non-small-cell lung cancer","volume":"376","author":"Jamal-Hanjani","year":"2017","journal-title":"N. Engl. J. Med"},{"key":"2023062504244449600_btaa801-B12","first-page":"85","volume-title":"Reducibility among Combinatorial Problems","author":"Karp","year":"1972"},{"key":"2023062504244449600_btaa801-B13","doi-asserted-by":"crossref","first-page":"1","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":"Algorithms Mol. Biol"},{"key":"2023062504244449600_btaa801-B14","doi-asserted-by":"crossref","first-page":"i379","DOI":"10.1093\/bioinformatics\/btz355","article-title":"Collaborative intra-tumor heterogeneity detection","volume":"35","author":"Khakabimamaghani","year":"2019","journal-title":"Bioinformatics"},{"key":"2023062504244449600_btaa801-B15","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":"2023062504244449600_btaa801-B16","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":"2023062504244449600_btaa801-B17","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":"2023062504244449600_btaa801-B18","volume-title":"Proceedings of Research in Computational Molecular Biology \u2013 Comparative Genomics.","author":"Pradhan","year":"2018"},{"key":"2023062504244449600_btaa801-B19","first-page":"742","article-title":"Neuer beweis eines satzes uber permutationen","volume":"27","author":"Pr\u00fcfer","year":"1918","journal-title":"Arch. Math. Phys"},{"key":"2023062504244449600_btaa801-B20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1186\/s13015-019-0155-6","article-title":"Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors","volume":"14","author":"Qi","year":"2019","journal-title":"Algorithms Mol. Biol"},{"key":"2023062504244449600_btaa801-B21","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.ccell.2018.08.008","article-title":"The genomic landscape of endocrine-resistant advanced breast cancers","volume":"34","author":"Razavi","year":"2018","journal-title":"Cancer Cell"},{"key":"2023062504244449600_btaa801-B22","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":"2023062504244449600_btaa801-B23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1038\/nrg.2016.170","article-title":"The evolution of tumour phylogenetics: principles and practice","volume":"18","author":"Schwartz","year":"2017","journal-title":"Nat. Rev. Genet"},{"key":"2023062504244449600_btaa801-B24","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.cell.2018.03.043","article-title":"Deterministic evolutionary trajectories influence primary tumor growth: TRACERx renal","volume":"173","author":"Turajlic","year":"2018","journal-title":"Cell"},{"key":"2023062504244449600_btaa801-B25","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1016\/j.cell.2018.03.057","article-title":"Tracking cancer evolution reveals constrained routes to metastases: TRACERx renal","volume":"173","author":"Turajlic","year":"2018","journal-title":"Cell, 0(0)"},{"key":"2023062504244449600_btaa801-B26","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.lungcan.2017.01.011","article-title":"Mutations in tp53, pik3ca, pten and other genes in egfr mutated lung cancers: correlation with clinical outcomes","volume":"106","author":"VanderLaan","year":"2017","journal-title":"Lung Cancer"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_2\/i684\/50693385\/btaa801.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_2\/i684\/50693385\/btaa801.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T04:25:59Z","timestamp":1687667159000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_2\/i684\/6055908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":26,"journal-issue":{"issue":"Supplement_2","published-print":{"date-parts":[[2020,12,30]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa801","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12]]},"published":{"date-parts":[[2020,12]]}}}