Heuristics based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915102015356928 |
|---|---|
| author | Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Zanoni |
| author_facet | Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Zanoni |
| contents | In this work, we explore heuristics for the Adjacency Graph Packing problem, which can be applied to the Double Cut and Join (DCJ) Distance Problem. The DCJ is a rearrangement operation and the distance problem considering it is a well established method for genome comparison. Our heuristics will use the structure called adjacency graph adapted to include information about intergenic regions, multiple copies of genes in the genomes, and multiple circular or linear chromosomes. The only required property from the genomes is that it must be possible to turn one into the other with DCJ operations. We propose one greedy heuristic and one heuristic based on Genetic Algorithms. Our experimental tests in artificial genomes show that the use of heuristics is capable of finding good results that are superior to a simpler random strategy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07606 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Heuristics based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions Siqueira, Gabriel Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Zanoni Quantitative Methods In this work, we explore heuristics for the Adjacency Graph Packing problem, which can be applied to the Double Cut and Join (DCJ) Distance Problem. The DCJ is a rearrangement operation and the distance problem considering it is a well established method for genome comparison. Our heuristics will use the structure called adjacency graph adapted to include information about intergenic regions, multiple copies of genes in the genomes, and multiple circular or linear chromosomes. The only required property from the genomes is that it must be possible to turn one into the other with DCJ operations. We propose one greedy heuristic and one heuristic based on Genetic Algorithms. Our experimental tests in artificial genomes show that the use of heuristics is capable of finding good results that are superior to a simpler random strategy. |
| title | Heuristics based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions |
| topic | Quantitative Methods |
| url | https://arxiv.org/abs/2501.07606 |