{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:41:59Z","timestamp":1753875719853,"version":"3.41.2"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:00:00Z","timestamp":1720569600000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Tumor trees, which depict the evolutionary process of cancer, provide a backbone for discovering recurring evolutionary processes in cancer. While they are not the primary information extracted from genomic data, they are valuable for this purpose. One such extraction method involves summarizing multiple trees into a single representative tree, such as consensus trees or supertrees.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We define the \u201cweighted centroid tree problem\u201d to find the centroid tree of a set of single-labeled rooted trees through the following steps: (i) mapping the given trees into the Euclidean space, (ii) computing the weighted centroid matrix of the mapped trees, and (iii) finding the nearest mapped tree (NMTP) to the centroid matrix. We show that this setup encompasses previously studied parent\u2013child and ancestor\u2013descendent metrics as well as the GraPhyC and TuELiP consensus tree algorithms. Moreover, we show that, while the NMTP problem is polynomial-time solvable for the adjacency embedding, it is NP-hard for ancestry and distance mappings. We introduce integer linear programs for NMTP in different setups where we also provide a new algorithm for the case of ancestry embedding called 2-AncL2, that uses a novel weighting scheme for ancestry signals. Our experimental results show that 2-AncL2 has a superior performance compared to available consensus tree algorithms. We also illustrate our setup\u2019s application on providing representative trees for a large real breast cancer dataset, deducing that the cluster centroid trees summarize reliable evolutionary information about the original dataset.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/vasei\/WAncILP.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btae120","type":"journal-article","created":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T12:00:46Z","timestamp":1720612846000},"source":"Crossref","is-referenced-by-count":0,"title":["Weighted centroid trees: a general approach to summarize phylogenies in single-labeled tumor mutation tree inference"],"prefix":"10.1093","volume":"40","author":[{"given":"Hamed","family":"Vasei","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Sharif University of Technology , Tehran 111559415,","place":["Iran"]}]},{"given":"Mohammad-Hadi","family":"Foroughmand-Araabi","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Sharif University of Technology , Tehran 111559415,","place":["Iran"]}]},{"given":"Amir","family":"Daneshgar","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Sharif University of Technology , Tehran 111559415,","place":["Iran"]}]}],"member":"286","published-online":{"date-parts":[[2024,7,10]]},"reference":[{"key":"2024102913473128400_btae120-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":"2024102913473128400_btae120-B2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0168-9525(88)90096-0","article-title":"The molecular biology of the notch locus and the fine tuning of differentiation in Drosophila","volume":"4","author":"Artavanis-Tsakonas","year":"1988","journal-title":"Trends Genet"},{"key":"2024102913473128400_btae120-B3","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1186\/s13045-020-00903-4","article-title":"XPO1-dependent nuclear export as a target for cancer therapy","volume":"13","author":"Azizian","year":"2020","journal-title":"J Hematol Oncol"},{"volume-title":"30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)","author":"Bernardini","key":"2024102913473128400_btae120-B4"},{"volume-title":"31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)","key":"2024102913473128400_btae120-B5"},{"key":"2024102913473128400_btae120-B6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1090\/dimacs\/061\/11","volume-title":"BioConsensus, DIMACS","author":"Bryant","year":"2003"},{"key":"2024102913473128400_btae120-B7","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":"2024102913473128400_btae120-B8","doi-asserted-by":"crossref","first-page":"I684","DOI":"10.1093\/bioinformatics\/btaa801","article-title":"Detecting evolutionary patterns of cancers using consensus trees","volume":"36","author":"Christensen","year":"2020","journal-title":"Bioinformatics"},{"key":"2024102913473128400_btae120-B9","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1093\/bioinformatics\/btaa676","article-title":"Triplet-based similarity score for fully multilabeled trees with poly-occurring labels","volume":"37","author":"Ciccolella","year":"2021","journal-title":"Bioinformatics"},{"key":"2024102913473128400_btae120-B10","doi-asserted-by":"crossref","first-page":"373","DOI":"10.18632\/oncotarget.28200","article-title":"NOTCH1 PEST domain variants are responsive to standard of care treatments despite distinct transformative properties in a breast cancer model","volume":"13","author":"Cravero","year":"2022","journal-title":"Oncotarget"},{"key":"2024102913473128400_btae120-B11","doi-asserted-by":"crossref","first-page":"2090","DOI":"10.1093\/bioinformatics\/btz869","article-title":"Distance measures for tumor evolutionary trees","volume":"36","author":"DiNardo","year":"2020","journal-title":"Bioinformatics"},{"key":"2024102913473128400_btae120-B12","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":"2024102913473128400_btae120-B13","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":"2024102913473128400_btae120-B14","first-page":"397","article-title":"Emerging topics in cancer evolution","volume":"27","author":"El-Kebir","year":"2022","journal-title":"Pac Symp Biocomput"},{"year":"2004","author":"Felsenstein","key":"2024102913473128400_btae120-B15"},{"first-page":"125","year":"2021","author":"Fu","key":"2024102913473128400_btae120-B16"},{"key":"2024102913473128400_btae120-B17","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1109\/TCBB.2020.3029689","article-title":"GraPhyC: using consensus to infer tumor evolution","volume":"19","author":"Govek","year":"2022","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"2024102913473128400_btae120-B18","doi-asserted-by":"crossref","first-page":"i204","DOI":"10.1093\/bioinformatics\/btad230","article-title":"A weighted distance-based approach for deriving consensus tumor evolutionary trees","volume":"39","author":"Guang","year":"2023","journal-title":"Bioinformatics"},{"key":"2024102913473128400_btae120-B19","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":"2024102913473128400_btae120-B20","first-page":"34","article-title":"TP53 mutations and SNPs as prognostic and predictive factors in patients with breast cancer","volume":"16","author":"Huszno","year":"2018","journal-title":"Oncol Lett"},{"key":"2024102913473128400_btae120-B21","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":"2024102913473128400_btae120-B22","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/s13015-021-00188-3","article-title":"The Bourque distances for mutation trees of cancers","volume":"16","author":"Jahn","year":"2021","journal-title":"Algorithms Mol Biol"},{"key":"2024102913473128400_btae120-B23","doi-asserted-by":"crossref","first-page":"1360","DOI":"10.3892\/ol.2020.11641","article-title":"ALOX12B promotes carcinogenesis in cervical cancer by regulating the PI3K\/ERK1 signaling pathway","volume":"20","author":"Jiang","year":"2020","journal-title":"Oncol Lett"},{"key":"2024102913473128400_btae120-B24","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":"2024102913473128400_btae120-B25","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":"2024102913473128400_btae120-B26","doi-asserted-by":"crossref","first-page":"S178","DOI":"10.1134\/S0006297922140140","article-title":"Targeting XPO1-dependent nuclear export in cancer","volume":"87","author":"Kim","year":"2022","journal-title":"Biochemistry (Mosc)"},{"key":"2024102913473128400_btae120-B27","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/1471-2105-15-27","article-title":"Using single cell sequencing data to model the evolutionary history of a tumor","volume":"15","author":"Kim","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2024102913473128400_btae120-B28","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/geno.2001.6519","article-title":"A gene cluster encoding human epidermis-type lipoxygenases at chromosome 17p13.1: cloning, physical mapping, and expression","volume":"73","author":"Krieg","year":"2001","journal-title":"Genomics"},{"key":"2024102913473128400_btae120-B29","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.bbcan.2017.02.001","article-title":"Advances in understanding tumour evolution through single-cell sequencing","volume":"1867","author":"Kuipers","year":"2017","journal-title":"Biochim Biophys Acta Rev Cancer"},{"key":"2024102913473128400_btae120-B30","doi-asserted-by":"crossref","first-page":"2139","DOI":"10.1007\/s00432-022-04247-z","article-title":"The efficacy of selinexor (KPT-330), an XPO1 inhibitor, on non-hematologic cancers: a comprehensive review","volume":"149","author":"Landes","year":"2023","journal-title":"J Cancer Res Clin Oncol"},{"key":"2024102913473128400_btae120-B31","doi-asserted-by":"crossref","first-page":"1528","DOI":"10.1093\/carcin\/bgp084","article-title":"Candidate gene approach evaluates association between innate immunity genes and breast cancer risk in Korean women","volume":"30","author":"Lee","year":"2009","journal-title":"Carcinogenesis"},{"key":"2024102913473128400_btae120-B32","doi-asserted-by":"crossref","first-page":"2223","DOI":"10.1182\/blood-2005-08-3329","article-title":"Recent insights into the role of notch signaling in tumorigenesis","volume":"107","author":"Leong","year":"2006","journal-title":"Blood"},{"year":"2020.","author":"Llabr\u00e9s","key":"2024102913473128400_btae120-B33"},{"key":"2024102913473128400_btae120-B34","doi-asserted-by":"crossref","first-page":"1181","DOI":"10.1089\/cmb.2021.0342","article-title":"The generalized Robinson-Foulds distance for phylogenetic trees","volume":"28","author":"Llabr\u00e9s","year":"2021","journal-title":"J Comput Biol"},{"key":"2024102913473128400_btae120-B35","doi-asserted-by":"crossref","first-page":"1931","DOI":"10.1084\/jem.20111855","article-title":"Oncogenic and tumor suppressor functions of notch in cancer: it\u2019s NOTCH what you think","volume":"208","author":"Lobry","year":"2011","journal-title":"J Exp Med"},{"key":"2024102913473128400_btae120-B36","first-page":"105","article-title":"Tumor heterogeneity: causes and consequences","volume":"1805","author":"Marusyk","year":"2010","journal-title":"Biochim Biophys Acta"},{"key":"2024102913473128400_btae120-B37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pcbi.1005509","article-title":"Clustering cancer evolutionary trees","volume":"13","author":"Matsui","year":"2017","journal-title":"PLoS Comput Biol"},{"key":"2024102913473128400_btae120-B38","doi-asserted-by":"crossref","first-page":"bpab006","DOI":"10.1093\/biomethods\/bpab006","article-title":"Novel metric for hyperbolic phylogenetic tree embeddings","volume":"6","author":"Matsumoto","year":"2021","journal-title":"Biol Methods Protoc"},{"year":"2018","author":"Monod","key":"2024102913473128400_btae120-B39"},{"key":"2024102913473128400_btae120-B40","doi-asserted-by":"crossref","first-page":"25533","DOI":"10.1038\/srep25533","article-title":"The impact of amplification on differential expression analyses by RNA-seq","volume":"6","author":"Parekh","year":"2016","journal-title":"Sci Rep"},{"key":"2024102913473128400_btae120-B41","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1177\/1947601913513950","article-title":"MAP3K1: genomic alterations in cancer and function in promoting cell survival or apoptosis","volume":"4","author":"Pham","year":"2013","journal-title":"Genes Cancer"},{"key":"2024102913473128400_btae120-B42","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1089\/cmb.2023.0262","article-title":"Consensus tree under the ancestor-descendant distance is NP-hard","volume":"31","author":"Qi","year":"2024","journal-title":"J Comput Biol"},{"key":"2024102913473128400_btae120-B43","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":"2024102913473128400_btae120-B44","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.cell.2014.12.033","article-title":"Molecular and genetic properties of tumors associated with local immune cytolytic activity","volume":"160","author":"Rooney","year":"2015","journal-title":"Cell"},{"key":"2024102913473128400_btae120-B45","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/em.20452","article-title":"Polymorphisms in innate immunity genes and lung cancer risk in Xuanwei, China","volume":"50","author":"Shen","year":"2009","journal-title":"Environ Mol Mutagen"},{"key":"2024102913473128400_btae120-B46","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1038\/s41592-020-01013-2","article-title":"A practical guide to cancer subclonal reconstruction from DNA sequencing","volume":"18","author":"Tarabichi","year":"2021","journal-title":"Nat Methods"},{"key":"2024102913473128400_btae120-B47","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1186\/s12885-022-10383-z","article-title":"Notch signaling pathway: a comprehensive prognostic and gene expression profile analysis in breast cancer","volume":"22","author":"Yousefi","year":"2022","journal-title":"BMC Cancer"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btae120\/58496650\/btae120.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/7\/btae120\/60176661\/btae120.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/40\/7\/btae120\/60176661\/btae120.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T13:48:19Z","timestamp":1730209699000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btae120\/7710428"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2024,7,1]]},"references-count":47,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btae120","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2024,7]]},"published":{"date-parts":[[2024,7,1]]},"article-number":"btae120"}}