| Full text | |
| Author(s): |
Santos Miranda, Guilherme Henrique
;
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 | |
Estimating the evolutionary distance between genomes of two organisms is a challenging task for Computational Biology. One of the most well-accepted ways to do this is to consider the size of the smallest sequence of rearrangement events required to transform one genome into another, characterizing the rearrangement distance problem. Computationally, genomes can be represented as permutations of integers and, with this, the problem can be reduced to transforming a permutation into the identity with the minimum number of operations (sorting the permutation). These operations are given by a rearrangement model and they affect segments of a genome in different ways. Among the most common models are those that allow only reversals, only transpositions, or both of them. In this paper we study sorting permutations when a restriction of biological relevance is added: the size of the rearrangements should be at most a given value lambda. Some results are known for lambda = 2 and lambda = 3 but, to the best of our knowledge, there are no results for lambda > 3. We consider rearrangement models that allow reversals and/or transpositions for sorting unsigned permutations given any value of lambda. We present approximation algorithms for 3 such problems, where the approximation factors depend on lambda and/or on the size of the permutations. (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: | 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: | 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 |