Search

Considering a pair of genomes, the goal of rearrangement distance problems is to estimate how distant these genomes are from each other based on genome rearrangements. Seminal works in genome rearrangements assumed that both genomes being compared have the same set of genes (balanced genomes) and, furthermore, only the relative order of genes and their orientations, when they are known, are used in the mathematical representation of the genomes. In this case, the genomes are represented as permutations, originating the Sorting Permutations by Rearrangements problems. The main problems of Sorting Permutations by Rearrangements considered DCJs, reversals, transpositions, or the combination of both reversals and transpositions, and these problems have their complexity known. Besides these problems, other ones were studied involving the combination of transpositions with one or more of the following rearrangements: transreversals, revrevs, and reversals. Although there are approximation results for these problems, their complexity remained open. Some of the results of this thesis are the complexity proofs for these problems. Furthermore, we present a new 1.375-approximation algorithm, which has better time complexity, for the Sorting Permutations by Transpositions. When considering unbalanced genomes, it is necessary to use insertions and deletions to transform one genome into another. In this thesis, we studied Rearrangement Distance problems on unbalanced genomes considering only gene order and their orientations (when they are known), as well as Intergenic Rearrangement Distance problems, which incorporate the information regarding the size distribution of intergenic regions, besides the use of gene order and their orientations (when they are known). We present complexity proofs and approximation algorithms for problems that include reversals and transpositions., Comment: PhD Dissertation, in Portuguese, presented at the Institute of Computing - Unicamp in March 2024

Given an Eulerian graph G, in the Maximum Eulerian Cycle Decomposition problem, we are interested in finding a collection of edge-disjoint cycles {E_1, E_2, ..., E_k} in G such that all edges of G are in exactly one cycle and k is maximum. We present an algorithm to solve the pricing problem of a column generation Integer Linear Programming (ILP) model introduced by Lancia and Serafini (2016). Furthermore, we propose a greedy heuristic, which searches for minimum size cycles starting from a random vertex, and a heuristic based on partially solving the ILP model. We performed tests comparing the three approaches in relation to the quality of solutions and execution time, using distinct sets of Eulerian graphs, each set grouping graphs with different numbers of vertices and edges. Our experimental results show that the ILP based heuristic outperforms the other methods.

One of the main challenges in Computational Biology is to find the evolutionary distance between two organisms. In the field of comparative genomics, one way to estimate such distance is to find a minimum cost sequence of rearrangements (large scale mutations) needed to transform one genome into another, which is called the rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. The complexity of the problems involving reversals, transpositions, and both rearrangements is known, even though the hardness proof for the problem combining reversals and transpositions was recently given. In this paper, we enhance the knowledge for these problems by proving that models involving transpositions alongside reversals, transreversals, and revrevs are NP-hard, considering weights w1 for reversals and w2 for the other rearrangements such that w2/w1 is less than or equal to 1.5. In addition, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function with some restrictions, is NP-hard for transpositions and the combination of reversals and transpositions.