InfoBio TD Programmation dynamique

From silico.biotoul.fr

Revision as of 08:58, 22 February 2012

Il s'agit de programmer en perl l'algorithme de Needleman-Wunsch exploitant la programmation dynamique vu en cours.

Etant donné 2 séquences nucléiques ou protéiques, une matrice contenant le score du meilleur alignement est progressivement remplie.

Vous commencerez par programmer la méthode pour un alignement global sans brèche en utilisant un score de distance :

• identité = 0
• substitution = 1
• indel = 2

Ce score sera représenté par une matrice de substitution assez triviale pour les séquences nucléiques :

  - A T C G
- 0 2 2 2 2
A 2 0 1 1 1
T 2 1 0 1 1
C 2 1 1 0 1
G 2 1 1 1 0

Le fait d'utiliser une telle matrice rendra le programme générique en terme du type de séquences alignées, qu'elles soient nucléiques ou protéiques. Pour les séquences protéiques, l'utilisateur pourra passez quelle matrice utiliser en paramètres, par exemple PAM120 ou BLOSUM62, mais vous commencerez par des séquences nucléiques.

Une fois la matrice de programmation dynamique remplie, faites-la afficher en indiquant le(s) chemin(s) correspondant au(x) meilleur(s) alignement(s). Par exemple, pour les séquences TTGTG et ACTTGCAG :

           A      C      T      T      G      C      A      G 
    0   -  2   -  4      6      8     10     12     14     16 
                      \                                       
 T  2      1      3      4      6      8     10     12     14 
                             \                                
 T  4      3      2      3      4      6      8     10     12 
                                    \                         
 G  6      5      4      3      4      4   -  6      8     10 
                                           \      \           
 T  8      7      6      4      3      5      5   -  7      9 
                                                         \    
 G 10      9      8      6      5      3      5      6      7 

Faites ensuite afficher le(s) meilleur(s) alignement(s), par exemple :

--TTG-TG
ACTTGCAG

--TTGT-G
ACTTGCAG