| Texto completo | |
| Autor(es): |
Oliveira, Andre Rodrigues
;
Alexandrino, Alexsandro Oliveira
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Ulisses
;
Dias, Zanoni
;
Jin, L
;
Durand, D
Número total de Autores: 8
|
| Tipo de documento: | Artigo Científico |
| Fonte: | COMPARATIVE GENOMICS (RECOMB-CG 2022); v. 13234, p. 16-pg., 2022-01-01. |
| Resumo | |
Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-Cut rearrangement which cuts a permutation (or a string) at k >= 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations, and a 1.5-approximation algorithm for the specific case k = 4. (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 |