{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T10:41:17Z","timestamp":1684320077701},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2018,5,3]],"date-time":"2018-05-03T00:00:00Z","timestamp":1525305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Bella Walter Memorial Fund of the Israel Cancer Association and by Len Blavatnik and the Blavatnik Family foundation"},{"name":"Edmond J. Safra Center for Bioinformatics at Tel-Aviv University"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,7,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Problems of genome rearrangement are central in both evolution and cancer research. Most genome rearrangement models assume that the genome contains a single copy of each gene and the only changes in the genome are structural, i.e. reordering of segments. In contrast, tumor genomes also undergo numerical changes such as deletions and duplications, and thus the number of copies of genes varies. Dealing with unequal gene content is a very challenging task, addressed by few algorithms to date. More realistic models are needed to help trace genome evolution during tumorigenesis.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Here, we present a model for the evolution of genomes with multiple gene copies using the operation types double-cut-and-joins, duplications and deletions. The events supported by the model are reversals, translocations, tandem duplications, segmental deletions and chromosomal amplifications and deletions, covering most types of structural and numerical changes observed in tumor samples. Our goal is to find a series of operations of minimum length that transform one karyotype into the other. We show that the problem is NP-hard and give an integer linear programming formulation that solves the problem exactly under some mild assumptions. We test our method on simulated genomes and on ovarian cancer genomes. Our study advances the state of the art in two ways: It allows a broader set of operations than extant models, thus being more realistic and it is the first study attempting to re-construct the full sequence of structural and numerical events during cancer evolution.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Code and data are available in https:\/\/github.com\/Shamir-Lab\/Sorting-Cancer-Karyotypes.<\/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\/bty381","type":"journal-article","created":{"date-parts":[[2018,5,2]],"date-time":"2018-05-02T11:10:47Z","timestamp":1525259447000},"page":"1489-1496","source":"Crossref","is-referenced-by-count":4,"title":["Sorting cancer karyotypes using double-cut-and-joins, duplications and deletions"],"prefix":"10.1093","volume":"37","author":[{"given":"Ron","family":"Zeira","sequence":"first","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv university , Tel Aviv 6997801, Israel"}]},{"given":"Ron","family":"Shamir","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv university , Tel Aviv 6997801, Israel"}]}],"member":"286","published-online":{"date-parts":[[2018,5,3]]},"reference":[{"key":"2023051709452467700_bty381-B1","doi-asserted-by":"crossref","first-page":"e19","DOI":"10.1093\/nar\/gku1211","article-title":"BreaKmer: detection of structural variation in targeted massively parallel sequencing data using kmers","volume":"43","author":"Abo","year":"2015","journal-title":"NAR"},{"key":"2023051709452467700_bty381-B2","doi-asserted-by":"crossref","first-page":"S27.","DOI":"10.1186\/1471-2105-11-S1-S27","article-title":"Genome rearrangements with duplications","volume":"11","author":"Bader","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B3","first-page":"272","volume-title":"SIAM J. Comput.","author":"Bafna","year":"1996"},{"key":"2023051709452467700_bty381-B4","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1038\/nature10166","article-title":"Integrated genomic analyses of ovarian carcinoma","volume":"474","author":"Bell","year":"2011","journal-title":"Nature"},{"key":"2023051709452467700_bty381-B5","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/11851561_16","volume-title":"Algorithms in Bioinformatics","author":"Bergeron","year":"2006"},{"key":"2023051709452467700_bty381-B6","first-page":"237","article-title":"Topology-free querying of protein interaction networks","volume":"17","author":"Bruckner","year":"2010","journal-title":"JCB"},{"key":"2023051709452467700_bty381-B7","doi-asserted-by":"crossref","first-page":"e1003740.","DOI":"10.1371\/journal.pcbi.1003740","article-title":"Algorithms to model single gene, single chromosome, and whole genome copy number changes jointly in tumor phylogenetics","volume":"10","author":"Chowdhury","year":"2014","journal-title":"PLoS Comp. Bio"},{"key":"2023051709452467700_bty381-B8","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1038\/ng.2762","article-title":"Emerging landscape of oncogenic signatures across human cancers","volume":"45","author":"Ciriello","year":"2013","journal-title":"Nat. Genet"},{"key":"2023051709452467700_bty381-B30","doi-asserted-by":"crossref","first-page":"S13.","DOI":"10.1186\/1471-2105-13-S19-S14","article-title":"Restricted DCJ-indel model: sorting linear genomes with DCJ and indels","volume":"13","author":"da Silva","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B9","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1038\/nrg3767","article-title":"Expanding the computational toolbox for mining cancer genomes","volume":"15","author":"Ding","year":"2014","journal-title":"Nat. Rev. Genet"},{"key":"2023051709452467700_bty381-B10","doi-asserted-by":"crossref","first-page":"488.","DOI":"10.1186\/s12859-017-1929-9","article-title":"Reconstructing cancer karyotypes from short read data: the half empty and half full glass","volume":"18","author":"Eitan","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B11","first-page":"1318","article-title":"SCJ: a breakpoint-like distance that simplifies several rearrangement problems","volume":"8","author":"Feij\u00e3o","year":"2011","journal-title":"TCBB"},{"key":"2023051709452467700_bty381-B12","doi-asserted-by":"crossref","first-page":"8","DOI":"10.3324\/haematol.2009.015974","article-title":"Current treatment of Philadelphia chromosome-positive acute lymphoblastic leukemia","volume":"95","author":"Fielding","year":"2010","journal-title":"Haematologica"},{"key":"2023051709452467700_bty381-B13","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1101\/gr.118414.110","article-title":"Estimation of rearrangement phylogeny for cancer genomes","volume":"22","author":"Greenman","year":"2012","journal-title":"Genome Res"},{"key":"2023051709452467700_bty381-B14","year":"2018"},{"key":"2023051709452467700_bty381-B16","first-page":"581","volume-title":"Proceedings of FOCS","author":"Hannenhalli","year":"1996"},{"key":"2023051709452467700_bty381-B151","first-page":"1","volume-title":"J. ACM","author":"Hannenhalli","year":"1999"},{"key":"2023051709452467700_bty381-B17","first-page":"85","volume-title":"Reducibility Among Combinatorial Problems","author":"Karp","year":"1972"},{"key":"2023051709452467700_bty381-B18","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1126\/science.1149504","article-title":"Paired-end mapping reveals extensive structural variation in the human genome","volume":"318","author":"Korbel","year":"2007","journal-title":"Science"},{"key":"2023051709452467700_bty381-B19","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1101\/gr.143677.112","article-title":"Breakpoint profiling of 64 cancer genomes reveals numerous complex rearrangements spawned by homology-independent mechanisms","volume":"23","author":"Malhotra","year":"2013","journal-title":"Genome Res"},{"key":"2023051709452467700_bty381-B20","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1002\/path.3980","article-title":"The role of tandem duplicator phenotype in tumour evolution in high-grade serous ovarian cancer","volume":"226","author":"Ng","year":"2012","journal-title":"J. Pathol"},{"key":"2023051709452467700_bty381-B21","doi-asserted-by":"crossref","first-page":"S10.","DOI":"10.1186\/1471-2105-13-S6-S10","article-title":"Reconstructing cancer genomes from paired-end sequencing data","volume":"13(Suppl. 6)","author":"Oesper","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B22","first-page":"1445","article-title":"Sorting cancer karyotypes by elementary operations","volume":"16","author":"Ozery-Flato","year":"2009","journal-title":"JCB"},{"key":"2023051709452467700_bty381-B23","doi-asserted-by":"crossref","first-page":"7672","DOI":"10.1073\/pnas.1330369100","article-title":"Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution","volume":"100","author":"Pevzner","year":"2003","journal-title":"PNAS"},{"key":"2023051709452467700_bty381-B24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","article-title":"The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two","volume":"8","author":"Ples\u0144ik","year":"1979","journal-title":"Inf. Process. Lett"},{"key":"2023051709452467700_bty381-B25","first-page":"p. 298","volume-title":"Proceedings of WABI","author":"Rahmann","year":"2006"},{"key":"2023051709452467700_bty381-B26","doi-asserted-by":"crossref","first-page":"ii162","DOI":"10.1093\/bioinformatics\/btg1074","article-title":"Reconstructing tumor genome architectures","volume":"19","author":"Raphael","year":"2003","journal-title":"Bioinformatics"},{"key":"2023051709452467700_bty381-B27","doi-asserted-by":"crossref","first-page":"e1003535.","DOI":"10.1371\/journal.pcbi.1003535","article-title":"Phylogenetic quantification of intra-tumour heterogeneity","volume":"10","author":"Schwarz","year":"2014","journal-title":"PLoS Comp. Bio"},{"key":"2023051709452467700_bty381-B28","doi-asserted-by":"crossref","first-page":"S13.","DOI":"10.1186\/1471-2105-13-S19-S13","article-title":"Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion","volume":"13","author":"Shao","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B29","doi-asserted-by":"crossref","first-page":"i329","DOI":"10.1093\/bioinformatics\/btv229","article-title":"Comparing genomes with rearrangements and segmental duplications","volume":"31","author":"Shao","year":"2015","journal-title":"Bioinformatics"},{"key":"2023051709452467700_bty381-B31","first-page":"425","article-title":"An exact algorithm to compute the double-cut-and-join jistance for jenomes with duplicate genes","volume":"22","author":"Shao","year":"2015","journal-title":"JCB"},{"key":"2023051709452467700_bty381-B32","doi-asserted-by":"crossref","first-page":"120.","DOI":"10.1186\/1471-2105-10-120","article-title":"Multichromosomal median and halving problems under different genomic distances","volume":"10","author":"Tannier","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023051709452467700_bty381-B33","doi-asserted-by":"crossref","first-page":"1546","DOI":"10.1126\/science.1235122","article-title":"Cancer genome landscapes","volume":"339","author":"Vogelstein","year":"2013","journal-title":"Science"},{"key":"2023051709452467700_bty381-B34","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"2023051709452467700_bty381-B35","doi-asserted-by":"crossref","first-page":"5546","DOI":"10.1073\/pnas.1220977110","article-title":"An algorithmic approach for breakage-fusion-bridge detection in tumor genomes","volume":"110","author":"Zakov","year":"2013","journal-title":"PNAS"},{"key":"2023051709452467700_bty381-B36","first-page":"127","article-title":"Sorting by cuts, joins, and whole chromosome duplications","volume":"24","author":"Zeira","year":"2017","journal-title":"JCB"},{"key":"2023051709452467700_bty381-B37","first-page":"1179","article-title":"A linear-time algorithm for the copy number transformation problem","volume":"24","author":"Zeira","year":"2017","journal-title":"JCB"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/11\/1489\/50361088\/bty381.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/11\/1489\/50361088\/bty381.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T10:27:15Z","timestamp":1684319235000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/11\/1489\/4992148"}},"subtitle":[],"editor":[{"given":"Oliver","family":"Stegle","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,5,3]]},"references-count":37,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7,12]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty381","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,6,1]]},"published":{"date-parts":[[2018,5,3]]}}}