Defesa de Mestrado de Guilherme Henrique Santos Miranda

Título do Trabalho
Ordenação de Permutações por Operações de Tamanho Limitado
Candidato(a)
Guilherme Henrique Santos Miranda
Nível
Mestrado
Data
Add to Calender 2019-02-21 00:00:00 2019-02-21 00:00:00 Defesa de Mestrado de Guilherme Henrique Santos Miranda Ordenação de Permutações por Operações de Tamanho Limitado Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Sala 85 IC 2
Orientador(a)
Zanoni Dias
Banca Examinadora

* Titulares

Unidade/Instituição

Zanoni Dias

IC/UNICAMP

Pedro Henrique Del Bianco Hokama

IMC/UNIFEI

Orlando Lee

IC/UNICAMP

* Suplentes

Unidade/Instituição

Ulisses Martins Dias

FT/UNICAMP

Mário César San Felice

DC/UFSCar

Resumo

Estimar a distância evolucionária entre genomas de dois organismos é uma tarefa desafi-
adora para Biologia Computacional. Uma das formas mais bem aceitas de estimar essa
distância é considerar o tamanho da menor sequência de eventos de rearranjos necessá-
rios para transformar um genoma em outro, o que caracteriza o problema de distância
de rearranjo. Diversos eventos de rearranjos podem ser considerados e, dentre os mais
estudados, estão os rearranjos de reversão, que revertem um trecho de um genoma, e os de
transposição, que trocam as posições de dois trechos adjacentes de um genoma. Compu-
tacionalmente, genomas podem ser representados como permutações de números inteiros
e, com isso, o problema pode ser reduzido ao problema de calcular o número mínimo de
operações (rearranjos) necessárias para transformar uma permutação na outra.
Dado um valor λ, uma operação é chamada de λ-operação se a mesma envolve no
máximo λ elementos da permutação e uma permutação é chamada de λ-permutação se
todos seus elementos estão a menos do que λ posições de distância de suas posições corretas
na permutação ordenada. Desta forma, para os problemas de ordenação de permutações
com e/ou sem sinais por reversões, por transposições, e por reversões e transposições,
consideramos duas novas variações: (i) o problema de Ordenação de Permutações por
λ-Operações, e (ii) o problema de Ordenação de λ-Permutações por λ-Operações, que
possui a restrição adicional de que λ-operações aplicadas sobre uma λ-permutação deve
gerar outra λ-permutação como resultado.
Para (i), esta dissertação apresenta algoritmos com fatores de aproximação baseados
no tamanho da permutação e/ou em λ, que estão divididos entre os que são melhores
para valores grandes e pequenos de λ. Para (ii), apresentamos algoritmos com fatores de
aproximação O(λ²), O(λ) e O(1), e limitantes inferiores e superiores sobre o número de
λ-permutações existentes. Além disso, para ambas as classes de problemas, são apresen-
tados resultados experimentais que comparam como os algoritmos se comportam numa
perspectiva prática.