Sorting permutations by prefix reversals and suffix reversals
The sorting permutations problem using prefix and suffix operations
Full text | |
Author(s): |
Alexandrino, Alexsandro Oliveira
[1]
;
Oliveira, Andre Rodrigues
[1]
;
Dias, Ulisses
[2]
;
Dias, Zanoni
[1]
Total Authors: 4
|
Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Campinas - Brazil
[2] Univ Estadual Campinas, Sch Technol, Limeira - Brazil
Total Affiliations: 2
|
Document type: | Journal article |
Source: | JOURNAL OF COMPUTATIONAL BIOLOGY; v. 28, n. 3, p. 235-247, MAR 1 2021. |
Web of Science Citations: | 0 |
Abstract | |
The rearrangement distance is a well-known problem in the field of comparative genomics. Given two genomes, the rearrangement distance is the minimum number of rearrangements in a set of allowed rearrangements (rearrangement model), which transforms one genome into the other. In rearrangement distance problems, a genome is modeled as a string, where each element represents a conserved region within the two genomes. When the orientation of the genes is known, it is represented by (plus or minus) signs assigned to the elements of the string. Two of the most studied rearrangements are reversals, which invert a segment of the genome, and transpositions, which exchange the relative positions of two adjacent segments of the genome. The first works in genome rearrangements considered that the genomes being compared had the same genetic material and that rearrangement events were restricted to reversals, transpositions, or both. El-Mabrouk extended the reversal model on signed strings to include the operations of insertion and deletion of segments in the genome, which allowed the comparison of genomes with different genetic material. Other studies also addressed this problem and, recently, this problem was proved to be solvable in polynomial time by Willing et al. For unsigned strings, we still observe a lack of results. That said, in this study we prove that computing the rearrangement distance for the following models is NP-Hard: reversals and indels on unsigned strings; transpositions and indels on unsigned strings; and reversals, transpositions, and indels on signed and unsigned strings. Along with the NP-hardness proofs, we present a 2-approximation algorithm for reversals on unsigned strings and 3-approximation algorithms for the other models. (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: | 19/27331-3 - Sorting by genome rearrangements problems |
Grantee: | André Rodrigues Oliveira |
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: | 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 |