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].
- A linear time algorithm for an extended version of the breakpoint double distance
- HP Distance Via Double Cut and Join Distance
- A linear time approximation algorithm for the DCJ distance for genomes with bounded number of duplicates
- A new linear time algorithm to compute the genomic distance via the double cut and join distance
- Computing the rearrangement distance of natural genomes
This page was built for publication: On the class of double distance problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086496)
