| Full text | |
| Author(s): |
Alexandrino, Alexsandro Oliveira
;
Oliveira, Andre Rodrigues
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Ulisses
;
Dias, Zanoni
;
Bansal, MS
;
Cai, Z
;
Mangul, S
Total Authors: 9
|
| Document type: | Journal article |
| Source: | BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2022; v. 13760, p. 14-pg., 2022-01-01. |
| Abstract | |
In seminal works of genome rearrangements, the distance between two genomes is measured by the minimum number of rearrangements (e.g., reversals, transpositions, DCJs, or combination of them) needed to transform a given permutation into another, where permutations represent gene orders of genomes with the same gene content. For the past few years, researchers have been extending the traditional models of genome rearrangement distance by either considering unbalanced genomes or adding more features to the representation of the genomes to be compared. In this work, we make progress in this direction by studying the intergenic transposition distance on unbalanced genomes, which also considers insertions and deletions as non-conservative rearrangements in the set of possible rearrangements to compute the distance. The best previously known result for this problem is a 4.5-approximation using breakpoints. In this paper, we use an adaptation of the breakpoint graph, a structure used in the literature on genome rearrangements, to present a new lower bound for the distance and a 4-approximation algorithm. (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: | 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: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |