Genome halving and aliquoting under the copy number distance

Ron Zeira, Geoffrey Mon, Benjamin J. Raphael

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publication21st International Workshop on Algorithms in Bioinformatics, WABI 2021
EditorsAlessandra Carbone, Mohammed El-Kebir
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772006
StatePublished - Jul 1 2021
Event21st International Workshop on Algorithms in Bioinformatics, WABI 2021 - Virtual, Chicago, United States
Duration: Aug 2 2021Aug 4 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference21st International Workshop on Algorithms in Bioinformatics, WABI 2021
Country/TerritoryUnited States
CityVirtual, Chicago

All Science Journal Classification (ASJC) codes

  • Software


  • Copy number distance
  • Genome aliquoting distance
  • Genome halving distance
  • Genome rearrangements
  • Polyploidization
  • Whole genome duplication


Dive into the research topics of 'Genome halving and aliquoting under the copy number distance'. Together they form a unique fingerprint.

Cite this