Jean-Stéphane Varré

Thème 1 : comparer des séquences

Thème 2 : rechercher des séquences similaires dans une banque

Thème 3 : comparer des génomes

Support
En TP : la recherche de répétitions avec l'arbre des suffixes

Pour programmer ces exercices, on pourra utiliser :

En Java : la classe représentant l'arbre des suffixes disponible ici qu'on pourra modifier à souhait,
En Python : le package pointé par Eric ici,
En C : les sources C du package ci-dessus qui ont été wrappées pour être utilisées en Python.

On appelle paire maximale à droite dans une chaîne de caractères S une paire de sous-chaînes u et v telles que le caractère immédiatement à droite de u est différent du caractère immédiatement à droite de v. Par exemple dans bananas on a quatre paires maximales à droite : ana (1,3), na (2,4), a (1,5), a (3,5)

Question 1. Ecrire un programme qui utilise un arbre des suffixes pour extraire toutes les paires maximales à droite d'une chaîne de caractères S. On affichera la chaîne répétée et le nombre de répétions. Par exemple a : 2, na : 1, ana : 1.

Sous-question: que représente la concaténation des étiquettes des arêtes menant de la racine à une feuille ?
Sous-question: que représente la concaténation des étiquettes des arêtes menant de la racine à un noeud ?

On appelle répétition maximale dans une chaîne de caractères S une paire maximale à droite ne pouvant être étendue à gauche. Par exemple dans bananas on a deux paires maximales : ana (1,3), a (1,5)

Question 2. Ecrire un programme qui utilise un arbre des suffixes pour extraire toutes les répétitions maximales d'une chaîne de caractères S. On affichera la chaîne répétée et ses positions.

Sous question: que signifie ne pas pourvoir étendre à gauche dans la chaîne ?
Sous-question: comment s'exprime cette proprité dans l'arbre des suffixes ?
Sous question: que signifie ne pas pourvoir étendre à gauche dans l'arbre des suffixes ?

On appelle répétition maximale en tandem dans une chaîne de caractères S une répétition maximale telle que la première occurrence se termine là où la seoncde commence. Par exemple dans bananas on a une répétition en tandem : na.

Question 3. Ecrire un programme qui utilise un arbre des suffixes pour extraire toutes les répétitions maximales en tandem d'une chaîne de caractères S. On affichera la chaîne répétée et sa position.

On pourra s'aider de ce qui est décrit dans cet article où ce que nous recherchons est défini comme des "branching tandem repeat".

Thème 4 : recherche de motifs

Support de cours
En TP: la recherche de motifs avec des profile HMM.
On souhaite construire un profile HMM pour la prédiction du motif doigt de zinc C2H2 (documentation Prosite).

On va partir d'un alignement de motifs doigt de zinc validé, construire un profile HMM et tester la validité du modèle établi sur des séquences possédant un motif doigt de zinc et sur des séquences ne possédant pas de motif doigt de zinc.

A partir de ces tests, on pourra calculer le nombre de vrais positifs (VP), de faux négatifs (FN), de vrais négatifs (VN) et de faux positifs (FP). Ces quantités permettront alors de calculer la senseibilité () et la spécificité () du modèle.

Comme le modèle produit une probabilité, il faudra adopter un seuil permettant de choisir si oui ou non on considère qu'une séquence contient un motif doigt de zinc. Le calcul de la sensibilité et de la spécificité pour différents seuils (de 0 à 1) permettra d'établir une courbe ROC qui trace le rapport en spécificité et sensibilité (voir cet article).

Enfin, nous pourrons tester différents modèles, et donc différentes courbes ROC, et choisir quel est celui qui donne les meilleurs résultats.

Les données utilisées seront les suivantes:
- les séquences doigt de zinc à modéliser : ZINC.fsa
- les séquences test qui ne sont pas des doigts de zinc : nonZINC.fsa
Le travail à réaliser est le suivant. Vous devrez rendre les programmes, un README indiquant comment lancer les tests et les courbes ROC.
1. Construire un programme qui étant donné un alignement multiple calcule les probabilité de transition et d'émission tel que discuté en cours. On produire un fichier qui indiquera ces valeurs dont le format sera le suivant. Chaque ligne décrit un état du modèle avec la syntaxe :
  - numéro de l'état
  - type de l'état : B=begin, E=end, M=match, I=insert, D=delete, S=silent
  - nombre de transitions
  - suite de couples de transitions sous la forme numéro état:probabilité de transition
  - suite de couples lettre:probabilité d'émission (toutes les lettres de l'alphabet doivent apparaître, même celles de probabilité d'émission nulle)
  Par exemple (sur l'ADN): 0 B 2 1:0.3 2:0.7 A:0.1 T:0.2 C:0.7 G:0.0 décrit l'état numéro 0, qui est l'état de départ, qui possède 2 transitions, l'une vers l'état 1 avec une probabilité de 0.3 et l'autre vers l'état 2 avec une probabilité de 0.7. Cet état à des probabilités d'émission respective pour A, T, C et G de 0.1, 0.2, 0.7 et 0.
2. Construire un programme qui étant donné un HMM et une séquence produira la position à laquelle la probabilité la plus grande est atteinte (ainsi que la probabilité associée). Remarquez qu'un HMM n'est qu'un graphe et qu'il peut être simplement et rapidement modélisé par des tableaux associatifs.
3. Construire un HMM en sélectionnant 10% de l'échantillon ZINC, puis calculer la sensibilité et la spécificité du modèle sur les jeux ZINC et nonZINC pour des seuils de 0.1 à 1.0 par pas de 0.1. Etablir la courbe ROC correspondante.
4. Recommencer en sélectionnant 20, puis 30, puis 40, puis 50% de l'échantillon ZINC. Discuter des résultats.