Genome Rearrangement distance problems are used in Computational Biology to estimate the evolutionary distance between genomes. These problems consist of minimizing the number of rearrangement events necessary to transform one genome into another. Two commonly used rearrangement events are reversal and transposition. The first studied problems ignored nucleotides outside genes (called intergenic regions), or assumed that genomes have a single copy of each gene. Recent works made advancements in more general problems considering the number of nucleotides in intergenic regions, and replicated genes. Nevertheless, genomes tend to have wildly different quantities of nucleotides on their intergenic regions, which poses a problem when comparing these regions exactly. To overcome this limitation, our work considers some flexibility when matching intergenic regions that do not have the same number of nucleotides. We propose new problems seeking the minimum number of reversals, or reversals and transpositions, necessary to transform one genome into another, while considering flexible intergenic region information. We show approximations for these problems by exploring their relationship with the Signed Minimum Common Flexible Intergenic String Partition problem. We also present different heuristics for the partition problem, and conduct experimental tests on simulated genomes to assess the performance of our algorithms.

Recent works on genome rearrangements have shown that incorporating intergenic region information along with gene order in models provides better estimations for the rearrangement distance than using gene order alone. The reversal distance is one of the main problems in genome rearrangements. It has a polynomial time algorithm when only gene order is used to model genomes, assuming that repeated genes do not exist and that gene orientation is known, even when the genomes have distinct gene sets. The reversal distance is NP-hard and has a 2-approximation algorithm when incorporating intergenic regions. However, the problem has only been studied assuming genomes with the same set of genes. In this work, we consider the variation that incorporates intergenic regions and that allows genomes to have distinct sets of genes, a scenario that leads us to include indels operations (insertions and deletions). We present a 2.5-approximation algorithm using the labeled intergenic breakpoint graph, which is based on the well-known breakpoint graph structure. We also present an experimental analysis of the proposed algorithm using simulated data, which showed that the practical approximation factor is considerably less than 2.5. Furthermore, we used the algorithm in real genomes to construct a phylogenetic tree.

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 and transposition 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 real 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 the target list is flexible, in the sense that each target intergenic region size is in a range of acceptable values. This allows us to model scenarios where the main objective is still to transform the order of genes from the source genome into the target genome, allowing flexibility in the sizes of the intergenic regions, since the nucleotides in these regions tend to undergo more changes when compared to genes. We investigate the rearrangement distance considering three sets of events, two with the exclusive use of reversals or transpositions, and the other allowing both rearrangement events. We present approximation algorithms for the problems and an NP-hardness proof. Our results rely on the Flexible Weighted Cycle Graph, adapted from the breakpoint graph to deal with flexible intergenic regions sizes.

Biologists have proposed a vast list of problems heavily studied by mathematicians, computer scientists, and statisticians. From a theoretical point of view, biology can inspire exciting new problems when one is interested in estimating genetic modifications that occurred in the course of evolution. Structural modifications, such as genome rearrangements, are important for comparative genomics and they have led to many NP-hard problems. Reversal and Transposition are the most studied genome rearrangement events. To solve these problems, the gene order inside a genome is usually mapped into a permutation or a string. Permutations do not allow us to work with duplicate genes; in this case strings should be used. Problems with reversals and transpositions on permutations and strings are being studied since the 70s. Recently, studies start incorporating information regarding the size of the intergenic regions, which are genetic regions between each pair of consecutive genes inside the genome with a specific number of nucleotides. Problems can differ by changing the genetic information carried into the representation model, but all of them aim to transform a source genome into a target genome. In this work, we study the Sorting by Reversals with Flexible Intergenic Regions and Sorting by Reversals and Transpositions with Flexible Intergenic Regions problems on unsigned permutations. The goal is still to transform a source genome into the target genome, but turning the constraint less strict regarding the size of the intergenic regions on the target genome. We present a theoretical study showing that both problems are NP-hard and algorithms with constant approximation factor.