Conexão de Saberes e Mundialização
19 a 24 de outubro de 2015
Trabalho 3665
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Teoria e Tecnologia da informação |
| Setor | Departamento de Informática |
| Bolsa | PROBIC/FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Laís França Baumgratz |
| Orientador | LUCIANA BRUGIOLO GONCALVES |
| Título | Problemas em Grafos com Cores nas Arestas para Aplicações em Biologia Computacional |
| Resumo | Nos últimos anos, um grande número de aplicações vêm sendo modelado como problemas em grafos e dígrafos coloridos. Em particular na área de Biologia Molecular Computacional, tais problemas são frequentemente modelados por meio de grafos coloridos, ou seja, grafos em que cores são associadas a arestas ou vértices. A principal dificuldade dos problemas desta área é a grande quantidade de dados envolvida. Muitos problemas práticos relevantes são altamente combinatórios, sendo fundamental o desenvolvimento de técnicas eficientes para a resolução dos mesmos em tempo viável. Neste trabalho foi abordado, em especial, o Problema da Sequência Mais Próxima – PSMP (Closest String Problem) que foi provado estar na classe NP-difícil. O PSMP consiste em, dado um conjunto S = {s1, s2, ..., sm} de sequências de tamanho n, sobre o alfabeto Σ, deseja-se encontrar uma sequência sH de tamanho n que minimize d, onde, para cada sequência si em S, dist(sH, si) ≤ d, para i = 1..m. Sendo dist(.) uma função que denota a distância entre duas sequências de mesmo tamanho. Uma aplicação para este trabalho envolve problemas de Biologia Molecular, onde deseja-se comparar e encontrar regiões comuns ou que sejam próximas a um conjunto de sequências de DNA, RNA ou proteínas. Outro problema com apelo prático para a área de Biologia é a descoberta de padrões comuns para um dado conjunto de entradas de sequências de DNA. Quando se deseja produzir uma droga genética com uma estrutura similar a um conjunto de sequências de RNA, é comum a necessidade de descoberta de padrões. O objetivo é propor métodos heurísticos para geração de soluções aproximadas de boa qualidade para o PSMP. Para tanto, foram desenvolvidas heurísticas baseadas em algoritmos evolutivos, como Algoritmos Genéticos, combinados com estratégias de busca local e reconexão de caminhos. Os resultados obtidos são comparados com aqueles obtidos por uma heurística GRASP-VNS (Lyra, 2012) e com resultados obtidos com a utilização do algoritmo evolutivo proposto por Soares (2013). |
| Palavras-chave | Biologia molecular, Grafos com cores nas arestas, Otimização Combinatória |
| Forma de apresentação..... | Painel |