Defesa de Doutorado de André Rodrigues Oliveira

Título do Trabalho
Modelos Restritos e Intergênicos para a Ordenação por Reversões e Transposições
Candidato(a)
André Rodrigues Oliveira
Nível
Doutorado
Data
Add to Calender 2019-12-09 00:00:00 2019-12-09 00:00:00 Defesa de Doutorado de André Rodrigues Oliveira Modelos Restritos e Intergênicos para a Ordenação por Reversões e Transposições Auditório 1 do IC 3 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14:00
Local
Auditório 1 do IC 3
Orientador(a)
Zanoni Dias
Banca Examinadora

* Titulares

Unidade/Instituição

Zanoni Dias

IC/UNICAMP

Carla Negri Lintzmayer

CMCC/UFABC

Maria Emília Machado Telles Walter

CIC/UnB

Orlando Lee

IC/UNICAMP

Guilherme Pimentel Telles

IC/UNICAMP

 

* Suplentes

Unidade/Instituição

Rafael Crivellari Saliba Schouery

IC/UNICAMP

Eduardo Candido Xavier

IC/UNICAMP

Nalvo Franco de Almeida Junior

FACOM/UFMS

Resumo

Rearranjos de Genomas são eventos que afetam longos trechos de um genoma durante a evolução. Dentre os rearranjos mais estudados temos a reversão, que inverte a ordem e a orientação de um bloco consecutivo de genes, e a transposição, que troca a ordem relativa de dois blocos adjacentes.

Modelos matemáticos vem sendo utilizados para estimar a distância evolutiva entre diferentes genomas por rearranjos de genomas. A representação de um genoma se dá, na maioria das vezes, pela atribuição de um número único para cada gene e, ao supor que não existem genes repetidos. Esta representação pode ser vista como uma permutação. Supondo que os dois genomas a ser comparados compartilham o mesmo conjunto de genes, calcular a distância evolutiva entre eles se transforma no problema de encontrar o ménor número de rearranjos necessários que transforma uma permutação em outra, o que pode ser simplificado ainda para o problema da ordenação de permutações.

Uma das variações deste problema considera que cada rearranjo pode afetar apenas um pequeno número de genes, também conhecidos como rearranjos curtos e super curtos. Neste contexto, uma de nossas contribuições é mostrar que o único problema cuja complexidade era desconhecida envolvendo reversões super curtas e transposições super curtas possui um algoritmo polinomial.

Além disso, a grande maioria dos problemas existentes na literatura até o momento focaram apenas na ordem relativa dos genes de um genoma, desconsiderando outras características importantes existentes no genoma. Recentemente, pesquisadores mostraram que considerar as regiões existentes entre cada par de genes, chamadas de regiões intergênicas, pode resultar em melhores estimadores de distância em dados reais. Neste trabalho investigamos a incorporação das regiões intergênicas em modelos já existentes para reversões e transposições, tanto na abordagem sem restrições como na abordagem que considera apenas rearranjos super curtos, onde investigamos diversos algoritmos de aproximação para problemas que são NP-difíceis ou possuem complexidade desconhecida.