Grafos de sequencias de DNA

AUTOR(ES)

Marilia Dias Vieira Braga

DATA DE PUBLICAÇÃO

2000

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

ASSUNTO(S)

algoritmos teoria dos grafos

Documentos Relacionados

• Analise de sequencias de DNA cloropastico de especies do genero Capsicum.
• Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos
• Particionamento de grafos de aplicações e mapeamento em grafos de arquiteturas heterogêneas
• Analise estatistica de polimorfismo molecular em sequencias de DNA utilizando informações filogeneticas
• Frequência de sequências de DNA do vírus Epstein-Barr em gliomas humanos