© Dunod – Toute reproduction non autorisée est un délit.
49
5.2 • Comparaison de protéines homologues (algorithme global)
moins structurées. Ainsi, on peut imaginer des systèmes de pénalité qui favorisent
les indels dans ces régions (voir le chapitre 9 sur les profils d’hydrophobie pour
l’identification des régions externes). Le nombre d’alignements possibles entre deux
séquences en autorisant des indels peut dépasser le nombre d’atomes dans l’Univers
(en fonction des longueurs).
Tout comme la recherche dans les banques (décrite dans le chapitre précédent),
l’alignement peut être global ou local.
Par exemple, l’alignement suivant présente sept identités :
G G C T G A C C A C C - T T
|
|
| |
| |
|
G A - T C A C T T C C A T G
Ainsi, le premier alignement est celui qui maximise les identités sur la totalité des
deux séquences. On parle alors d’alignement global. L’application majeure de ce
type d’alignement est l’alignement de séquences de protéines homologues en vue
d’identifier des acides aminés conservés par l’évolution. Au cours de l’évolution, les
séquences varient de façon à préserver (voire optimiser) la fonction biologique.
Un alignement local des mêmes séquences fournira aussi sept identités mais
donnera un alignement différent :
G G C T G A C C A C C T T
| |
| | |
| |
G A T C A C - T T C C A T G
Cet alignement local sera privilégié si le plus long chevauchement entre deux
séquences est recherché comme dans le cas de la reconstruction à partir de données
obtenues par séquençage. Le choix de l’alignement global ou local revient donc à
l’utilisateur biologiste en fonction des objectifs poursuivis.
5.2 COMPARAISON DE PROTÉINES HOMOLOGUES
(ALGORITHME GLOBAL)
Il s’agit d’un algorithme de programmation dynamique pour l’alignement global
optimal entre deux séquences. Les trois paramètres du programme sont les scores
pour i) l’identité, ii) la substitution et iii)
quences sont placées
l’indel. Les deux sé
dans un tableau. Le principe consiste à calculer des scores de chaque case du tableau
en partant de la case (0,0) jusqu’à la case (n,m) en remplissant ligne par ligne en
simulant les trois types d’opérations possibles (insertion, délétion ou mise en correspondance). Dans le cas de la mise en correspondance, on peut avoir substitution de
Ai par Bj ou identité Ai, Aj. Pour chaque cas, le score S(i,j) de la case i,j est calculé
des trois façons symbolisant les trois déplacements possibles :
S(i,j)= S(i-1,j-1) + subst(i,j) (substitution ou identité)
S(i,j)=s(i-1,j) + Indel() car insertion à la position i-1 (ou délétion à la
position j)
S(i,j)=s(i,j-1) + Indel() car insertion à la position j-1 (ou délétion à la
position i)
49
5.2 • Comparaison de protéines homologues (algorithme global)
moins structurées. Ainsi, on peut imaginer des systèmes de pénalité qui favorisent
les indels dans ces régions (voir le chapitre 9 sur les profils d’hydrophobie pour
l’identification des régions externes). Le nombre d’alignements possibles entre deux
séquences en autorisant des indels peut dépasser le nombre d’atomes dans l’Univers
(en fonction des longueurs).
Tout comme la recherche dans les banques (décrite dans le chapitre précédent),
l’alignement peut être global ou local.
Par exemple, l’alignement suivant présente sept identités :
G G C T G A C C A C C - T T
|
|
| |
| |
|
G A - T C A C T T C C A T G
Ainsi, le premier alignement est celui qui maximise les identités sur la totalité des
deux séquences. On parle alors d’alignement global. L’application majeure de ce
type d’alignement est l’alignement de séquences de protéines homologues en vue
d’identifier des acides aminés conservés par l’évolution. Au cours de l’évolution, les
séquences varient de façon à préserver (voire optimiser) la fonction biologique.
Un alignement local des mêmes séquences fournira aussi sept identités mais
donnera un alignement différent :
G G C T G A C C A C C T T
| |
| | |
| |
G A T C A C - T T C C A T G
Cet alignement local sera privilégié si le plus long chevauchement entre deux
séquences est recherché comme dans le cas de la reconstruction à partir de données
obtenues par séquençage. Le choix de l’alignement global ou local revient donc à
l’utilisateur biologiste en fonction des objectifs poursuivis.
5.2 COMPARAISON DE PROTÉINES HOMOLOGUES
(ALGORITHME GLOBAL)
Il s’agit d’un algorithme de programmation dynamique pour l’alignement global
optimal entre deux séquences. Les trois paramètres du programme sont les scores
pour i) l’identité, ii) la substitution et iii)
quences sont placées
l’indel. Les deux sé
dans un tableau. Le principe consiste à calculer des scores de chaque case du tableau
en partant de la case (0,0) jusqu’à la case (n,m) en remplissant ligne par ligne en
simulant les trois types d’opérations possibles (insertion, délétion ou mise en correspondance). Dans le cas de la mise en correspondance, on peut avoir substitution de
Ai par Bj ou identité Ai, Aj. Pour chaque cas, le score S(i,j) de la case i,j est calculé
des trois façons symbolisant les trois déplacements possibles :
S(i,j)= S(i-1,j-1) + subst(i,j) (substitution ou identité)
S(i,j)=s(i-1,j) + Indel() car insertion à la position i-1 (ou délétion à la
position j)
S(i,j)=s(i,j-1) + Indel() car insertion à la position j-1 (ou délétion à la
position i)