On Variants of the Genome Rearrangement Distance Problem
Resumo
Na genômica comparativa, a distância evolucionária pode ser estimada determinando uma sequência mínima de rearranjos de genomas necessários para transformar um genoma em outro. O tamanho dessa sequência é chamado de distância de rearranjos. Tradicionalmente, a maioria dos estudos assumiu que os genomas comparados compartilhavam o mesmo conjunto de genes, utilizando apenas a ordem relativa dos genes para a comparação. Estudos recentes indicam que incorporar o tamanho das regiões intergênicas leva a estimativas de distância mais precisas ao analisar genomas reais. Além disso, esses estudos começaram a considerar que os genomas possuem um conjunto distinto de genes. Neste trabalho, investigamos problemas de rearranjos de genomas incorporando informações adicionais e complexidade aos modelos, a fim de alcançar resultados práticos mais realistas que possam beneficiar diversos campos científicos.Referências
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.
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.
Publicado
20/07/2025
Como Citar
ALEXANDRINO, Alexsandro Oliveira; DIAS, Ulisses; DIAS, Zanoni.
On Variants of the Genome Rearrangement Distance Problem. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 38. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 5-14.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2025.7128.
