Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Sorting Permutations by lambda-Operations

Santos Miranda, Guilherme Henrique [1] ; Lintzmayer, Carla Negri [2] ; Dias, Zanoni [1]
Total Authors: 3
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre - Brazil
Total Affiliations: 2
Document type: Journal article
Source: JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 25, n. 2, p. 98-121, 2019.
Web of Science Citations: 0

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 lambda 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 lambda, for both signed and unsigned permutations (which represent known and unknown gene orientations, respectively). (AU)

FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
Grantee:Anderson de Rezende Rocha
Support type: Research Projects - Thematic Grants
FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants
FAPESP's process: 16/14132-4 - One and two-dimensional bin packing with conflicts and unloading restrictions
Grantee:Carla Negri Lintzmayer
Support type: Scholarships in Brazil - Post-Doctorate