Estudo de heurísticas para distância por transposição considerando regiões intergênicas e repetição de genes

Abstract

This study focuses on the computation of Intergenic Transposition Distance (ITD) in linear genomes with repeated genes and intergenic regions, a key issue for understanding biological evolution. We explore an approximate solution proposed by [Siqueira et al., 2021], which leverages the Minimum Common Intergenic String Partition Problem (MCISP) as a subroutine. Both ITD and MCISP are NP-hard problems. The primary objective of this research is to evaluate the practical implications of using MCISP as a subroutine by substituting it with conceptually simpler heuristics. Preliminary findings indicate that employing heuristics for this step has the potential to enhance solution quality.