| Full text | |
| Author(s): |
Siqueira, Gabriel
;
Oliveira, Andre Rodrigues
;
Alexandrino, Alexsandro Oliveira
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Zanoni
Total Authors: 6
|
| Document type: | Journal article |
| Source: | Journal of Heuristics; v. 30, n. 5-6, p. 21-pg., 2024-05-31. |
| Abstract | |
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) | |
| FAPESP's process: | 21/13824-8 - Generalization of string partition problems |
| Grantee: | Gabriel Henriques Siqueira |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 22/13555-0 - Rearrangement distances in unbalanced genomes considering intergenic regions |
| Grantee: | Gabriel Henriques Siqueira |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |