# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 1 Introduction  
One challenge in biology is to understand how species evolve, considering that new organisms arise from mutations that occurred in others. Using the _principle of parsimony_, the minimum number of rearrangements that transform one genome into another, called _rearrangement distance_, is a widely adopted way to estimate the evolutionary distance between two genomes. A _genome rearrangement_ is a global mutation that alters the order and the orientation of the genes in a genome. Depending on the genomic information available and the problems considered, a genome can be modeled in different ways. Considering that a genome has no repeated genes, we can model it as a _permutation_, with each element representing a gene. Each gene has an orientation inside the genome. Gene orientation is represented by a plus or minus sign in each element of the permutation. In this case, we say that the permutation is signed. Due to mapping problems in the genome, orientation information could not be available. In this scenario, we use unsigned permutations to represent the genomes. By representing one of the genomes as the identity permutation, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation with the minimum number of rearrangements, which is called sorting rearrangement distance or simply _distance_. A _rearrangement model_\(\mathcal{M}\) is the set of valid rearrangements used to calculate the distance. A _reversal_ rearrangement inverts a segment of the genome, and a _transpositionrearrangement swaps two adjacent segments of the genome. Genome rearrangements are also sometimes called operations. The problems of Sorting Permutations by Transpositions and Sorting Unsigned Permutations by Reversals are NP-Hard [1; 2]. The best known results for both problems are approximation algorithms with factor 1.375 [3; 4]. Despite that, the problem of Sorting Signed Permutations by Reversals is solvable in polynomial time [5]. The variation in which the rearrangement model contains both (signed or unsigned) reversals and transpositions is NP-Hard [6]. For signed permutations, there are 2-approximation algorithms [7; 8]. For unsigned permutations, the best approximation factor is \(2k\)[7], where \(k\) is the approximation factor of an algorithm used for cycle decomposition of the breakpoint graph [9]. Given the best known value for \(k\)[9], this algorithm guarantees an approximation factor of \(2.8334+\epsilon\), where \(\epsilon>0\). Extra restrictions can be added to these sorting problems, such as applying operations that only affect specific parts of a genome [10; 11]. Other variants of the sorting problems emerged from the assumption that operations which affect large portions of a genome are less likely to occur [12]. Most of these variants add a constraint that limits the size of a valid operation [13; 14; 15]. The size of an operation is equal to the number of elements affected by it. Considering a size limit of 2, the problems of Sorting Unsigned Permutations by Reversals and/or Transpositions are solvable in polynomial time [13]. Considering a size limit of 3, the best known approximation factors for Sorting Unsigned Permutations by Reversals, by Transpositions, and by Reversals and Transpositions are 2 [13], 5/4 [14], and 2 [15], respectively. For Sorting Signed Permutations by Reversals and by Reversals and Transpositions, the best known approximation factors are 5 [16] and 3 [16], respectively. Recently, [PERSON] et al. [17] presented polynomial algorithms to decide if a permutation can be sorted using a number of short operations equal to the lower bound for the distance, which are based on the number of inversions and entropy of the permutation (these concepts are described in Sections 3 and 4). The problem of Sorting (Unsigned or Signed) Permutations by \(\lambda\)-Operations is a generalization of the size limited variants in which an operation is valid if its size is less than or equal to \(\lambda\).