Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information

• Gabriel Siqueira Universidade Estadual de Campinas (UNICAMP) https://orcid.org/0000-0001-5745-399X
• Alexsandro Oliveira Alexandrino Universidade Estadual de Campinas (UNICAMP) https://orcid.org/0000-0002-6320-9747
• Zanoni Dias Universidade Estadual de Campinas (UNICAMP) https://orcid.org/0000-0003-3333-6822

DOI: https://doi.org/10.5753/bsb.2025.14145

Resumo

Genome rearrangement distances are an established method in genome comparison. Works in this area may include various rearrangement operations representing large-scale mutations, gene orientation information, the number of nucleotides in intergenic regions, and weights reflecting the expected frequency of each operation. In this article, we model genomes containing at most one copy of each gene by considering gene sequences, with orientations, and representing intergenic regions according to their nucleotide lengths. We looked at a problem called Weighted Reversal, Transposition, and Indel Distance, which seeks the minimal cost sequence composed by the rearrangement operations of reversals, transposition, and indels, capable of transforming one genome into another. We leverage a structure called Labeled Intergenic Breakpoint Graph to show an algorithm for that problem with guaranteed approximations considering some sets of weights for the operations.

Palavras-chave: Genome Rearrangement, Reversal, Transposition, Indel

Referências

Alexandrino, A. O., Brito, K. L., Oliveira, A. R., Dias, U., and Dias, Z. (2021). Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information. In Proceedings of the 8th International Conference on Algorithms for Computational Biology (AlCoB’2021), volume 12715, pages 121–133. Springer International Publishing.

Alexandrino, A. O., Brito, K. L., Oliveira, A. R., Dias, U., and Dias, Z. (2023a). Reversal and indel distance with intergenic region information. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 20(3):1628–1640.

Alexandrino, A. O., Oliveira, A. R., Dias, U., and Dias, Z. (2022). Labeled Cycle Graph for Transposition and Indel Distance. Journal of Computational Biology, 29(03):243–256.

Alexandrino, A. O., Oliveira, A. R., Jean, G., Fertin, G., Dias, U., and Dias, Z. (2023b). Reversal and transposition distance on unbalanced genomes using intergenic information. Journal of Computational Biology, 30(8):861–876.

Alexandrino, A. O., Siqueira, G., Brito, K. L., Oliveira, A. R., Dias, U., and Dias, Z. (2023c). Block interchange and reversal distance on unbalanced genomes. In Advances in Bioinformatics and Computational Biology, pages 1–13, Cham. Springer Nature Switzerland.

Bafna, V. and Pevzner, P. A. (1996). Genome Rearrangements and Sorting by Reversals. SIAM Journal on Computing, 25(2):272–289.

Bafna, V. and Pevzner, P. A. (1998). Sorting by Transpositions. SIAM Journal on Discrete Mathematics, 11(2):224–240.

Blanchette, M., Kunisawa, T., and Sankoff, D. (1996). Parametric Genome Rearrangement. Gene, 172(1):GC11–GC17.

Brito, K. L., Jean, G., Fertin, G., Oliveira, A. R., Dias, U., and Dias, Z. (2020). Sorting by Genome Rearrangements on both Gene Order and Intergenic Sizes. Journal of Computational Biology, 27(2):156–174.

Hannenhalli, S. and Pevzner, P. A. (1999). Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals. Journal of the ACM, 46(1):1–27.

Oliveira, A. R., Brito, K. L., Dias, U., and Dias, Z. (2019a). On the Complexity of Sorting by Reversals and Transpositions Problems. Journal of Computational Biology, 26:1223–1229.

Oliveira, A. R., Brito, K. L., Dias, Z., and Dias, U. (2019b). Sorting by Weighted Reversals and Transpositions. Journal of Computational Biology, 26:420–431.

Oliveira, A. R., Jean, G., Fertin, G., Brito, K. L., Bulteau, L., Dias, U., and Dias, Z. (2021a). Sorting Signed Permutations by Intergenic Reversals. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 18(6):2870–2876.

Oliveira, A. R., Jean, G., Fertin, G., Brito, K. L., Dias, U., and Dias, Z. (2021b). Sorting Permutations by Intergenic Operations. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 18(6):2080–2093.

Walter, M. E. M. T., Dias, Z., and Meidanis, J. (1998). Reversal and Transposition Distance of Linear Chromosomes. In Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE’1998), pages 96–102, Los Alamitos, CA, USA. IEEE Computer Society.

Willing, E., Stoye, J., and Braga, M. (2021). Computing the Inversion-Indel Distance. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 18(6):2314–2326.