Assignment of orthologous genes in unbalanced genomes using cycle packing of adjacency graphs

Gabriel Siqueira (), Andre Rodrigues Oliveira (), Alexsandro Oliveira Alexandrino (), Géraldine Jean (), Guillaume Fertin () and Zanoni Dias ()
Additional contact information
Gabriel Siqueira: Universidade Estadual de Campinas (UNICAMP)
Andre Rodrigues Oliveira: Universidade Presbiteriana Mackenzie
Alexsandro Oliveira Alexandrino: Universidade Estadual de Campinas (UNICAMP)
Géraldine Jean: Nantes Université, École Centrale Nantes
Guillaume Fertin: Nantes Université, École Centrale Nantes
Zanoni Dias: Universidade Estadual de Campinas (UNICAMP)

Journal of Heuristics, 2024, vol. 30, issue 5, No 2, 269-289

Abstract: 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.

Keywords: Genome rearrangements; Cycle packing; Transposition; Reversals; Indels (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09528-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09528-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09528-z

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().