| Full text | |
| Author(s): |
Alexandrino, Alexsandro Oliveira
[1]
;
Miranda, Guilherme Henrique Santos
[1]
;
Lintzmayer, Carla Negri
[2]
;
Dias, Zanoni
[1]
Total Authors: 4
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 41, n. 3, p. 579-602, APR 2021. |
| Web of Science Citations: | 1 |
| Abstract | |
Comparative genomics is a field of biology that aims at comparing genomes of different species. One major question of this field is to find the evolutionary distance between two given genomes. One way to estimate such distance is to use the rearrangement distance, which consists in finding a minimum cost sequence of rearrangements that transforms one genome into another. We use permutations to model the genomes being compared and, in this way, we can treat this problem as the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the early works with rearrangement distance, it was considered that all rearrangements are equally likely to occur and, consequently, they use a unitary cost for all rearrangements. Some variations of the problem were motivated by the observation that rearrangements involving large segments of a genome rarely occur. One of these variants also uses a unitary cost, however it adds a constraint in the length of the operations allowed to estimate the distance. Another variant uses a cost function based on the rearrangement's length. In this work, we study problems that combine both variants, that is, problems with a constraint in the rearrangement's length and with a cost function based on the rearrangement's length. We present approximation algorithms for five such problems involving reversals and/or transpositions for sorting signed and unsigned permutations. We also analyze the problems for specific parameters of the length restriction and for when the cost function is equal to l(alpha), where l is the rearrangement's length and alpha >= 1 is a real value parameter. (AU) | |
| 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: | 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: | 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 |