Resumo
Motivados por problemas biológicos, decidimos estudar certos grafos construídos a partir de seqüências de DNA e problemas NP-difíceis relacionados a eles. Alguns destes problemas são NP-difíceis para alfabetos grandes, sendo sua complexidade desconhecida no caso de um alfabeto de quatro letras (como é o caso de seqüências de DNA). Outros são NP-difíceis para qualquer alfabeto com pelo men…