The sorting permutations problem using prefix and suffix operations
Sorting permutations by prefix reversals and suffix reversals
Morphophonological processes triggered by the suffixes -s/ção and -mento in the fo...
| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Nantes, UMR CNRS 6241, Lab Informat Nantes Atlantique, F-44322 Nantes 3 - France
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | THEORETICAL COMPUTER SCIENCE; v. 593, p. 26-41, AUG 16 2015. |
| Web of Science Citations: | 2 |
| Abstract | |
The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearrangements that are needed to sort a given permutation, and numerous efforts have been made over the past years regarding these problems. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. In this paper we present the first results regarding problems of sorting permutations by length-weighted operations that consider rearrangement models with prefix and suffix variations of reversals and transpositions, which are the two most common types of genome rearrangements. Our main results are O (lg(2) n)-approximation algorithms for 10 such problems. (C) 2015 Elsevier B.V. All rights reserved. (AU) | |
| 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: | 14/20738-7 - Sorting permutations by prefix reversals and suffix reversals |
| Grantee: | Carla Negri Lintzmayer |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate (Direct) |
| FAPESP's process: | 14/19401-8 - Genome rearrangement algorithms |
| Grantee: | Zanoni Dias |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 13/01172-0 - The sorting permutations problem using prefix and suffix operations |
| Grantee: | Carla Negri Lintzmayer |
| Support Opportunities: | Scholarships in Brazil - Doctorate (Direct) |