| Full text | |
| Author(s): |
Brito, Klairton Lima
;
Alexandrino, Alexsandro Oliveira
;
Oliveira, Andre Rodrigues
;
Dias, Ulisses
;
Dias, Zanoni
Total Authors: 5
|
| Document type: | Journal article |
| Source: | IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 20, n. 3, p. 13-pg., 2023-05-01. |
| Abstract | |
Most mathematical models for genome rearrangement problems have considered only gene order. In this way, the rearrangement distance considering some set of events, such as reversal and transposition events, is commonly defined as the minimum number of rearrangement events that transform the gene order from a genome G(1) into the gene order from a genome G(2). Recent works initiate incorporating more information such as the sizes of the intergenic regions (i.e., number of nucleotides between pairs of consecutive genes), which yields good results for estimated distances on real data. In these models, besides transforming the gene order, the sequence of rearrangement events must transform the list of intergenic regions sizes from G(1) into the list of intergenic regions sizes from G(2) (target list). We study a new variation where the target list is flexible, in the sense that each target intergenic region size is in a range of acceptable values. This allows us to model scenarios where the main objective is still to transform the order of genes from the source genome into the target genome, allowing flexibility in the sizes of the intergenic regions, since the nucleotides in these regions tend to undergo more changes when compared to genes. We investigate the rearrangement distance considering three sets of events, two with the exclusive use of reversals or transpositions, and the other allowing both rearrangement events. We present approximation algorithms for the problems and an NP-hardness proof. Our results rely on the Flexible Weighted Cycle Graph, adapted from the breakpoint graph to deal with flexible intergenic regions sizes. (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: | 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 |