Reversals Distance Considering Flexible Intergenic Regions Sizes.

Most mathematical models for genome rearrangement problems have considered only gene order. In this way, the rearrangement distance considering some set of events, such as reversal events, is commonly defined as the minimum number of rearrangement events that transform the gene order from a genome \(\mathcal {G}_1\) into the gene order from a genome \(\mathcal {G}_2\). Recent works initiate incorporating more information such as the sizes of the intergenic regions (i.e., number of nucleotides between pairs of consecutive genes), which yields good results for estimated distances on realistic data. In these models, besides transforming the gene order, the sequence of rearrangement events must transform the list of intergenic regions sizes from \(\mathcal {G}_1\) into the list of intergenic regions sizes from \(\mathcal {G}_2\) (target list). We study a new variation where each value from the target list is flexible, in the sense that each target intergenic region size is a range of acceptable values. We consider the well-known reversals distance and present a 2-approximation algorithm, alongside NP-hardness proof. Our results rely on the Flexible Weighted Cycle Graph, adapted from the breakpoint graph to deal with flexible intergenic regions sizes.