Grafos de sequencias de DNA

Este trabalho esta relacionado a Biologia Computacional, uma area da Ciencia da Computacao cuja existencia e motivada pela busca de metodos computacionais que resolvam ou ajudem a resolver problemas de origem biologica. Esta ciencia tem sido largamente utilizada no âmbito da genetica, contribuindo essencialmente no sequenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma familia de problemas denominada Minimum Contig Problems (MCP) [4], que e um modelo teorico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhanca com um problema de grafos denominado Cobertura de Vertices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentacao de provas formais da NP-dificuldade dos problemas de MCP. A partir dai, complementamos o nosso trabalho propondo um algoritmo de aproximacao para instâncias restritas de cada problema de MCP Abstract