27 mar 2024
09:00 Defesa de Doutorado Integralmente a distância
Tema
Variações do Problema de Distância de Rearranjos
Aluno
Alexsandro Oliveira Alexandrino
Orientador / Docente
Zanoni Dias - Coorientador: Ulisses Martins Dias
Breve resumo
Considerando um par de genomas de organismos de espécies relacionadas, os problemas de distância de rearranjos têm como objetivo estimar quão distante um deles está em relação ao outro em termos de rearranjos de genomas, que são eventos mutacionais capazes de modificar o material genético ou a posição relativa de segmentos de um genoma. Considerando o Princípio da Máxima Parcimônia, o termo distância, ou ainda distância de rearranjos, é definido como o número mínimo de rearranjos de genomas necessários para transformar um genoma no outro.
Os primeiros trabalhos que estudaram a distância de rearranjos assumiram que os genomas comparados possuem o mesmo conjunto de genes (genomas balanceados) e, além disso, apenas a ordem relativa dos genes e suas orientações, quando conhecidas, são utilizadas na representação matemática dos genomas. Essas restrições implicam que é possível transformar um genoma em outro usando apenas rearranjos que não alteram a quantidade de material genético no genoma (rearranjos conservativos). Nesse caso, os genomas são representados como permutações, o que deu origem aos problemas de Ordenação de Permutações por Rearranjos. Os principais problemas de Ordenação de Permutações por Rearranjos consideram DCJs, reversões, transposições, ou a combinação de reversões e transposições, sendo que eles possuem complexidade conhecida. Além desses, foram estudados outros problemas que combinam transposições com um ou mais dos seguintes rearranjos: transposições inversas, revrevs e reversões. Apesar de existirem algoritmos de aproximação na literatura para esses problemas, as complexidades deles permaneciam em aberto. Um dos resultados desta tese é a prova de complexidade desses problemas que combinam transposições com transposições inversas, revrevs e reversões. Além disso, apresentamos um novo algoritmo de 1.375-aproximação para a Ordenação de Permutações por Transposições que possui melhor complexidade de tempo.
Com o avanço da área, novos trabalhos começaram a considerar genomas desbalanceados e a incorporar a distribuição dos tamanhos das regiões intergênicas. Ao considerar genomas desbalanceados, é necessário o uso de inserções e deleções para transformar um genoma em outro. Nesta tese, estudamos tanto o problema de Distância de Rearranjos em genomas desbalanceados considerando apenas a sequência de genes e suas orientações (quando conhecidas), quanto o problema de Distância de Rearranjos Intergênicos em genomas desbalanceados, que incorpora os tamanhos das regiões intergênicas na representação dos genomas, além do uso da sequência de genes e suas orientações (quando conhecidas). Apresentamos novas estruturas e conceitos para problemas que envolvem reversões, transposições e a combinação de reversões e transposições, que são usados em provas de complexidade e algoritmos de aproximação. Além disso, realizamos experimentos em genomas sintéticos e em genomas reais, evidenciando a aplicabilidade dos nossos algoritmos.
Banca examinadora
Titulares:
| Zanoni Dias | IC/UNICAMP |
| Marie-France Sagot | INRIA |
| Maria Emília Machado Telles Walter | CIC/UnB |
| Orlando Lee | IC/UNICAMP |
| Guilherme Pimentel Telles | IC/UNICAMP |
Suplentes:
| Fábio Luiz Usberti | IC/UNICAMP |
| Eduardo Candido Xavier | Mercado Livre |
| Luis Antonio Brasil Kowada | IC/UFF |