Abstract
Two genomes over the same set of gene families form a canonical pair when each of them has exactly one gene from each family. A genome is circular when it contains only circular chromosomes. Different distances of canonical circular genomes can be derived from a structure called breakpoint graph, which represents the relation between the two given genomes as a collection of cycles of even length. Then, the breakpoint distance is equal to nc_2, where n is the number of genes and c_2 is the number of cycles of length 2. Similarly, when the considered rearrangements are those modeled by the doublecutandjoin (DCJ) operation, the rearrangement distance is nc, where c is the total number of cycles.
The distance problem is a basic unit for several other combinatorial problems related to genome evolution and ancestral reconstruction, such as median or double distance. Interestingly, both median and double distance problems can be solved in polynomial time for the breakpoint distance, while they are NPhard for the rearrangement distance. One way of exploring the complexity space between these two extremes is to consider a σ_k distance, defined to be n(c_2+c_4+…+c_k), and increasingly investigate the complexities of median and double distance for the σ₄ distance, then the σ₆ distance, and so on. While for the median much effort was done in our and in other research groups but no progress was obtained even for the σ₄ distance, for solving the double distance under σ₄ and σ₆ distances we could devise linear time algorithms, which we present here.
BibTeX  Entry
@InProceedings{braga_et_al:LIPIcs.WABI.2022.13,
author = {Braga, Mar{\'\i}lia D. V. and Brockmann, Leonie R. and Klerx, Katharina and Stoye, Jens},
title = {{A Linear Time Algorithm for an Extended Version of the Breakpoint Double Distance}},
booktitle = {22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
pages = {13:113:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772433},
ISSN = {18688969},
year = {2022},
volume = {242},
editor = {Boucher, Christina and Rahmann, Sven},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17047},
URN = {urn:nbn:de:0030drops170472},
doi = {10.4230/LIPIcs.WABI.2022.13},
annote = {Keywords: Comparative genomics, genome rearrangement, breakpoint distance, doublecutandjoin (DCJ) distance, double distance}
}
Keywords: 

Comparative genomics, genome rearrangement, breakpoint distance, doublecutandjoin (DCJ) distance, double distance 
Collection: 

22nd International Workshop on Algorithms in Bioinformatics (WABI 2022) 
Issue Date: 

2022 
Date of publication: 

26.08.2022 