Abstract
In the literature on genome rearrangement, several approaches use different structures to improve the results of genome rearrangement problems. In particular, graphs are structures widely used for the purpose of representing information retrieved from genomes. The breakpoint graph is a useful tool in this area because it allows representing in the same structure the gene orders of two genomes being compared. The maximum cycle decomposition of this graph brings immediate gain for deriving lower bounds for various genome rearrangement problems. This paper introduces a generalization of the Maximum Alternating Cycle Decomposition problem (MAX-ACD), called the Maximum Alternating Balanced Cycle Decomposition problem (MAX-ABCD). The MAX-ACD problem is closely related to the Sorting by Reversals problem and is a relevant topic of investigation in mathematics. The MAX-ABCD problem has applications in the Sorting by Intergenic Reversals problem, which is a problem that takes into account both the gene order and the information present in the intergenic regions. We present an algorithm with a constant approximation factor for the MAX-ABCD problem. Furthermore, we design an improved algorithm for the Sorting by Intergenic Operations of Reversal and Indel problem that guarantees an approximation factor of \(\frac{3}{2}\) considering a scenario where the orientation of the genes is known. For the scenario where the orientation of the genes is unknown and based on an algorithm for the MAX-ABCD problem, we develop approximation algorithms for the Sorting by Intergenic Reversals and Sorting by Intergenic Operations of Reversal and Indel problems with an approximation factor of 2k, where \(k=\frac{31}{21}+\epsilon \).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alexandrino, A.O., Brito, K.L., Oliveira, A.R., Dias, U., Dias, Z.: Reversal distance on genomes with different gene content and intergenic regions information. In: Martín-Vide, C., Vega-Rodríguez, M.A., Wheeler, T. (eds.) AlCoB 2021. LNCS, vol. 12715, pp. 121–133. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-74432-8_9
Alexandrino, A.O., Brito, K.L., Oliveira, A.R., Dias, U., Dias, Z.: Reversal and indel distance with intergenic region information. IEEE/ACM Transactions on Computational Biology and Bioinformatics, pp. 1–13 (2022)
Alexandrino, A.O., Oliveira, A.R., Dias, U., Dias, Z.: Incorporating intergenic regions into reversal and transposition distances with indels. J. Bioinform. Comput. Biol. 19(06), 2140011 (2021)
Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. SIAM J. Comput. 25(2), 272–289 (1996)
Berman, P., Fürer, M.: Approximating maximum independent set in bounded degree graphs. In: SODA’94: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 365–371. Society for Industrial and Applied Mathematics (1994)
Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-approximation algorithm for sorting by reversals. In: Möhring, R., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 200–210. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45749-6_21
Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_17
Biller, P., Knibbe, C., Beslon, G., Tannier, E.: Comparative genomics on artificial life. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds.) CiE 2016. LNCS, vol. 9709, pp. 35–44. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40189-8_4
Brito, K.L., Jean, G., Fertin, G., Oliveira, A.R., Dias, U., Dias, Z.: Sorting by genome rearrangements on both gene order and intergenic sizes. J. Comput. Biol. 27(2), 156–174 (2020)
Bulteau, L., Fertin, G., Komusiewicz, C.: (Prefix) Reversal distance for (signed) strings with few blocks or small alphabets. J. Discret. Algorithms 37, 44–55 (2016)
Caprara, A.: On the tightness of the alternating-cycle lower bound for sorting by reversals. J. Comb. Optim. 3(2), 149–182 (1999)
Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discret. Math. 12(1), 91–110 (1999)
Caprara, A., Rizzi, R.: Improved approximation for breakpoint graph decomposition and sorting by reversals. J. Comb. Optim. 6(2), 157–182 (2002)
Chen, X.: On sorting unsigned permutations by double-cut-and-joins. J. Comb. Optim. 25(3), 339–351 (2013)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)
Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46(1), 1–27 (1999)
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math. 2(1), 68–72 (1989)
Karp, R.M.: Reducibility among combinatorial problems. In: Jünger, M., et al. (eds.) 50 Years of Integer Programming 1958-2008, pp. 219–241. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-540-68279-0_8
Lin, G., Jiang, T.: A further improved approximation algorithm for breakpoint graph decomposition. J. Comb. Optim. 8(2), 183–194 (2004)
Oliveira, A.R., et al.: Sorting signed permutations by intergenic reversals. IEEE/ACM Trans. Comput. Biol. Bioinform. 18(6), 2870–2876 (2021)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425–440 (1991)
Pinheiro, P.O., Alexandrino, A.O., Oliveira, A.R., de Souza, C.C., Dias, Z.: Heuristics for breakpoint graph decomposition with applications in genome rearrangement problems. In: BSB 2020. LNCS, vol. 12558, pp. 129–140. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65775-8_12
Rahman, A., Shatabda, S., Hasan, M.: An approximation algorithm for sorting by reversals and transpositions. J. Discret. Algorithms 6(3), 449–457 (2008)
Swenson, K.M., Lin, Yu., Rajan, V., Moret, B.M.E.: Hurdles hardly have to be heeded. In: Nelson, C.E., Vialette, S. (eds.) RECOMB-CG 2008. LNCS, vol. 5267, pp. 241–251. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87989-3_18
Acknowledgments
This work was supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001 and the São Paulo Research Foundation, FAPESP (grants 2013/08293-7 and 2021/13824-8).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Brito, K.L., Alexandrino, A.O., Siqueira, G., Oliveira, A.R., Dias, U., Dias, Z. (2024). Maximum Alternating Balanced Cycle Decomposition and Applications in Sorting by Intergenic Operations Problems. In: Scornavacca, C., Hernández-Rosales, M. (eds) Comparative Genomics. RECOMB-CG 2024. Lecture Notes in Computer Science(), vol 14616. Springer, Cham. https://doi.org/10.1007/978-3-031-58072-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-58072-7_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-58071-0
Online ISBN: 978-3-031-58072-7
eBook Packages: Computer ScienceComputer Science (R0)