Maximum alternating clean balanced cycle decomposition and applications in rearrangement distance problems

What the paper says

In genome rearrangement, graph-based representations are widely used to analyze and solve rearrangement problems. In particular, when each gene occurs at most once, the breakpoint graph is a useful tool. A maximum cycle decomposition of this graph yields immediate lower bounds for several genome rearrangement distances. This paper introduces a generalization of the Maximum Alternating Cycle Decomposition problem ( MAX-ACD ), called the Maximum Alternating Clean Balanced Cycle Decomposition problem ( MAX-ACBCD ). The MAX-ACD problem is closely related to some rearrangement problems, where the orientation of the genes is unknown, and all genes are common to both genomes. The MAX-ACBCD problem has applications to related rearrangement problems, which allow genes present in only one of the genomes and consider both gene order and intergenic-region information. We present a constant-factor approximation and a heuristic for the MAX-ACBCD problem, and we performed tests with the heuristic applied to artificially generated genomes. Considering intergenic regions and a scenario where the orientation of the genes is known, we design an improved algorithm for the Sorting by Reversals and Intergenic Indels problem that guarantees an approximation factor of $$\frac{3}{2}$$ 3 2 . For the scenario where the orientation of the genes is unknown, and using the MAX-ACBCD problem, we develop approximation algorithms for the Sorting by Reversals, the Sorting by Reversals and Intergenic Indels, the Reversal, Transposition and Indel Distance, the Sorting by DCJ, and the Sorting by DCJ and Intergenic Indels problems with approximation factors of 2 k , $$\frac{3k}{2}$$ 3 k 2 , 4 k , 2 k , and k , respectively, where $$k=\frac{31}{21}+\epsilon $$ k = 31 21 + ϵ .