---
_id: '7214'
abstract:
- lang: eng
  text: "Background: 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.\r\n\r\nResults:
    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 CCR capable of solving
    CCCP in polynomial time. We apply CCR 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.\r\n\r\nConclusions: CCR 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."
article_number: '641'
article_processing_charge: No
article_type: original
author:
- first_name: Sergey
  full_name: Aganezov, Sergey
  last_name: Aganezov
- first_name: Ilya
  full_name: Zban, Ilya
  last_name: Zban
- first_name: Vitalii
  full_name: Aksenov, Vitalii
  id: 2980135A-F248-11E8-B48F-1D18A9856A87
  last_name: Aksenov
- first_name: Nikita
  full_name: Alexeev, Nikita
  last_name: Alexeev
- first_name: Michael C.
  full_name: Schatz, Michael C.
  last_name: Schatz
citation:
  ama: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. Recovering rearranged
    cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>. 2019;20.
    doi:<a href="https://doi.org/10.1186/s12859-019-3208-4">10.1186/s12859-019-3208-4</a>
  apa: Aganezov, S., Zban, I., Aksenov, V., Alexeev, N., &#38; Schatz, M. C. (2019).
    Recovering rearranged cancer chromosomes from karyotype graphs. <i>BMC Bioinformatics</i>.
    BMC. <a href="https://doi.org/10.1186/s12859-019-3208-4">https://doi.org/10.1186/s12859-019-3208-4</a>
  chicago: Aganezov, Sergey, Ilya Zban, Vitalii Aksenov, Nikita Alexeev, and Michael
    C. Schatz. “Recovering Rearranged Cancer Chromosomes from Karyotype Graphs.” <i>BMC
    Bioinformatics</i>. BMC, 2019. <a href="https://doi.org/10.1186/s12859-019-3208-4">https://doi.org/10.1186/s12859-019-3208-4</a>.
  ieee: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, and M. C. Schatz, “Recovering
    rearranged cancer chromosomes from karyotype graphs,” <i>BMC Bioinformatics</i>,
    vol. 20. BMC, 2019.
  ista: Aganezov S, Zban I, Aksenov V, Alexeev N, Schatz MC. 2019. Recovering rearranged
    cancer chromosomes from karyotype graphs. BMC Bioinformatics. 20, 641.
  mla: Aganezov, Sergey, et al. “Recovering Rearranged Cancer Chromosomes from Karyotype
    Graphs.” <i>BMC Bioinformatics</i>, vol. 20, 641, BMC, 2019, doi:<a href="https://doi.org/10.1186/s12859-019-3208-4">10.1186/s12859-019-3208-4</a>.
  short: S. Aganezov, I. Zban, V. Aksenov, N. Alexeev, M.C. Schatz, BMC Bioinformatics
    20 (2019).
date_created: 2019-12-29T23:00:46Z
date_published: 2019-12-17T00:00:00Z
date_updated: 2023-09-06T14:51:06Z
day: '17'
ddc:
- '570'
department:
- _id: DaAl
doi: 10.1186/s12859-019-3208-4
external_id:
  isi:
  - '000511618800007'
file:
- access_level: open_access
  checksum: 7a30357efdcf8f66587ed495c0927724
  content_type: application/pdf
  creator: dernst
  date_created: 2020-01-02T16:10:58Z
  date_updated: 2020-07-14T12:47:54Z
  file_id: '7221'
  file_name: 2019_BMCBioinfo_Aganezov.pdf
  file_size: 1917374
  relation: main_file
file_date_updated: 2020-07-14T12:47:54Z
has_accepted_license: '1'
intvolume: '        20'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: BMC Bioinformatics
publication_identifier:
  eissn:
  - '14712105'
publication_status: published
publisher: BMC
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recovering rearranged cancer chromosomes from karyotype graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 20
year: '2019'
...