DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2022.21

A Maximum Parsimony Principle for Multichromosomal Complex Genome Rearrangements

Authors: Pijus Simonaitis and Benjamin J. Raphael

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)

Abstract

Motivation. Complex genome rearrangements, such as chromothripsis and chromoplexy, are common in cancer and have also been reported in individuals with various developmental and neurological disorders. These mutations are proposed to involve simultaneous breakage of the genome at many loci and rejoining of these breaks that produce highly rearranged genomes. Since genome sequencing measures only the novel adjacencies present at the time of sequencing, determining whether a collection of novel adjacencies resulted from a complex rearrangement is a complicated and ill-posed problem. Current heuristics for this problem often result in the inference of complex rearrangements that affect many chromosomes. Results. We introduce a model for complex rearrangements that builds upon the methods developed for analyzing simple genome rearrangements such as inversions and translocations. While nearly all of these existing methods use a maximum parsimony assumption of minimizing the number of rearrangements, we propose an alternative maximum parsimony principle based on minimizing the number of chromosomes involved in a rearrangement scenario. We show that our model leads to inference of more plausible sequences of rearrangements that better explain a complex congenital rearrangement in a human genome and chromothripsis events in 22 cancer genomes.

Cite as

Pijus Simonaitis and Benjamin J. Raphael. A Maximum Parsimony Principle for Multichromosomal Complex Genome Rearrangements. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{simonaitis_et_al:LIPIcs.WABI.2022.21,
  author =	{Simonaitis, Pijus and Raphael, Benjamin J.},
  title =	{{A Maximum Parsimony Principle for Multichromosomal Complex Genome Rearrangements}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.21},
  URN =		{urn:nbn:de:0030-drops-170552},
  doi =		{10.4230/LIPIcs.WABI.2022.21},
  annote =	{Keywords: Genome rearrangements, maximum parsimony, cancer evolution, chromothripsis, structural variation, affected chromosomes}
}

Document

DOI: 10.4230/LIPIcs.WABI.2021.18

Genome Halving and Aliquoting Under the Copy Number Distance

Authors: Ron Zeira, Geoffrey Mon, and Benjamin J. Raphael

Published in: LIPIcs, Volume 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)

Abstract

Large-scale genome rearrangements occur frequently in species evolution and cancer evolution. While the computation of evolutionary distances is tractable for balanced rearrangements, such as inversions and translocations, computing distances involving duplications and deletions is much more difficult. In the recently proposed Copy Number Distance (CND) model, a genome is represented as a Copy Number Profile (CNP), a sequence of integers, and the CND between two CNPs is the length of a shortest sequence of deletions and amplifications of contiguous segments that transforms one CNP into the other. In addition to these segmental events, genomes also undergo global events such as Whole Genome Duplication (WGD) or polyploidization that multiply the entire genome content. These global events are common and important in both species and cancer evolution. In this paper, we formulate the genome halving problem of finding a closest preduplication CNP that has undergone a WGD and evolved into a given CNP under the CND model. We also formulate the analogous genome aliquoting problem of finding the closest prepolyploidzation CNP under the CND distance. We give a linear time algorithm for the halving distance and a quadratic time dynamic programming algorithm for the aliquoting distance. We implement these algorithms and show that they produce reasonable solutions on simulated CNPs.

Cite as

Ron Zeira, Geoffrey Mon, and Benjamin J. Raphael. Genome Halving and Aliquoting Under the Copy Number Distance. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 18:1-18:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{zeira_et_al:LIPIcs.WABI.2021.18,
  author =	{Zeira, Ron and Mon, Geoffrey and Raphael, Benjamin J.},
  title =	{{Genome Halving and Aliquoting Under the Copy Number Distance}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{18:1--18:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2021.18},
  URN =		{urn:nbn:de:0030-drops-143711},
  doi =		{10.4230/LIPIcs.WABI.2021.18},
  annote =	{Keywords: Genome rearrangements, Copy number distance, Whole genome duplication, polyploidization, genome halving distance, genome aliquoting distance}
}

Search Results

Documents authored by Raphael, Benjamin J.

A Maximum Parsimony Principle for Multichromosomal Complex Genome Rearrangements

Abstract

Cite as

Genome Halving and Aliquoting Under the Copy Number Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message