09 dez 2019
14:00 Auditório 1
Tema
Modelos Restritos e Intergênicos para a Ordenação por Reversões e Transposições
Aluno
André Rodrigues Oliveira
Orientador / Docente
Zanoni Dias
Breve 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.