Heurísticas para Problemas de Rearranjo de Genomas com Genes Multiplicados

• Gabriel Siqueira UNICAMP
• Andre Rodrigues Oliveira UNICAMP
• Zanoni Dias UNICAMP

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

Resumo

Um dos objetivos dos problemas de rearranjo de genomas consiste em estimar a distância evolutiva entre genomas de diferentes espécies utilizando eventos de rearranjo, mutações capazes de alterar a sequência genética dos genomas. Diferentes problemas de rearranjo podem ser definidos de acordo com os eventos utilizados e as características dos genomas considerados. O objetivo do trabalho foi o desenvolvimento de heurísticas para resolver problemas de rearranjo de genomas considerando genes multiplicados e os eventos de rearranjo de reversão e transposição. Desenvolvemos heurísticas baseadas em técnicas amplamente adotadas para problemas de otimização combinatória, como Busca Local, Algoritmos Genéticos e GRASP. Nos testes realizados, verificamos que as distâncias obtidas pelas heurísticas propostas são menores que as distâncias obtidas por algoritmos da literatura.

Palavras-chave: Biologia Computacional, Rearranjo de genomas, Heurística

Referências

Berman, P., Hannenhalli, S., and Karpinski, M. (2002). 1.375-Approximation Algorithm for Sorting by Reversals. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA’2002), pages 200–210, London, UK. Springer-Verlag.

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

Caprara, A. (1999). Sorting permutations by reversals and eulerian cycle decompositions. SIAM Journal on Discrete Mathematics, 12(1):91–110.

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.

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., Labarre, A., Rusu, I., Tannier, E., and Vialette, S. (2009). Combinatorics of Genome Rearrangements. Computational Molecular Biology. The MIT Press, London, England, 1 edition.

Hannenhalli, S. and Pevzner, P. A. (1999). Transforming cabbage into turnip. Journal of ACM, 46(1):1–27.

Kolman, P. and Walén, T. (2007). Approximating reversal distance for strings with bounded number of duplicates. Discrete Applied Mathematics, 155(3):327–336.

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(11):1223–1229.

Radcliffe, A. J., Scott, A. D., and Wilmer, E. (2005). Reversals and transpositions over finite alphabets. SIAM Journal on Discrete Mathematics, 19(1):224–244.

Rahman, A., Shatabda, S., and Hasan, M. (2008). An approximation algorithm for sorting by reversals and transpositions. Journal of Discrete Algorithms, 6(3):449–457.

Shao, M., Lin, Y., and Moret, B. M. (2015). An exact algorithm to compute the doublecut-and-join distance for genomes with duplicate genes. Journal of Computational Biology, 22(5):425–435.

Shapira, D. and Storer, J. A. (2007). Edit distance with move operations. Journal of Discrete Algorithms, 5(2):380–392.

Walter, M. E. M., Dias, Z., and Meidanis, J. (1998). Reversal and transposition distance of linear chromosomes. In Proceedings of the String Processing and Information Retrieval: A South American Symposium (SPIRE’1998), pages 96–102, Los Alamitos, CA, USA.

Yancopoulos, S., Attie, O., and Friedberg, R. (2005). Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics, 21(16):3340–3346.