{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:10:54Z","timestamp":1772165454600,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"S20","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Many cancer genomes are extensively rearranged with highly aberrant chromosomal karyotypes. Structural and copy number variations in cancer genomes can be determined via abnormal mapping of sequenced reads to the reference genome. Recently it became possible to reconcile both of these types of large-scale variations into a karyotype graph representation of the rearranged cancer genomes. Such a representation, however, does not directly describe the linear and\/or circular structure of the underlying rearranged cancer chromosomes, thus limiting possible analysis of cancer genomes somatic evolutionary process as well as functional genomic changes brought by the large-scale genome rearrangements.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Here we address the aforementioned limitation by introducing a novel methodological framework for recovering rearranged cancer chromosomes from karyotype graphs. For a cancer karyotype graph we formulate an Eulerian Decomposition Problem (EDP) of finding a collection of linear and\/or circular rearranged cancer chromosomes that are determined by the graph. We derive and prove computational complexities for several variations of the EDP. We then demonstrate that Eulerian decomposition of the cancer karyotype graphs is not always unique and present the Consistent Contig Covering Problem (CCCP) of recovering unambiguous cancer contigs from the cancer karyotype graph, and describe a novel algorithm  capable of solving CCCP in polynomial time. We apply  on a prostate cancer dataset and demonstrate that it is capable of consistently recovering large cancer contigs even when underlying cancer genomes are highly rearranged.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>can recover rearranged cancer contigs from karyotype graphs thereby addressing existing limitation in inferring chromosomal structures of rearranged cancer genomes and advancing our understanding of both patient\/cancer-specific as well as the overall genetic instability in cancer.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-019-3208-4","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T20:02:24Z","timestamp":1576526544000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Recovering rearranged cancer chromosomes from karyotype graphs"],"prefix":"10.1186","volume":"20","author":[{"given":"Sergey","family":"Aganezov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Zban","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitaly","family":"Aksenov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikita","family":"Alexeev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael C.","family":"Schatz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"issue":"16","key":"3208_CR1","doi-asserted-by":"publisher","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N, Marth G, Abecasis G, Durbin R. The Sequence Alignment\/Map format and SAMtools. Bioinformatics. 2009; 25(16):2078\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/btp352.","journal-title":"Bioinformatics"},{"issue":"1","key":"3208_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1038\/nrg2626","volume":"11","author":"ML Metzker","year":"2010","unstructured":"Metzker ML. Sequencing technologies \u2014 the next generation. Nat Rev Genet. 2010; 11(1):31\u201346. https:\/\/doi.org\/10.1038\/nrg2626.","journal-title":"Nat Rev Genet"},{"issue":"17","key":"3208_CR3","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1093\/bioinformatics\/btp373","volume":"25","author":"DC Koboldt","year":"2009","unstructured":"Koboldt DC, Chen K, Wylie T, Larson DE, McLellan MD, Mardis ER, Weinstock GM, Wilson RK, Ding L. VarScan: variant detection in massively parallel sequencing of individual and pooled samples. Bioinformatics. 2009; 25(17):2283\u20135. https:\/\/doi.org\/10.1093\/bioinformatics\/btp373.","journal-title":"Bioinformatics"},{"issue":"24","key":"3208_CR4","doi-asserted-by":"publisher","first-page":"3458","DOI":"10.1093\/bioinformatics\/btu714","volume":"30","author":"A Ritz","year":"2014","unstructured":"Ritz A, Bashir A, Sindi S, Hsu D, Hajirasouliha I, Raphael BJ. Characterization of Structural variants with single molecule and hybrid sequencing approaches. Bioinformatics. 2014; 30(24):3458\u201366. https:\/\/doi.org\/10.1093\/bioinformatics\/btu714.","journal-title":"Bioinformatics"},{"issue":"6","key":"3208_CR5","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1186\/gb-2014-15-6-r84","volume":"15","author":"RM Layer","year":"2014","unstructured":"Layer RM, Chiang C, Quinlan AR, Hall IM. LUMPY: a probabilistic framework for structural variant discovery. Genome Biol. 2014; 15(6):84. https:\/\/doi.org\/10.1186\/gb-2014-15-6-r84.","journal-title":"Genome Biol"},{"issue":"4","key":"3208_CR6","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1101\/gr.221028.117","volume":"28","author":"JA Wala","year":"2018","unstructured":"Wala JA, Bandopadhayay P, Greenwald NF, O\u2019Rourke R, Sharpe T, Stewart C, Schumacher S, Li Y, Weischenfeldt J, Yao X, Nusbaum C, Campbell P, Getz G, Meyerson M, Zhang C. -Z, Imielinski M, Beroukhim R. SvABA: genome-wide detection of structural variants and indels by local assembly. Genome Res. 2018; 28(4):581\u201391. https:\/\/doi.org\/10.1101\/gr.221028.117.","journal-title":"Genome Res"},{"issue":"6","key":"3208_CR7","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1038\/s41592-018-0001-7","volume":"15","author":"FJ Sedlazeck","year":"2018","unstructured":"Sedlazeck FJ, Rescheneder P, Smolka M, Fang H, Nattestad M, von Haeseler A, Schatz MC. Accurate detection of complex structural variations using single-molecule sequencing. Nat Methods. 2018; 15(6):461\u20138. https:\/\/doi.org\/10.1038\/s41592-018-0001-7.","journal-title":"Nat Methods"},{"key":"3208_CR8","doi-asserted-by":"publisher","unstructured":"Nattestad M, Goodwin S, Ng K, Baslan T, Sedlazeck F, Resheneder P, Garvin T, Fang H, Gurtowski J, Hutton E, Tseng E, Chin J, Beck T, Sundaravadanam Y, Kramer M, Antoniou E, McPherson J, Hicks J, McCombie WR, Schatz MC. Complex rearrangements and oncogene amplifications revealed by long-read DNA and RNA sequencing of a highly rearranged cancer cell line. bioRxiv. 2017:1\u201312. https:\/\/doi.org\/10.1101\/174938.","DOI":"10.1101\/174938"},{"issue":"2","key":"3208_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1093\/bioinformatics\/btx712","volume":"34","author":"R Elyanow","year":"2018","unstructured":"Elyanow R, Wu H-T, Raphael BJ. Identifying structural variants using linked-read sequencing data. Bioinformatics. 2018; 34(2):353\u201360. https:\/\/doi.org\/10.1093\/bioinformatics\/btx712.","journal-title":"Bioinformatics"},{"issue":"11","key":"3208_CR10","doi-asserted-by":"publisher","first-page":"1881","DOI":"10.1101\/gr.180281.114","volume":"24","author":"G Ha","year":"2014","unstructured":"Ha G, Roth A, Khattra J, Ho J, Yap D, Prentice LM, Melnyk N, McPherson A, Bashashati A, Laks E, Biele J, Ding J, Le A, Rosner J, Shumansky K, Marra MA, Gilks CB, Huntsman DG, McAlpine JN, Aparicio S, Shah SP. TITAN: inference of copy number architectures in clonal cell populations from tumor whole-genome sequence data. Genome Res. 2014; 24(11):1881\u201393. https:\/\/doi.org\/10.1101\/gr.180281.114.","journal-title":"Genome Res"},{"issue":"1","key":"3208_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.mayocp.2018.06.028","volume":"94","author":"G Vasmatzis","year":"2019","unstructured":"Vasmatzis G, Kosari F, Murphy SJ, Terra S, Kovtun IV, Harris FR, Zarei S, Smadbeck JB, Johnson SH, Gaitatzes AG, Therneau TM, Rangel LJ, Knudson RA, Greipp P, Sukov WR, Knutson DL, Kloft-Nelson SM, Karnes RJ, Cheville JC. Large Chromosomal Rearrangements Yield Biomarkers to Distinguish Low-Risk From Intermediate- and High-Risk Prostate Cancer. Mayo Clin Proc. 2019; 94(1):27\u201336. https:\/\/doi.org\/10.1016\/j.mayocp.2018.06.028.","journal-title":"Mayo Clin Proc"},{"issue":"Supple 1","key":"3208_CR12","doi-asserted-by":"publisher","first-page":"34417","DOI":"10.4137\/BIC.S34417","volume":"8s1","author":"BS Paratala","year":"2016","unstructured":"Paratala BS, Dolfi SC, Khiabanian H, Rodriguez-Rodriguez L, Ganesan S, Hirshfield KM. Emerging Role of Genomic Rearrangements in Breast Cancer: Applying Knowledge from Other Cancers. Biomark Cancer. 2016; 8s1(Supple 1):34417. https:\/\/doi.org\/10.4137\/bic.s34417.","journal-title":"Biomark Cancer"},{"issue":"2","key":"3208_CR13","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1200\/JCO.2015.62.0138","volume":"34","author":"KL Johung","year":"2016","unstructured":"Johung KL, Yeh N, Desai NB, Williams TM, Lautenschlaeger T, Arvold ND, Ning MS, Attia A, Lovly CM, Goldberg S, Beal K, Yu JB, Kavanagh BD, Chiang VL, Camidge DR, Contessa JN. Extended survival and prognostic factors for patients with ALK-rearranged non-small-cell lung cancer and brain metastasis. J Clin Oncol. 2016; 34(2):123\u20139. https:\/\/doi.org\/10.1200\/JCO.2015.62.0138.","journal-title":"J Clin Oncol"},{"issue":"21","key":"3208_CR14","doi-asserted-by":"publisher","first-page":"1963","DOI":"10.1056\/NEJMoa1406766","volume":"371","author":"AT Shaw","year":"2014","unstructured":"Shaw AT, Ou S-HI, Bang Y-J, Camidge DR, Solomon BJ, Salgia R, Riely GJ, Varella-Garcia M, Shapiro GI, Costa DB, Doebele RC, Le LP, Zheng Z, Tan W, Stephenson P, Shreeve SM, Tye LM, Christensen JG, Wilner KD, Clark JW, Iafrate AJ. Crizotinib in ROS1 -Rearranged Non\u2013Small-Cell Lung Cancer. N Engl J Med. 2014; 371(21):1963\u201371. https:\/\/doi.org\/10.1056\/nejmoa1406766.","journal-title":"N Engl J Med"},{"issue":"1","key":"3208_CR15","doi-asserted-by":"publisher","first-page":"4821","DOI":"10.1038\/s41467-018-07341-4","volume":"9","author":"BS Paratala","year":"2018","unstructured":"Paratala BS, Chung JH, Williams CB, Yilmazel B, Petrosky W, Williams K, Schrock AB, Gay LM, Lee E, Dolfi SC, Pham K, Lin S, Yao M, Kulkarni A, DiClemente F, Liu C, Rodriguez-Rodriguez L, Ganesan S, Ross JS, Ali SM, Leyland-Jones B, Hirshfield KM. RET rearrangements are actionable alterations in breast cancer. Nat Commun. 2018; 9(1):4821. https:\/\/doi.org\/10.1038\/s41467-018-07341-4.","journal-title":"Nat Commun"},{"key":"3208_CR16","doi-asserted-by":"publisher","unstructured":"Zaccaria S, Raphael BJ. Accurate quantification of copy-number aberrations and whole-genome duplications in multi-sample tumor sequencing data. bioRxiv. 2018:496174. https:\/\/doi.org\/10.1101\/496174.","DOI":"10.1101\/496174"},{"issue":"7547","key":"3208_CR17","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1038\/nature14347","volume":"520","author":"Gunes Gundem","year":"2015","unstructured":"Gundem G, Van Loo P, Kremeyer B, Alexandrov LB, Tubio JMC, Papaemmanuil E, Brewer DS, Kallio HML, H\u00f6gn\u00e4s G, Annala M, Kivinummi K, Goody V, Latimer C, O\u2019Meara S, Dawson KJ, Isaacs W, Emmert-Buck MR, Nykter M, Foster C, Kote-Jarai Z, Easton D, Whitaker HC, Neal DE, Cooper CS, Eeles RA, Visakorpi T, Campbell PJ, McDermott U, Wedge DC, Bova GS, Bova GS. The evolutionary history of lethal metastatic prostate cancer. Nature. 2015; 520(7547):353\u20137. https:\/\/doi.org\/10.1038\/nature14347.","journal-title":"Nature"},{"key":"3208_CR18","doi-asserted-by":"publisher","unstructured":"Aganezov S, Raphael BJ. Reconstruction of clone- and haplotype-specific cancer genome karyotypes from bulk tumor samples. 560839. 2019. https:\/\/doi.org\/10.1101\/560839.","DOI":"10.1101\/560839"},{"issue":"Suppl 6","key":"3208_CR19","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/1471-2105-13-S6-S10","volume":"13 Suppl 6","author":"L Oesper","year":"2012","unstructured":"Oesper L, Ritz A, Aerni SJ, Drebin R, Raphael BJ. Reconstructing cancer genomes from paired-end sequencing data. BMC Bioinformatics. 2012; 13 Suppl 6(Suppl 6):10. https:\/\/doi.org\/10.1186\/1471-2105-13-S6-S10.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"3208_CR20","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1038\/s41467-018-08200-y","volume":"10","author":"V Deshpande","year":"2019","unstructured":"Deshpande V, Luebeck J, Nguyen NPD, Bakhtiari M, Turner KM, Schwab R, Carter H, Mischel PS, Bafna V. Exploring the landscape of focal amplifications in cancer using AmpliconArchitect. Nat Commun. 2019; 10(1):392. https:\/\/doi.org\/10.1038\/s41467-018-08200-y.","journal-title":"Nat Commun"},{"issue":"1","key":"3208_CR21","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1101\/gr.211201.116","volume":"27","author":"M Dzamba","year":"2017","unstructured":"Dzamba M, Ramani AK, Buczkowicz P, Jiang Y, Yu M, Hawkins C, Brudno M. Identification of complex genomic rearrangements in cancers using CouGaR. Genome Res. 2017; 27(1):107\u201317. https:\/\/doi.org\/10.1101\/gr.211201.116.","journal-title":"Genome Res"},{"issue":"1","key":"3208_CR22","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1186\/1471-2105-11-21","volume":"11","author":"C Kingsford","year":"2010","unstructured":"Kingsford C, Schatz MC, Pop M. Assembly complexity of prokaryotic genomes using short reads. BMC Bioinformatics. 2010; 11(1):21. https:\/\/doi.org\/10.1186\/1471-2105-11-21.","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"3208_CR23","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01188582","volume":"13","author":"PA Pevzner","year":"1995","unstructured":"Pevzner PA. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica. 1995; 13(1):77\u2013105. https:\/\/doi.org\/10.1007\/BF01188582.","journal-title":"Algorithmica"},{"issue":"4","key":"3208_CR24","doi-asserted-by":"publisher","first-page":"1525","DOI":"10.1128\/MCB.8.4.1525","volume":"8","author":"SM Carroll","year":"1988","unstructured":"Carroll SM, DeRose ML, Gaudray P, Moore CM, Needham-Vandevanter DR, Von Hoff DD, Wahl GM. Double minute chromosomes can be produced from precursors derived from a chromosomal deletion. Mol Cell Biol. 1988; 8(4):1525\u201333.","journal-title":"Mol Cell Biol"},{"issue":"1","key":"3208_CR25","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s13353-010-0007-z","volume":"52","author":"Y Fan","year":"2011","unstructured":"Fan Y, Mao R, Lv H, Xu J, Yan L, Liu Y, Shi M, Ji G, Yu Y, Bai J, Jin Y, Fu S. Frequency of double minute chromosomes and combined cytogenetic abnormalities and their characteristics. J Appl Genet. 2011; 52(1):53\u20139. https:\/\/doi.org\/10.1007\/s13353-010-0007-z.","journal-title":"J Appl Genet"},{"issue":"7643","key":"3208_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1038\/nature21356","volume":"543","author":"KM Turner","year":"2017","unstructured":"Turner KM, Deshpande V, Beyter D, Koga T, Rusert J, Lee C, Li B, Arden K, Ren B, Nathanson DA, Kornblum HI, Taylor MD, Kaushal S, Cavenee WK, Wechsler-Reya R, Furnari FB, Vandenberg SR, Rao PN, Wahl GM, Bafna V, Mischel PS. Extrachromosomal oncogene amplification drives tumour evolution and genetic heterogeneity. Nature. 2017; 543(7643):122\u20135. https:\/\/doi.org\/10.1038\/nature21356.","journal-title":"Nature"},{"issue":"4","key":"3208_CR27","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I. The NP-Completeness of Some Edge-Partition Problems. SIAM J Comput. 1981; 10(4):713\u20137. https:\/\/doi.org\/10.1137\/0210054.","journal-title":"SIAM J Comput"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3208-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-019-3208-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-019-3208-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,15]],"date-time":"2020-12-15T19:15:07Z","timestamp":1608059707000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-019-3208-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":27,"journal-issue":{"issue":"S20","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["3208"],"URL":"https:\/\/doi.org\/10.1186\/s12859-019-3208-4","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/831057","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"17 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"641"}}