O problema de ordenação de permutações usando operações de prefixo e sufixo
O problema da ordenação de permutações usando operações de prefixo e sufixo
Ordenação de permutações por reversões de prefixo e reversões de sufixo
| Texto completo | |
| Autor(es): |
Oliveira, Andre Rodrigues
;
Jean, Geraldine
;
Fertin, Guillaume
;
Brito, Klairton Lima
;
Dias, Ulisses
;
Dias, Zanoni
;
MartinVide, C
;
VegaRodriguez, MA
;
Wheeler, T
Número total de Autores: 9
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2020); v. 12099, p. 13-pg., 2020-01-01. |
| Resumo | |
Genome Rearrangements affect large stretches of genomes during evolution. One of the most studied genome rearrangement is the transposition, which occurs when a sequence of genes is moved to another position inside the genome. Mathematical models have been used to estimate the evolutionary distance between two different genomes based on genome rearrangements. However, many of these models have focused only on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering existing regions between each pair of genes, called intergenic regions, can enhance the distance estimation in realistic data. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting Permutations by Intergenic Transpositions (SbIT). We show that this problem is NP-hard and propose a 3.5-approximation algorithm for it. (AU) | |
| 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/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: | 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 |