On the class of double distance problems (Q6086496)

The paper focuses on the comparison of genomes (with singular occurrences i.e. every gene family has exactly one component vs duplicated i.e. every gene family has exactly two members) by addressing the minimisation of breakpoints problem, using the double distance approach (NP hard problem). Building up from previous work that proposed linear solutions for particular cases (circular chromosomes), the authors generalise their approaches on linear chromosomes. Following a description of the breakpoint graph and breakpoint distance (including the class of \(\sigma_k\) distances), the authors focus on the equivalence of \(\sigma_k\) double distance and the \(\sigma_k\) disambiguation, proposing a linear time, greedy approach for particular values of \(k\). the paper concludes with a discussion of the approach in the context of cycle bubbles. For the entire collection see [Zbl 1525.92003].