| Full text | |
| Author(s): |
Oliveira, Andre Rodrigues
[1]
;
Jean, Geraldine
[2]
;
Fertin, Guillaume
[2]
;
Brito, Klairton Lima
[1]
;
Dias, Ulisses
[3]
;
Dias, Zanoni
[1]
Total Authors: 6
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, BR-13083970 Campinas - Brazil
[2] Univ Nantes, LS2N, CNRS, UMR 6004, F-44035 Nantes - France
[3] Univ Estadual Campinas, Sch Technol, BR-13484350 Limeira - Brazil
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 18, n. 6, p. 2080-2093, NOV 1 2021. |
| Web of Science Citations: | 0 |
| Abstract | |
Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data. (AU) | |
| 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: | 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 |