Avanços no cálculo da distância Double Cut and Join com regiões intergênicas para genomas reais

Abstract

The double cut and join (DCJ) distance problem has been extensively studied in recent years, leading to the development of multiple algorithms for its different variations. However, limited attention has been given to the DCJ distance problem in the context of genomes containing duplicated genes and intergenic regions. The genome sizes and the inequalities of the intergenic sizes play an important role in the running times of algorithms; yet these factors are often overlooked in existing studies. In this work, we establish a formal definition for the DCJ distance problem considering intergenic regions and duplicated genes, and propose different strategies to find a heuristic solution for it by using existing exact and approximation algorithms. The methods we propose improve upon existing approaches in both quality and efficiency, particularly overcoming severe limitations of the current methods regarding the number of genes and intergenic size inequalities.