| Texto completo | |
| Autor(es): |
Oliveira, Andre Rodrigues
;
Brito, Klairton Lima
;
Dias, Zanoni
;
Dias, Ulisses
;
Alves, R
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018; v. 11228, p. 12-pg., 2018-01-01. |
| Resumo | |
Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem in two variants depending on whether we model genomes as signed or unsigned permutations. Here, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present one algorithm with an approximation factor of 2 for both signed or unsigned permutations, and one algorithm with an approximation factor of 5/3 for signed permutations. We also analyze the behavior of the 5/3-approximation algorithm with different weights for reversals and transpositions. (AU) | |
| Processo FAPESP: | 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade |
| Beneficiário: | Anderson de Rezende Rocha |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| 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 |
| Processo FAPESP: | 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo |
| Beneficiário: | Sandra Eliza Fontes de Avila |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Processo FAPESP: | 17/16871-1 - Problemas de ordenação de permutações por operações ponderadas pelo número de fragmentações |
| Beneficiário: | Alexsandro Oliveira Alexandrino |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |