| Texto completo | |
| Autor(es): |
Siqueira, Gabriel
;
Oliveira, Andre Rodrigues
;
Alexandrino, Alexsandro Oliveira
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Zanoni
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Journal of Heuristics; v. 30, n. 5-6, p. 21-pg., 2024-05-31. |
| Resumo | |
The adjacency graph is a structure used to model genomes in several rearrangement distance problems. In particular, most studies use properties of a maximum cycle packing of this graph to develop bounds and algorithms for rearrangement distance problems, such as the reversal distance, the reversal and transposition distance, and the double cut and join distance. When each genome has no repeated genes, there exists only one cycle packing for the graph. However, when each genome may have repeated genes, the problem of finding a maximum cycle packing for the adjacency graph (adjacency graph packing) is NP-hard. In this work, we develop a randomized greedy heuristic and a genetic algorithm heuristic for the adjacency graph packing problem for genomes with repeated genes and unequal gene content. We also propose new algorithms with simple implementation and good practical performance for reversal distance and reversal and transposition distance in genomes without repeated genes, which we combine with the heuristics to find solutions for the problems with repeated genes. We present experimental results and compare the application of these heuristics with the application of the MSOAR framework in rearrangement distance problems. Lastly, we apply our genetic algorithm heuristic to real genomic data to validate its practical use. (AU) | |
| Processo FAPESP: | 21/13824-8 - Generalizações de problemas envolvendo partição de strings |
| Beneficiário: | Gabriel Henriques Siqueira |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 22/13555-0 - Distância de rearranjo em genomas não balanceados considerando regiões intergênicas |
| Beneficiário: | Gabriel Henriques Siqueira |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |