Sorting permutations by prefix reversals and suffix reversals
The sorting permutations problem using prefix and suffix operations
Problems of sorting permutations by fragmentation-weighted operations
| Full text | |
| Author(s): |
Oliveira, Andre Rodrigues
;
Brito, Klairton Lima
;
Dias, Zanoni
;
Dias, Ulisses
;
Alves, R
Total Authors: 5
|
| Document type: | Journal article |
| Source: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018; v. 11228, p. 12-pg., 2018-01-01. |
| Abstract | |
Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem in two variants depending on whether we model genomes as signed or unsigned permutations. Here, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present one algorithm with an approximation factor of 2 for both signed or unsigned permutations, and one algorithm with an approximation factor of 5/3 for signed permutations. We also analyze the behavior of the 5/3-approximation algorithm with different weights for reversals and transpositions. (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: | 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/16246-0 - Sensitive media analysis through deep learning architectures |
| Grantee: | Sandra Eliza Fontes de Avila |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 17/16871-1 - Problems of sorting permutations by fragmentation-weighted operations |
| Grantee: | Alexsandro Oliveira Alexandrino |
| Support Opportunities: | Scholarships in Brazil - Master |