---
_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: 2026-04-16T08:35:00Z
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
license: https://creativecommons.org/licenses/by/4.0/
month: '12'
oa: 1
oa_version: Published Version
publication: BMC Bioinformatics
publication_identifier:
  eissn:
  - 1471-2105
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 20
year: '2019'
...
---
OA_place: publisher
OA_type: gold
_id: '4351'
abstract:
- lang: eng
  text: 'BACKGROUND: Character mapping on phylogenies has played an important, if
    not critical role, in our understanding of molecular, morphological, and behavioral
    evolution. Until very recently we have relied on parsimony to infer character
    changes. Parsimony has a number of serious limitations that are drawbacks to our
    understanding. Recent statistical methods have been developed that free us from
    these limitations enabling us to overcome the problems of parsimony by accommodating
    uncertainty in evolutionary time, ancestral states, and the phylogeny. RESULTS:
    SIMMAP has been developed to implement stochastic character mapping that is useful
    to both molecular evolutionists, systematists, and bioinformaticians. Researchers
    can address questions about positive selection, patterns of amino acid substitution,
    character association, and patterns of morphological evolution. CONCLUSION: Stochastic
    character mapping, as implemented in the SIMMAP software, enables users to address
    questions that require mapping characters onto phylogenies using a probabilistic
    approach that does not rely on parsimony. Analyses can be performed using a fully
    Bayesian approach that is not reliant on considering a single topology, set of
    substitution model parameters, or reconstruction of ancestral states. Uncertainty
    in these quantities is accommodated by using MCMC samples from their respective
    posterior distributions.'
article_number: '88'
article_processing_charge: No
article_type: original
author:
- first_name: Jonathan P
  full_name: Bollback, Jonathan P
  id: 2C6FA9CC-F248-11E8-B48F-1D18A9856A87
  last_name: Bollback
  orcid: 0000-0002-4624-4612
citation:
  ama: 'Bollback JP. SIMMAP: stochastic character mapping of discrete traits on phylogenies.
    <i>BMC Bioinformatics</i>. 2006;7. doi:<a href="https://doi.org/10.1186/1471-2105-7-88">10.1186/1471-2105-7-88</a>'
  apa: 'Bollback, J. P. (2006). SIMMAP: stochastic character mapping of discrete traits
    on phylogenies. <i>BMC Bioinformatics</i>. BioMed Central. <a href="https://doi.org/10.1186/1471-2105-7-88">https://doi.org/10.1186/1471-2105-7-88</a>'
  chicago: 'Bollback, Jonathan P. “SIMMAP: Stochastic Character Mapping of Discrete
    Traits on Phylogenies.” <i>BMC Bioinformatics</i>. BioMed Central, 2006. <a href="https://doi.org/10.1186/1471-2105-7-88">https://doi.org/10.1186/1471-2105-7-88</a>.'
  ieee: 'J. P. Bollback, “SIMMAP: stochastic character mapping of discrete traits
    on phylogenies,” <i>BMC Bioinformatics</i>, vol. 7. BioMed Central, 2006.'
  ista: 'Bollback JP. 2006. SIMMAP: stochastic character mapping of discrete traits
    on phylogenies. BMC Bioinformatics. 7, 88.'
  mla: 'Bollback, Jonathan P. “SIMMAP: Stochastic Character Mapping of Discrete Traits
    on Phylogenies.” <i>BMC Bioinformatics</i>, vol. 7, 88, BioMed Central, 2006,
    doi:<a href="https://doi.org/10.1186/1471-2105-7-88">10.1186/1471-2105-7-88</a>.'
  short: J.P. Bollback, BMC Bioinformatics 7 (2006).
date_created: 2018-12-11T12:08:25Z
date_published: 2006-01-01T00:00:00Z
date_updated: 2026-08-21T11:57:14Z
day: '01'
doi: 10.1186/1471-2105-7-88
extern: '1'
external_id:
  pmid:
  - '16504105 '
intvolume: '         7'
language:
- iso: eng
month: '01'
oa_version: None
pmid: 1
publication: BMC Bioinformatics
publication_identifier:
  eissn:
  - 1471-2105
publication_status: published
publisher: BioMed Central
publist_id: '1109'
status: public
title: 'SIMMAP: stochastic character mapping of discrete traits on phylogenies'
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 7
year: '2006'
...