Search

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}$G1 into the gene order from a genome $\mathcal {G}_{2}$G2. 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}$G1 into the list of intergenic regions sizes from $\mathcal {G}_{2}$G2 (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.

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.

In this paper, we consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex, that is, every set formed by all the vertices with the same color induces a connected subgraph. The problem is most commonly studied considering trees due to its origins in the study of phylogenetic trees, but in this paper, we focus on general graphs and propose a GRASP heuristic to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming model from the literature. In these experiments, the GRASP algorithm recolored a similar number of vertices than the model from the literature, and used considerably less time. We also introduce a set of benchmark instances for the problem. [ABSTRACT FROM AUTHOR]

Genome rearrangements are events that affect large portions of a genome. When using the rearrangement distance to compare two genomes, one wants to find a minimum cost sequence of rearrangements that transforms one into another. Since we represent genomes as permutations, we can reduce this problem to the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the traditional approach, we consider that all rearrangements are equally likely to occur and we set a unitary cost for all rearrangements. However, there are two variations of the problem motivated by the observation that rearrangements involving large segments of a genome rarely occur. The first variation adds a restriction to the rearrangement's length. The second variation uses a cost function based on the rearrangement's length. In this work, we present approximation algorithms for five problems combining both variations, that is, problems with a length-limit restriction and a cost function based on the rearrangement's length. [ABSTRACT FROM AUTHOR]

One possible model to study genome evolution is to represent genomes as permutations of genes and compute distances based on the minimum number of certain operations (rearrangements) needed to transform one permutation into another. Under this model, the shorter the distance, the closer the genomes are. Two operations that have been extensively studied are the reversal and the transposition. A reversal is an operation that reverses the order of the genes on a certain portion of the permutation. A transposition is an operation that "cuts" a certain portion of the permutation and "pastes" it elsewhere in the same permutation. In this note, we show that the reversal and transposition distance of the signed permutation πn = (-1 -2...-(n - 1)-n) with respect to the identity is ⌊n/2⌋ + 2 for all n≥3. We conjecture that this value is the diameter of the permutation group under these operations.