Devoir 2

Date limite de remise: mercredi le 12 février 2003, 18:00. Vous pouvez remettre votre travail en personne au cours ou plus tard dans mon bureau (3253).

Pour chacun dex exercices suivants où un algorithme est demandé, analysez le temps et l'espace de calcul de votre algorithme.

1. Interprétation probabiliste d'un alignement (15 points)

Soit S1 et S2 deux séquences évoluées d'une séquence S0 ancestrale inconnue. L'évolution de S0 est modelé de la façcon suivante. Les séquences S1 et S2 ont évolué indépendemmant, selon les probabilités de mutation p=identité, q=substitution, ri=insertion, rd=suppression. Considérez l'alignement multiple des trois séquences qui correspond aux mutations de S0 qui mènent à S1 et S2. La probabilité de l'alignement est égale au produit des probabilités des mutations (c-à-d les évenements de mutation sont indépendants). Exemple:

S0 AC-GG
S1 -C-GT
S2 ACTGG

La probabilité de cet alignement est égale à (prd)(p2)(ri)(p2)(pq).

2. Alignement de profiles (15 points)

Définissez le concept d'alignement global de deux profiles et décrivez un algorithme qui trouve l'alignement optimal de deux profiles. Un profile est défini par la matrice de probabilités qui donne la probabilité d'avoir caractère a dans colonne j pour chaque a et j. Utilisez un système de pondération affine de trous. Vous devrez besoin de définir la notion de similarité entre deux distributions sur l'alphabet pour comparer deux colonnes des profiles: choisissez une notion sensible de votre préférence. (Par exemple, si pi : i=1,...,m donnent les probabilités des caractères ai de l'alphabet, et qi donnent une autre distribution sur le même alphabet, alors la somme des |pi-qi|, où |x| est la valeur absolue de x, mesure la distance entre les deux distributions.)

3. Le fils de Viterbi (20 points)

Soit M un modèle de Markov caché et s une séquence. Décrivez un algorithme qui calcule le deuxième chemin plus probable sur les états de M qui génère s. Analysez le temps de calcul de votre algorithme dans les deux cas [a] où M est un HMM général, et [b] où M est un HMM de profile.