PUB - Publikationen an der Universität Bielefeld

The Double Cut and Join (DCJ) model is a simple and powerful model for the analysis of large structural rearrangements. After being extended to the DCJ-indel model, capable of handling gains and losses of genetic material, research has shifted in recent years toward enabling it to handle natural genomes, for which no assumption about the distribution of markers has to be made. Whole Genome Duplications (WGD) are events that double the content and structure of a genome. In some organisms, multiple WGD events have been observed while loss of genetic material is a typical occurrence following a WGD event. Natural genomes are therefore the ideal framework, under which to study this event. The traditional theoretical framework for studying WGD events is the Genome Halving Problem (GHP). While the GHP is solved for the DCJ model for genomes without losses, there are currently no exact algorithms utilizing the DCJ-indel model. In this work, we make the first step towards halving natural genomes and present a simple and general view on the DCJ-indel model that we apply to derive an exact polynomial time and space solution for the GHP on genomes with at most two genes per family. Supplementary material including a generalization to natural genomes can be found at https://doi.org/10.6084/m9.figshare.22269697.