{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T07:11:02Z","timestamp":1765609862175,"version":"3.37.3"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T00:00:00Z","timestamp":1533686400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"publisher","award":["I0-0035","P1-0285","N1-0032","N1-0038","N1-0062","J1-7051","J1-9110"],"award-info":[{"award-number":["I0-0035","P1-0285","N1-0032","N1-0038","N1-0062","J1-7051","J1-9110"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["274977"],"award-info":[{"award-number":["274977"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Foundations of Computational Health program"},{"name":"Helsinki Institute for Information Technology HIIT"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Discovering the evolution of a tumor may help identify driver mutations and provide a more comprehensive view on the history of the tumor. Recent studies have tackled this problem using multiple samples sequenced from a tumor, and due to clinical implications, this has attracted great interest. However, such samples usually mix several distinct tumor subclones, which confounds the discovery of the tumor phylogeny.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We study a natural problem formulation requiring to decompose the tumor samples into several subclones with the objective of forming a minimum perfect phylogeny. We propose an Integer Linear Programming formulation for it, and implement it into a method called MIPUP. We tested the ability of MIPUP and of four popular tools LICHeE, AncesTree, CITUP, Treeomics to reconstruct the tumor phylogeny. On simulated data, MIPUP shows up to a 34% improvement under the ancestor-descendant relations metric. On four real datasets, MIPUP\u2019s reconstructions proved to be generally more faithful than those of LICHeE.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>MIPUP is available at https:\/\/github.com\/zhero9\/MIPUP as open source.<\/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\/bty683","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T11:12:15Z","timestamp":1533640335000},"page":"769-777","source":"Crossref","is-referenced-by-count":15,"title":["MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP"],"prefix":"10.1093","volume":"35","author":[{"given":"Edin","family":"Husi\u0107","sequence":"first","affiliation":[{"name":"Department of Mathematics, London School of Economics and Political Science, London, UK"}]},{"given":"Xinyue","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Finland"}]},{"given":"Ademir","family":"Hujdurovi\u0107","sequence":"additional","affiliation":[{"name":"University of Primorska, UP IAM, Koper, Slovenia"},{"name":"University of Primorska, UP FAMNIT, Koper, Slovenia"}]},{"given":"Miika","family":"Mehine","sequence":"additional","affiliation":[{"name":"Genome-Scale Biology Research Program, Research Programs Unit, Department of Medical and Clinical Genetics, Faculty of Medicine, University of Helsinki, Medicum, Helsinki, Finland"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Verona, Verona, Italy"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Finland"}]},{"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[{"name":"University of Primorska, UP IAM, Koper, Slovenia"},{"name":"University of Primorska, UP FAMNIT, Koper, Slovenia"}]},{"given":"Alexandru I","family":"Tomescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology HIIT, University of Helsinki, Finland"}]}],"member":"286","published-online":{"date-parts":[[2018,8,8]]},"reference":[{"key":"2023013107253351000_bty683-B1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/path.4230","article-title":"Distinct evolutionary trajectories of primary high-grade serous ovarian cancers revealed through spatial mutational profiling","volume":"231","author":"Bashashati","year":"2013","journal-title":"J. Pathol"},{"key":"2023013107253351000_bty683-B2","doi-asserted-by":"crossref","first-page":"13081","DOI":"10.1073\/pnas.0801523105","article-title":"Subclonal phylogenetic structures in cancer revealed by ultra-deep sequencing","volume":"105","author":"Campbell","year":"2008","journal-title":"Proc. Natl. Acad. Sci"},{"key":"2023013107253351000_bty683-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":"2023013107253351000_bty683-B4","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1038\/nature13952","article-title":"Dynamics of genomic clones in breast cancer patient xenografts at single-cell resolution","volume":"518","author":"Eirew","year":"2015","journal-title":"Nature"},{"key":"2023013107253351000_bty683-B5","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":"2023013107253351000_bty683-B6","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":"2023013107253351000_bty683-B7","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":"2023013107253351000_bty683-B8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1038\/ng.2891","article-title":"Genomic architecture and evolution of clear cell renal cell carcinomas defined by multiregion sequencing","volume":"46","author":"Gerlinger","year":"2014","journal-title":"Nat. Genet"},{"key":"2023013107253351000_bty683-B9","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":"2023013107253351000_bty683-B10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023013107253351000_bty683-B11","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":"2023013107253351000_bty683-B12","first-page":"354","volume-title":"Algorithms in Bioinformatics - 14th International Workshop, WABI 2014, Volume 8701 of LNCS","author":"Hajirasouliha","year":"2014"},{"key":"2023013107253351000_bty683-B13","first-page":"80","volume-title":"Algorithms in Bioinformatics - 15th International Workshop, WABI 2015, Volume 9289 of LNCS","author":"Hujdurovi\u0107","year":"2015"},{"key":"2023013107253351000_bty683-B14","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1109\/TCBB.2016.2606620","article-title":"Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples","volume":"15","author":"Hujdurovi\u0107","year":"2016","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"2023013107253351000_bty683-B15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3182178","article-title":"Perfect phylogenies via branchings in acyclic digraphs and a generalization of dilworth\u2019s theorem","volume":"14","author":"Hujdurovi\u0107","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"2023013107253351000_bty683-B16","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"},{"key":"2023013107253351000_bty683-B17","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":"2023013107253351000_bty683-B18","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1101\/gr.129684.111","article-title":"VarScan 2: somatic mutation and copy number alteration discovery in cancer by exome sequencing","volume":"22","author":"Koboldt","year":"2012","journal-title":"Genome Res"},{"key":"2023013107253351000_bty683-B19","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":"2023013107253351000_bty683-B20","doi-asserted-by":"crossref","first-page":"4407.","DOI":"10.1093\/hmg\/ddv177","article-title":"Clonally related uterine leiomyomas are common and display branched tumor evolution","volume":"24","author":"Mehine","year":"2015","journal-title":"Hum. Mol. Genet"},{"key":"2023013107253351000_bty683-B21","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1101\/gr.151670.112","article-title":"Genome evolution during progression to breast cancer","volume":"23","author":"Newburger","year":"2013","journal-title":"Genome Research"},{"key":"2023013107253351000_bty683-B22","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":"2023013107253351000_bty683-B23","doi-asserted-by":"crossref","first-page":"1","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":"2023013107253351000_bty683-B24","first-page":"742","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","author":"Pr\u00fcfer","year":"1918","journal-title":"Arch. Math. Phys"},{"key":"2023013107253351000_bty683-B25","doi-asserted-by":"crossref","first-page":"14114","DOI":"10.1038\/ncomms14114","article-title":"Reconstructing metastatic seeding patterns of human cancers","volume":"8","author":"Reiter","year":"2017","journal-title":"Nat. Commun"},{"key":"2023013107253351000_bty683-B26","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1089\/cmb.2013.0106","article-title":"Inference of tumor phylogenies with improved somatic mutation discovery","volume":"20","author":"Salari","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023013107253351000_bty683-B27","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":"2023013107253351000_bty683-B28","doi-asserted-by":"crossref","first-page":"42.","DOI":"10.1186\/1471-2105-11-42","article-title":"Applying unmixing to gene expression data for tumor phylogeny inference","volume":"11","author":"Schwartz","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023013107253351000_bty683-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":"2023013107253351000_bty683-B30","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1093\/bioinformatics\/btu755","article-title":"SNV-PPILP: refined SNV calling for tumor data using perfect phylogenies and ILP","volume":"31","author":"van Rens","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/5\/769\/48966010\/bioinformatics_35_5_769.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/5\/769\/48966010\/bioinformatics_35_5_769.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T10:21:01Z","timestamp":1675160461000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/5\/769\/5068162"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,8,8]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty683","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2019,3,1]]},"published":{"date-parts":[[2018,8,8]]}}}