Texto completo
| |
| Autor(es): |
Marília Dias Vieira Braga
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2000-11-27 |
| Membros da banca: |
João Meidanis;
Eduardo Sany Laber;
Cid Carvalho de Souza
|
| Orientador: | João Meidanis |
| Resumo | |
Este trabalho está relacionado à Biologia Computacional, uma área da Ciência da Computação cuja existência é motivada pela busca de métodos computacionais que resolvam ou ajudem a resolver problemas de origem biológica. Esta ciência tem sido largamente utilizada no âmbito da genética, contribuindo essencialmente no seqüenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma família de problemas denominada Minimum Contig Problems (MCP) [4], que é um modelo teórico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhança com um problema de grafos denominado Cobertura de Vértices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentação de provas formais da NP-dificuldade dos problemas de MCP. A partir daí, complementamos o nosso trabalho propondo um algoritmo de aproximação para instâncias restritas de cada problema de MCP. (AU) | |
| Processo FAPESP: | 97/11629-2 - Grafos de sequencias de dna. |
| Beneficiário: | Marilia Dias Vieira Braga |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |