IMPORTANT NOTICE: electrical maintenance in the Annotathon server room on Monday December 11th 2017 from 18:00 to 22:00 (Paris time, also known as Central European Summer Time GMT+1H) means no annotation will be possible during this downtime!

Forum "Alignement multiple: CLUSTALW"

Thread subject: Faute dans le cours matrice de programmation dynamique. Chapitre 2

[ Return to forums ]
Faute dans le cours matrice de programmation dynamique. Chapitre 2
ClaraSophie
14 May 2017 15:16
Non evaluated contribution

Bonjour à tous, 

Je révise le cours de bio-info et j'ai une grosse difficultée a essayer de faire une matrice de programmation dynamique toute seule.

Celle donnée dans le cours à la page 9 me semble fausse ou elle a un probleme, c'est au niveau de la colonne 7 et de la ligne 4 avec les deux C qui se suivent, il y a une flèche dans ce sens -> qui ne devrait pas y etre.  Est ce que quelqu'un pourrait m'aider ? 

Merci d'avance 

B_Wirth_17
14 May 2017 17:37
Game master

Bonjour,

je viens de regarder rapidement, il n'y a pas de souci, la flèche horizontale doit bien y être.

Vous avez 3 chemins différents possibles pour accéder à une cellule. Il faut passer en revue ces 3 chemins possibles pour savoir lequel ou lesquels on retient.

On peut retenir plusieurs chemins s'ils donnent le même score dans la cellule d'arrivée, ce qui est le cas dans l'exemple que vous citez :

- si on vient par la diagonale : C s'aligne avec C, ces résidus sont identiques, donc 6+0 = 6

- si on vient par la verticale : on introduirait un indel, donc 8+2 = 10, valeur plus élevée que 6, donc chemin non retenu.

- si on vient par l'horizontale : on introduirait un indel, donc 4+2 = 6

==> On retient la valeur la plus faible (car score de distance), or vous obtenez 2 fois la valeur de 6, donc on retient les 2 chemins permettant d'obtenir ce score de 6.

Bon Travail,

BW

ClaraSophie
14 May 2017 19:44
Non evaluated contribution

Oui je ne comprends juste pas pourquoi à l'horizontal on introduirait un indel justement. Il n'y a pas de tiret entre les C indiquant un gap ou un indel.

Merci d'avance 

 

B_Wirth_17
15 May 2017 10:02
Game master

Vous avez deux séquences que vous voulez aligner. Au départ, les séquences ne contiennent ni tiret, ni indel, ni trou. C'est le programme d'alignement qui introduit les indels pour pouvoir aligner au mieux les deux séquences entre elles, dans le but d'obtenir un alignement optimal.

Le but de la matrice de programmation dynamique est donc justement de définir combien il faut introduire d'indels et à quelles positions entre les deux séquences.

Il n'existe pas qu'une seule manière d'aligner les deux séq entre elles, il existe une multitude d'alignements possibles, obtenant des scores divers.

Le but est de trouver rapidement le meilleur alignement, celui avec un score optimal.

A chaque fois qu'on aligne un résidu avec un autre, il faut donc tester les différentes possibilités (alignement, indel dans une seq ou dans l'autre), et on retient LA solution optimale, celle qui minimise le score (ou maximise le score, selon le cas : score de distance ou score d'homologie).

Donc pour l'endroit qui vous pose souci, on teste les 3 possibilités, par la diagonale, par l'horizontale et la verticale. Dans ce cas, le score minimal obtenu est 6, et il y a deux chemins qui donnent ce score minimal de 6. On retient donc ces deux chemins possibles dans la matrice.

Attention, à ce stade là, nous n'avons pas encore l'alignement optimal, il sera défini lors de la lecture arrière. Et dans cet exemple, ces cases ne seront pas utilisées pour l'alignemet optimal, elles ne correspondent pas à la trajectoire optimale.

Est ce que c'est plus clair ?

BW