Defesa de Mestrado de Alexsandro Oliveira Alexandrino

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

* Titulares

Unidade/Instituição

Zanoni Dias

IC/UNICAMP

Mário César San Felice

DC/UFSCar

Rafael Crivellari Saliba Schouery

IC/UNICAMP

* Suplentes

Unidade/Instituição

Ulisses Martins Dias

FT/UNICAMP

Pedro Henrique Del Bianco Hokama

IMC/UNIFEI

Resumo

Calcular a distância evolucionária entre espécies é um problema importante da área de Biologia Computacional. Em várias abordagens, o cálculo dessa distância considera apenas rearranjos de genomas, os quais são conjuntos de mutações que alteram grandes trechos do genoma de um organismo. Assumindo que o genoma não possui genes duplicados, podemos representá-los como permutações de números inteiros, em que cada elemento corresponde a um bloco conservado (região de alta similaridade entre os genomas comparados) e o sinal de cada elemento corresponde a orientação desse bloco. Ao usar permutações, o problema de transformar um genoma em outro é equivalente ao da Ordenação de Permutações por Operações de Rearranjo. A abordagem tradicional desse problema considera que todas as operações tem o mesmo custo e, assim, o objetivo é encontrar uma sequência mínima de operações que ordene a permutação. Entretanto, estudos indicam que algumas operações de rearranjo tem maior probabilidade de acontecer do que outras, fazendo com que abordagens em que operações possuem custos diferentes sejam mais realistas. Nas abordagens ponderadas, o objetivo é encontrar a sequência que ordena a permutação, tal que a soma dos custos dos rearranjos dessa sequência seja mínimo.

Neste trabalho, apresentamos algoritmos de aproximação para duas novas variações dos problemas da Ordenação de Permutações por Operações Ponderadas. A primeira variação utiliza uma função de custo correspondente à quantidade de fragmentações que a operação causa na permutação. A segunda variação utiliza uma função de custo proporcional ao tamanho da operação, além de adicionar a restrição de que as operações sejam curtas. Para cada uma das variações, foram considerados cinco problemas com os seguintes modelos de rearranjo: reversões sem sinais, transposições, reversões sem sinais e tranposições, reversões com sinais, e reversões com sinais e transposições.

Considerando os problemas da Ordenação de Permutações por Operações Ponderadas pelo Número de Fragmentações, apresentamos uma análise da relação entre os problemas não ponderados e essa variação, dois algoritmos de 2-aproximação para cada um dos cinco modelos de rearranjo, resultados experimentais desses algoritmos e limitantes inferiores e superiores para o diâmetro desses problemas. Além disso, apresentamos propriedades sobre permutações simples e um algoritmo de 1.5-aproximação assintótica para essa classe de permutações considerando reversões com sinais e/ou transposições.

Para os problemas da Ordenação de Permutações por Operações Curtas Ponderadas pelo Tamanho, apresentamos uma análise da relação entre os problemas não ponderados e essa variação, algoritmos de aproximação com fator constante para cada um dos cinco modelos de rearranjo e resultados experimentais desses algoritmos. Além disso, fizemos uma análise do fator de aproximação dos algoritmos quando a função de custo é igual a l ^ alpha, onde l é o tamanho da operação e alpha > 1 é uma constante.