| Full text | |
| Author(s): |
Oliveira, Andre Rodrigues
[1]
;
Jean, Geraldine
[2]
;
Fertin, Guillaume
[2]
;
Brito, Klairton Lima
[1]
;
Bulteau, Laurent
[3]
;
Dias, Ulisses
[4]
;
Dias, Zanoni
[1]
Total Authors: 7
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, 1251 Albert Einstein Ave, BR-13083852 Campinas - Brazil
[2] Univ Nantes, LS2N CNRS UMR 6004, 2 Rue Houssiniere, F-44322 Nantes 3 - France
[3] Univ Paris Est Marne La Vallee, LIGM CNRS UMR 8049, 5 Bd Descartes, F-77454 Marne La Vallee - France
[4] Univ Estadual Campinas, Sch Technol, 1888 Paschoal Marmo St, BR-13484332 Limeira - Brazil
Total Affiliations: 4
|
| Document type: | Journal article |
| Source: | IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 18, n. 6, p. 2870-2876, NOV 1 2021. |
| Web of Science Citations: | 3 |
| Abstract | |
Genome rearrangements are mutations affecting large portions of a genome, and a reversal is one of the most studied genome rearrangements in the literature through the Sorting by Reversals (SbR) problem. SbR is solvable in polynomial time on signed permutations (i.e., the gene orientation is known), and it is NP-hard on unsigned permutations. This problem (and many others considering genome rearrangements) models genome as a list of its genes in the order they appear, ignoring all other information present in the genome. Recent works claimed that the incorporation of the size of intergenic regions, i.e., sequences of nucleotides between genes, may result in better estimators for the real distance between genomes. Here we introduce the Sorting Signed Permutations by Intergenic Reversals problem, that sorts a signed permutation using reversals both on gene order and intergenic sizes. We show that this problem is NP-hard by a reduction from the 3-partition problem. Then, we propose a 2-approximation algorithm for it. Finally, we also incorporate intergenic indels (i.e., insertions or deletions of intergenic regions) to overcome a limitation of sorting by conservative events (such as reversals) and propose two approximation algorithms. (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: | 19/27331-3 - Sorting by genome rearrangements problems |
| Grantee: | André Rodrigues Oliveira |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| 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: | 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 |