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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\frac{3}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>3</mn> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation>. 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 2k, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\frac{3k}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>3</mn> <mi>k</mi> </mrow> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation>, 4k, 2k, and k, respectively, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$k=\frac{31}{21}+\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mfrac> <mn>31</mn> <mn>21</mn> </mfrac> <mo>+</mo> <mi>ϵ</mi> </mrow> </math></EquationSource> </InlineEquation>.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年3月7日

查看全文

Gabriel Siqueira,
Klairton Lima Brito,
Alexsandro Oliveira Alexandrino,
Andre Rodrigues Oliveira,
Ulisses Dias,
Zanoni Dias

摘要

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}$ $\frac{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 2k, $\frac{3k}{2}$ $\frac{3 k}{2}$ , 4k, 2k, and k, respectively, where $k=\frac{31}{21}+\epsilon $ $k = \frac{31}{21} + ϵ$ .