MAC 5726 – Biologia Computacional

Segunda lista de exercícios – Entrega 3 de novembro de 1999

Exercício 1 Na montagem de fragmentos de DNA, dados dois fragmentos s e t, de comprimentos m e n, precisamos encontrar o maior sufixo de s com boa similaridade com um prefixo de t. Usando o algoritmo de programação dinâmica, isso pode ser feito em tempo O(mn). Mostre que se, ao invés de boa similaridade, quisermos encontrar o maior sufixo de s que é prefixo de t, o problema pode ser resolvido em tempo O(m + n).

Exercício 2 O problema de decisão associado ao problema dos 1’s consecutivos é o seguinte. Dada uma matriz binária M e um inteiro k, decidir se existe uma permutação das colunas de M tal que o número de blocos de 1’s nas linhas é menor ou igual a k. Prove que esse problema é NP-completo. Dica: redução do problema Caminho Hamiltoniano.

Exercício 3 Seja M uma matriz binária, onde colunas representam características e linhas representam táxons. Assuma que característica com valor 0 é ancestral de característica com valor 1. Prove ou dê um contra-exemplo para cada uma das duas afirmações abaixo. Se M admite uma filogenia perfeita, então M tem a propriedade dos 1’s consecutivos para as colunas. Se M tem a propriedade dos 1’s consecutivos para as colunas, então M admite uma filogenia perfeita.