On Variants of the Genome Rearrangement Distance Problem

• Alexsandro Oliveira Alexandrino Unicamp
• Ulisses Dias Unicamp
• Zanoni Dias Unicamp

DOI: https://doi.org/10.5753/ctd.2025.7128

Abstract

In comparative genomics, evolutionary distance can be estimated by determining a minimum sequence of genome rearrangements required to transform one genome into another. The length of this sequence is called the rearrangement distance. Traditionally, most studies assumed that compared genomes shared the same set of genes, with only their relative gene order being used for comparison. Recent studies indicate that incorporating intergenic region sizes leads to more accurate distance estimates when analyzing real genomes. Furthermore, they started to consider genomes having a distinct set of genes. In this work, we investigate genome rearrangement problems by incorporating additional information and complexity into the models, in order to achieve more realistic practical results that can benefit several scientific fields.

References

Bafna, V. and Pevzner, P. A. (1995). Sorting Permutations by Transpositions. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’ 1995), pages 614–623, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics.

Biller, P., Guéguen, L., Knibbe, C., and Tannier, E. (2016a). Breaking Good: Accounting for Fragility of Genomic Regions in Rearrangement Distance Estimation. Genome Biology and Evolution, 8(5):1427–1439.

Biller, P., Knibbe, C., Beslon, G., and Tannier, E. (2016b). Comparative Genomics on Artificial Life. In Pursuit of the Universal, pages 35–44. Springer International Publishing.

Bochkareva, O. O., Moroz, E. V., Davydov, I. I., and Gelfand, M. S. (2018). Genome Rearrangements and Selection in Multi-chromosome Bacteria Burkholderia spp. BMC genomics, 19(1):1–17.

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.

Brito, K. L., Oliveira, A. R., Alexandrino, A. O., Dias, U., and Dias, Z. (2021). An Improved Approximation Algorithm for the Reversal and Transposition Distance Considering Gene Order and Intergenic Sizes. Algorithms for Molecular Biology, 16(1):1–21.

Bulteau, L., Fertin, G., and Rusu, I. (2012). Sorting by Transpositions is Difficult. SIAM Journal on Discrete Mathematics, 26(3):1148–1180.

Bulteau, L., Fertin, G., and Tannier, E. (2016). Genome Rearrangements with Indels in Intergenes Restrict the Scenario Space. BMC Bioinformatics, 17(14):426.

Caprara, A. (1999). Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM Journal on Discrete Mathematics, 12(1):91–110.

Chen, J.-M., Cooper, D. N., Férec, C., Kehrer-Sawatzki, H., and Patrinos, G. P. (2010). Genomic Rearrangements in Inherited Disease and Cancer. Seminars in Cancer Biology, 20(4):222–233.

Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., and Jiang, T. (2005). Assignment of Orthologous Genes via Genome Rearrangement. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2(4):302–315.

El-Mabrouk, N. (2000). Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments. In Annual Symposium on Combinatorial Pattern Matching (CPM’2000), pages 222–234. Springer.

Elias, I. and Hartman, T. (2006). A 1.375-Approximation Algorithm for Sorting by Transpositions. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):369–379.

Fertin, G., Jean, G., and Tannier, E. (2017). Algorithms for Computing the Double Cut and Join Distance on both Gene Order and Intergenic Sizes. Algorithms for Molecular Biology, 12(1):16.

Fertin, G., Labarre, A., Rusu, I., Tannier, É., and Vialette, S. (2009). Combinatorics of Genome Rearrangements. Computational Molecular Biology. The MIT Press, London, England.

Garczarek, L., Guyet, U., Doré, H., Farrant, G. K., Hoebeke, M., Brillet-Guéguen, L., Bisch, A., Ferrieux, M., Siltanen, J., Corre, E., Corguillé, G. L., Ratin, M., Pitt, F. D., Ostrowski, M., Conan, M., Siegel, A., Labadie, K., Aury, J.-M., Wincker, P., Scanlan, D. J., and Partensky, F. (2020). Cyanorak v2.1: A Scalable Information System Dedicated to the Visualization and Expert Curation of Marine and Brackish Picocyanobacteria Genomes. Nucleic Acids Research, 49(D1):D667–D676.

Hannenhalli, S. and Pevzner, P. A. (1995). Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS’1995), pages 581–592, Washington, DC, USA. IEEE Computer Society Press.

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.

Lupski, J. R. (1998). Genomic Disorders: Structural Features of the Genome can Lead to DNA Rearrangements and Human Disease Traits. Trends in Genetics, 14(10):417–422.

Oliveira, A. R., Brito, K. L., Alexandrino, A. O., Siqueira, G., Dias, U., and Dias, Z. (2024). Rearrangement distance problems: An updated survey. ACM Computing Surveys, 56(8).

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

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. (2020). A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions. In Proceedings of the 7th International Conference on Algorithms for Computational Biology (AlCoB’2020), pages 16–28. Springer International Publishing.

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.

Sankoff, D. (1999). Genome Rearrangement with Gene Families. Bioinformatics, 15(11):909–917.

Schuy, J., Grochowski, C. M., Carvalho, C. M., and Lindstrand, A. (2022). Complex Genomic Rearrangements: an Underestimated Cause of Rare Diseases. Trends in Genetics, 38(11):1134–1146.

Shendure, J., Balasubramanian, S., Church, G. M., Gilbert, W., Rogers, J., Schloss, J. A., and Waterston, R. H. (2017). DNA sequencing at 40: past, present and future. Nature, 550(7676):345–353.

Silva, L. A. G., Kowada, L. A. B., Rocco, N. R., and Walter, M. E. M. T. (2022). A new 1.375-approximation algorithm for sorting by transpositions. Algorithms for Molecular Biology, 17(1):1–17.

Siqueira, G., Alexandrino, A. O., and Dias, Z. (2023a). Signed Rearrangement Distances Considering Repeated Genes, Intergenic Regions, and Indels. Journal of Combinatorial Optimization, 46(2):16.

Siqueira, G., Alexandrino, A. O., Oliveira, A. R., and Dias, Z. (2021). Approximation Algorithm for Rearrangement Distances Considering Repeated Genes and Intergenic Regions. Algorithms for Molecular Biology, 16(1):1–23.

Siqueira, G., Oliveira, A. R., Alexandrino, A. O., Jean, G., Fertin, G., and Dias, Z. (2024). Assignment of orthologous genes in unbalanced genomes using cycle packing of adjacency graphs. Journal of Heuristics.

Siqueira, G., Oliveira Alexandrino, A., Rodrigues Oliveira, A., Jean, G., Fertin, G., and Dias, Z. (2023b). Approximating Rearrangement Distances with Replicas and Flexible Intergenic Regions. In Proceedings of the 19th International Symposium on Bioinformatics Research and Applications (ISBRA’2023), volume 14248, pages 241–254. Springer.

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.

Willing, E., Zaccaria, S., Braga, M. D., and Stoye, J. (2013). On the Inversion-Indel Distance. BMC Bioinformatics, 14:S3.