Busca avançada
Ano de início
Entree


Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations

Texto completo
Autor(es):
Alexandrino, Alexsandro Oliveira ; Lintzmayer, Carla Negri ; Dias, Zanoni ; Jansson, J ; MartinVide, C ; VegaRodriguez, MA
Número total de Autores: 6
Tipo de documento: Artigo Científico
Fonte: ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018); v. 10849, p. 12-pg., 2018-01-01.
Resumo

Rearrangements are mutations that affect large portions of a genome. When comparing two genomes, one wants to find a sequence of rearrangements that transforms one into another. When we use permutations to represent the genomes, this reduces to the problem of sorting a permutation using some sequence of rearrangements. The traditional approach is to find a sequence of minimum length. However, some studies show that some rearrangements are more likely to disturb an individual, and so a weighted approach is closer to the real evolutionary process. Most weighted approaches consider that the cost of a rearrangement can be related to its type or to the number of elements affected by it. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for 5 versions of the fragmentation-weighted problem involving reversals and transpositions events. (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: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
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
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