Search

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. [ABSTRACT FROM AUTHOR]

In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption, one can assign different weights to different events, where common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here, we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We show the complexity of this problem for any desired proportion considering scenarios where the orientation of the genes is known or unknown. We also develop an approximation algorithm with a constant approximation factor for each scenario and, in particular, we describe an improved (asymptotic) approximation algorithm for the case where the gene orientation is known. At last, we present the experimental tests comparing the proposed algorithms with others from the literature for the version of the problem without the proportion restriction. [ABSTRACT FROM AUTHOR]