Devoir 1

Date limite de remise: le 29 janvier 2003, 13:20. Vous pouvez remettre votre travail en personne au cours.

1. Distance d'édition entre deux séquences (10 points)

Calculez la distance d'édition et un alignement global optimal qui y correspond entre les deux séquences ATCAACTTTA et AAGAATGATT. Est-ce qu'il y a plusieurs alignements qui correspondent à la même distance? Montrez les détails de votre travail, surtout le tableau de PD rempli.

2. Alignement ADN-protéine (10 points)

Soit S une séquence d'ADN et T une séquence de protéine. On veut aligner les triplets de S aux acides aminés de T à l'aide des scores de similarité et programmation dynamique. Les scores s() sont définis par une matrice M de coût de substitutions entre acides aminés (p.e. PAM) et des coûts fixés pour des espaces: dN pour un espace en S et dP pour un espace en T. On a donc s(b, -)=-dP, s(-, a)=-dN, et s(b1b2b3, a) =M[g(b1,b2,b3), a] où g() denote le code génétique. Donnez la définition formelle de l'alignement (global) optimal. Donnez les récurrences pour une solution par programmation dynamique et démontrez que votre récurrence est corrrecte. Décrivez un algorithme de PD basé sur la récurrence. Quel est le temps de calcul de votre algorithm?

3. Combien d'alignements? (12 points)

Après avoir rempli le tableau de PD pour trouver la distance d'édition entre deux séquences, on peut retrouver la solution optimale en retraçant les pas de la procédure. Donnez un algorithme efficace pour compter le nombre de solutions optimales, c-à-d solutions avec le même nombre minimal d'opérations d'édition. Quel est le temps de calcul de votre algorithm?

4. Et si on aligne les alignements? (8 points)

Supposons qu'on a aligné deux séquences S et T. Soit S' et T' les séquences dans un alignement global optimal: S' et obtenu de S par insertion de signes d'espace - comme indiqué par l'alignement. Exemple: si S=AACT, T=AATG, et on a l'alignement suivant.

AACT-
AA-TG

Alors S'=AACT- et T'=AA-TG. Quel est le résultat de l'alignement de S' et T' pour des séquencesS et T en général? Est-ce que c'est le même que l'alignement de S et T?

5. Est-ce que je ressemble à moi-même? (10 points)

On veut trouver des régions similaires dans la méme séquence. Par exemple, si on a S=AGTTATTCAAATTACTCGGAG, S[3..8] et S[12..17] sont presque identique: TTATTC et TTACTC. Pour trouver des régions de similarité maximale, on peut utiliser l'algorithme de Smith-Waterman: on compare simplement S à S. Hélas, la région de similarité maximale sera toute la séquence. Même si on considère un case (i,j) dans le tableau, le meilleur alignement qui y finit commence probablement sur la diagonale du tableau. Modifiez l'algorithme original pour éviter ce problème. Est-ce que votre solution peut produire des régions chevauchantes?