Paralelismo e Heurísticas para o problema da mediana por swap

Vol 55, 2023 - 160960
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O problema da mediana em Rearranjo de Genomas consiste em, conhecendo a métrica entre permutações, ao receber três permutações de entrada, determinar uma permutação-solução s que minimiza a soma das distâncias entre s e cada uma das três permutações da entrada.
A métrica entre permutações está associada a eventos mutacionais entre genomas; assim, o conhecimento da mediana determina uma ancestralidade comum relativamente próxima das espécies representadas pelas permutações de entrada.
Algumas métricas foram consideradas na literatura, desde aquelas baseadas em operações mais limitadas, como breakpoints, até aquelas baseadas em operações em sequências mais gerais que permutações, como double-cut-and-join ou single-cut-or-join em DNAs.
Trabalhamos com o problema da mediana utilizando como métrica o swap entre permutações.
A complexidade computacional deste problema ainda está em aberto, e para lidar com este problema desenvolvemos heurísticas, determinamos condições suficientes para soluções e avaliamos a qualidade das heurísticas comparando com os algoritmos de força bruta sequencial e paralelo.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal Fluminense
Eixo Temático
  • 14. OC – Otimização Combinatória
Palavras-chave
Rearranjo de genomas; Mediana; Swap