| Texto completo | |
| Autor(es): |
Alexandrino, Alexsandro Oliveira
;
Oliveira, Andre Rodrigues
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Ulisses
;
Dias, Zanoni
;
Bansal, MS
;
Cai, Z
;
Mangul, S
Número total de Autores: 9
|
| Tipo de documento: | Artigo Científico |
| Fonte: | BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2022; v. 13760, p. 14-pg., 2022-01-01. |
| Resumo | |
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) | |
| Processo FAPESP: | 19/27331-3 - Problemas de ordenação por rearranjos de genomas |
| Beneficiário: | André Rodrigues Oliveira |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |