JUCS - Journal of Universal Computer Science 25(2): 98-121, doi: 10.3217/jucs-025-02-0098

Sorting Permutations by λ-Operations

‡ University of Campinas, Campinas, Brazil

Corresponding author: Guilherme Henrique Santos Miranda ( guilherme.miranda@students.ic.unicamp.br ) © Guilherme Henrique Santos Miranda, Carla Lintzmayer, Zanoni Dias. This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use. Citation:
Miranda GHS, Lintzmayer CN, Dias Z (2019) Sorting Permutations by λ-Operations. JUCS - Journal of Universal Computer Science 25(2): 98-121. https://doi.org/10.3217/jucs-025-02-0098 |

Abstract

For estimating the evolutionary distance between genomes of two different organisms, many sorting permutation problems have emerged. A well accepted way to do this is considering the smallest sequence of rearrangement events { mutations which affect large portions of the genomes { that transform one genome into the other. In these problems, both genomes are represented as permutations of integer numbers, but one of them can be represented as the identity permutation, so that the problem is reduced to sort a permutation. Moreover, rearrangement models define which type of operations (rearrangement events) can be applied over a permutation in order to modify it. Reversals, which are operations that revert a genome segment, and transpositions, which are operations that swap two adjacent genome segments, are two of the most studied types of rearrangements in the literature. In this paper, we consider rearrangement models that allow reversals, transpositions, and both operations together. Since there exist evidences that large mutations rarely occur, we add a restriction with biological relevance: any operation can affect at most λ elements of a permutation. For this variation of sorting permutation problem, we present approximation algorithms with approximation factors based on the size of the permutation and/or on λ, for both signed and unsigned permutations (which represent known and unknown gene orientations, respectively).

Keywords

sorting permutations, genome rearrangements, reversals, transpositions, computational biology