Problems of sorting permutations by fragmentation-weighted operations
The sorting permutations problem using prefix and suffix operations
Sorting permutations by prefix reversals and suffix reversals
| Full text | |
| Author(s): |
Alexandrino, Alexsandro Oliveira
;
Lintzmayer, Carla Negri
;
Dias, Zanoni
;
Jansson, J
;
MartinVide, C
;
VegaRodriguez, MA
Total Authors: 6
|
| Document type: | Journal article |
| Source: | ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018); v. 10849, p. 12-pg., 2018-01-01. |
| Abstract | |
Rearrangements are mutations that affect large portions of a genome. When comparing two genomes, one wants to find a sequence of rearrangements that transforms one into another. When we use permutations to represent the genomes, this reduces to the problem of sorting a permutation using some sequence of rearrangements. The traditional approach is to find a sequence of minimum length. However, some studies show that some rearrangements are more likely to disturb an individual, and so a weighted approach is closer to the real evolutionary process. Most weighted approaches consider that the cost of a rearrangement can be related to its type or to the number of elements affected by it. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for 5 versions of the fragmentation-weighted problem involving reversals and transpositions events. (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 Opportunities: | 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 Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 17/16871-1 - Problems of sorting permutations by fragmentation-weighted operations |
| Grantee: | Alexsandro Oliveira Alexandrino |
| Support Opportunities: | Scholarships in Brazil - Master |