Texto completo
| |
| Autor(es): |
Carla Negri Lintzmayer
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2016-12-15 |
| Membros da banca: |
Zanoni Dias;
Maria Emilia Machado Telles Walter;
Cristina Gomes Fernandes;
Eduardo Candido Xavier;
Fábio Luiz Usberti
|
| Orientador: | Zanoni Dias |
| Resumo | |
O Problema das Panquecas tem como objetivo ordenar uma pilha de panquecas que possuem tamanhos distintos realizando o menor número possível de operações. A operação permitida é chamada reversão de prefixo e, quando aplicada, inverte o topo da pilha de panquecas. Tal problema é interessante do ponto de vista combinatório por si só, mas ele também possui algumas aplicações em biologia computacional. Dados dois genomas que compartilham o mesmo número de genes, e assumindo que cada gene aparece apenas uma vez por genoma, podemos representá-los como permutações (pilhas de panquecas também são representadas por permutações). Então, podemos comparar os genomas tentando descobrir como um foi transformado no outro por meio da aplicação de rearranjos de genoma, que são eventos de mutação de grande escala. Reversões e transposições são os tipos mais comumente estudados de rearranjo de genomas e uma reversão de prefixo (ou transposição de prefixo) é um tipo de reversão (ou transposição) que é restrita ao início da permutação. Quando o rearranjo é restrito ao final da permutação, dizemos que ele é um rearranjo de sufixo. Um problema de ordenação de permutações por rearranjos é, portanto, o problema de encontrar uma sequência de rearranjos de custo mínimo que ordene a permutação dada. A abordagem tradicional considera que todos os rearranjos têm o mesmo custo unitário, de forma que o objetivo é tentar encontrar o menor número de rearranjos necessários para ordenar a permutação. Vários esforços foram feitos nos últimos anos considerando essa abordagem. Por outro lado, um rearranjo muito longo (que na verdade é uma mutação) tem mais probabilidade de perturbar o organismo. Portanto, pesos baseados no comprimento do segmento envolvido podem ter um papel importante no processo evolutivo. Dizemos que essa abordagem é ponderada por comprimento e o objetivo nela é tentar encontrar uma sequência de rearranjos cujo custo total (que é a soma do custo de cada rearranjo, que por sua vez depende de seu comprimento) seja mínimo. Nessa tese nós apresentamos os primeiros resultados que envolvem problemas de ordenação de permutações por reversões e transposições de prefixo e sufixo considerando ambas abordagens tradicional e ponderada por comprimento. Na abordagem tradicional, consideramos um total de 10 problemas e desenvolvemos novos resultados para 6 deles. Na abordagem ponderada por comprimento, consideramos um total de 13 problemas e desenvolvemos novos resultados para todos eles (AU) | |
| Processo FAPESP: | 13/01172-0 - O problema da ordenação de permutações usando operações de prefixo e sufixo |
| Beneficiário: | Carla Negri Lintzmayer |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |