METHODES

D’ALIGNEMENT
MULTIPLE

PAR M.OUNISSI
INTRODUCTION
Dans la comparaison de séquences en générale, Il y a des méthodes de calcul d’alignement de paires de
séquences et les méthodes d’alignement multiple,

Ainsi, on peut distinguer les méthodes d’alignement global versus local

Dans le coté application ou algorithme il y a l’heuristiques (par ex : blast) versus les algorithmes dits optimaux
(par ex. Smith et Waterman).

Problème

Ce dernier cas (algorithmes optimaux) est intéressant, car il est tout à fait possible de le mettre en application : mais en
effet, si l’on considère le cas d’un alignement de 10 séquences d’une longueur de 300 pb, l’espaces mémoire requis
serait 515 giga-octet (dans le case des algorithmes optimaux)!, pratiquement impossible

Par conséquent, les seules méthodes existantes a ce jour qui sont capable a résoudre ce problème sont des algorithmes
heuristiques c’est-à-dire des algorithmes qui tendent à une solution optimale (mais pas nécessairement exacte ).
 Les Méthodes heuristiques
C’est méthodes peuvent être classées en deux catégories
selon l’approche utilisée

Progressive Itérative
METHODE PROGRISSIVE
D’ALIGNEMENT MULTIPLE
INTRODUCTION

Les alignements progressifs sont des méthodes couramment utilisés pour le

développement d’alignements multiple de séquences.
Essentiellement, le processus de préparation d'un alignement progressif est basé sur la
construction d'alignements globaux par paires successifs par programmation
dynamique .

La plupart des algorithmes appliquent des méthodes

d'alignement progressif utilisent un arbre de guidage
pour établir un ordre dans lequel les séquences sont
fusionnés dans l'alignement multiple progressif.

L’arbre de guidage est formé en prenant toutes les

séquences et en appliquant les principes de
regroupement « clustring» pour construire un arbre
binaire dont les feuilles représentent des séquences et
des nœuds internes représentent alignements.
 RÉSUMÉ
Alignement multiple
 Une approche pour aligner des séquences Séquences non-alignées
multiples est de réaliser un alignement (.fasta)
progressif. Distances entre paires de séquences
 L’algorithme procède en plusieurs étapes: Sur base d’alignements global

 Calculer une matrice de distances, qui Matrice de distance

indique la distance entre chaque paire
de séquences. Regroupement hiérarchique
 Construire un arbre guide qui

regroupe en premier lieu les Arbre guide

séquences les plus proches, et remonte (.dnd)
en regroupant progressivement les
Alignement progressif
séquences les plus éloignées.
 Utiliser ce arbre pour aligner Alignement multiple
progressivement les séquences. (.aln)
CONSTRUCTION DE L'ARBRE
DE GUIDAGE
La construction de l'arbre de guidage pour un ensemble de N séquences procède essentiellement
comme suit:

1- calcule de matrice de score de similarité par paires (ou distance).

2- Chacune des séquences N est considéré comme un groupe de singleton. La similitude entre les
groupes (ou distance) est identique à la similitude par paire calculée à l'étape précédente.

3- Les groupes sont fusionnées de sorte que chaque étape de fusion successive choisit les groupes les
plus similaires et recalcule la similarité (ou distance) du nouveau groupe avec tous les autres groupes.

4- Le processus de fusion arrête lorsque toutes les séquences appartiennent à un grand groupe
contenant toutes les séquences N.

5- L'ordre dans lequel la séquence et les groupes sont fusionnés fournit l’arbre de guidage.

L'exemple suivant illustre l'application du procédé ci-dessus.

Exemple : __________________________________________________________________________________

Considérons l'ensemble de séquences suivantes:

S1 = ATTTACGCCT
S2 = TTAAGCCAT
S3 = TTAATTAACC
S4 = ATTTTCCGGA
S5 = AATTTACCGCCT

Utilisant le modèle de coût unitaire ou la « distance de Levenshtein », les valeurs de distance par paires
sont calculés comme suit: S1 S2 S3 S4 S5
S1 0 4 6 5 2 w(a,a) = 0
S2 0 5 7 6 w(a,b) =1 pour a≠b
S3 0 8 7 w(a,-) = w(-,b) =1
(modèle de coût unitaire)
S4 0 5
S5 0
Sur la base des valeurs de distance, les séquences les plus proches dans l'ensemble sont les
séquences S1 et S5 qui sont fusionnés dans une nouvelle séquence ou groupe S6.

Les distances de cette séquence fusionnée (S6) est ensuite calculés en prenant la distance moyenne de
S1 et S5 avec chacune des séquences restantes et recoder dans la matrice de distance indiquée ci-
dessous.

S6 S2 S3 S4
S6 0 5 6,5 5
S2 0 5 7
S3 0 8
S4 0

La plus petite distance entre deux paires des séquences dans le tableau ci-dessus est maintenant 5.
Nous pouvons choisir de fusionner une des trois paires qui ont cette distance minimale. Laissez-nous
choisir de fusionner par exemple les séquences S6 et S4 dans un nouveau groupe S7.
La distance de S7 sera calculée avec les séquences restantes S2 et S3.

Pour calculer la distance entre les groupes, une moyenne pondérée avec les membres du groupe (les
séquences) doit être utilisé de sorte que toutes les distances de séquences individuelles sont calculées.

Ainsi, comme groupe S6 contient déjà deux séquences (S1 et S5), la distance entre S2 et S7 est calculée

× , × ( , )
comme suit : ou 5,67. La distance entre S7 et S3 est calculée de façon similaire. A l'issue

de cette étape, la nouvelle matrice de distance se présente comme suit:

S7 S2 S3
S7 0 5,67 7
S2 0 5
S3 0
La paire de séquence la plus proche à fusionner ensuite est celle de S2 et S3. Le groupe fusionné est
groupé dans S8. Puisque ce dernier group contient des séquences uniques, leur distance à l'S7 peut
simplement être la moyenne et conduit à la matrice de distances ci-dessous:

S7 S8

S7 0 6,33

S8 0

L'étape finale est tout simplement une fusion des groupes S7 et S8 pour obtenir le groupe final S9 qui
comprend l'ensemble de séquences.

Le but essentiel de ce processus est la construction de l'arbre de guidage. L’Arbre de Guidage fournit
l'ordre dans lequel les séquences seront fusionnées dans l'alignement croissant progressivement.
_________________________________________________________________________________________Fin d’exemple
Construire AMS avec l'Arbre Guidage
>L’alignement multiple de séquences sera effectué comme ordonné par l'arbre de guidage.
Lors de l'alignement par paires original, n’importe quelle étape qui suivant l'arbre de guidage se traduira
par une nécessité des deux alignements possibles à être réaliser.
*Soit une séquence peut avoir besoin d'être alignés à un groupe de séquences, ou
*Un groupe de séquences nécessitant pour être aligné à un autre groupe de séquences.

Le 1er cas Le 2ème cas

Quand une seule séquence doit être aligné à un groupe de Et lorsqu'un groupe de séquence doit être aligné
séquences, l'algorithme de programmation dynamique est avec un autre groupe, la distance la plus faible
applicable pour le calcul du distance (ou un score) de la par paires entre chaque membre des deux
nouvelle séquence avec toutes les séquences dans le groupes est utilisé pour établir comment les
groupe. L'alignement qui a la distance la plus faible est deux groupes alignent les uns avec les autres.
utilisée pour déterminer comment la nouvelle
séquences va ensuite alignée au groupe.
Puisque les alignements progressifs sont formés, les trous (Indels) introduits dans un alignement par
paires sont remplacés par un caractère spécial, comme un X.
Ceci permet aux trous de progresser jusqu'à la fin d’alignement multiple où tous les Xs introduit dans
l'alignement multiple final construit sont remplacés par le caractère d'espace (─)

Concernant les algorithmes

Les algorithmes d'alignement par programmation dynamiques doivent également être ajustés
pour recevoir le spécial symbole X, notamment qu'il n'y a aucun coût associé à aligner un X avec
quoi que ce soit, y compris les autres caractères X.
Suite de l’exemple précédent : _________________________________________________________________________________

En continuant avec l'exemple précédent, où l'arbre de guidage été construit utilisant les
distances entre les paires de séquences, le processus de construction progressive de l'alignement
multiples de séquences est illustré dans cet exemple:

Pour débuter l’alignement multiple on commence par le groupe S7 qui contient la paire de
séquences à fusionner, S1 et S5, et la Séquence S4.
1-L’alignement entre La S1 et S5 est modifié de telle sorte que les Indels sont remplacés par les Xs.
Comme suit :

S1: -ATTTA-CGCCT S1: XATTTAXCGCCT

||||| |||||
S5: AATTTACCGCCT S5: AATTTACCGCCT
(Le group S6)
Selon l'arbre de guidage, la séquence suivante à aligner est S4.

La procédure d'alignement de cette séquence pour ce groupe va tenter d'aligner cette séquence avec
chacune des séquences dans le groupe (S1 et S5).

Nous essayons donc un alignement par paire global de S1 et S5 avec S4 et l'alignement qui a la faible
distance détermine comment la séquence S4 va s’aligner au groupe.

Chacun de ces alignements et leurs distances avec le modèle de coût unitaire sont présentés ci-dessous:

S1: XATTTAXCGCCT S5: AATTTACCGCCT

|||| :|| |||| |||
S4: -ATTTTCCG-GA S4: -ATTTTCCG-GA
Distance = 4 Distance = 5
Rappelons que dans le calcul des valeurs de distance, l'alignement du caractère X avec un autre
caractère n’ajoute rien au calcule globale de la distance d'alignement.

Basant sur les alignements ci-dessus, la séquence S4 serait donc être alignée à S1 a fin de l'inclure dans
le groupe. L’AMS des trois séquences à ce stade se présente comme suit:
S1: XATTTAXCGCCT
S5: AATTTACCGCCT Groupe7
S4: XATTTTCCGXGA
Processus similaire est utilisé pour créer un alignement de séquences S2 et S3 avec le groupe
7 calculés comme suit avec le caractère neutre X remplaçant les indels.

S2: TTAAGCCA-T S2: TTAAGCCAXT

|||| |
S3: TTAATTAACC S3: TTAATTAACC
L'étape suivante dans le procédé d'alignement progressif implique la fusion des deux groupes de séquences,
{S1, S4, S5} et {S2, S3}.

Pour un alignement des deux groupes, toutes les paires de séquences dans les deux groupes sont essayés, et
la faible distance d’alignement entre les groupes est utilisé pour ancrer les alignement des groupes fusionnés.

Dans notre exemple, l'un des six possibles alignements par paires représenté sur le tableau suivant, aura
choisi pour ancrer l'alignement de l'ensemble des deux groupes (S7 et S8).

S2 S3
S1 XATTTAXCGCC--T -XATTTAXCGCCT
|||: ||| | :| |||: ||
---TTAA-GCCAXT TTAATTAA--CC-

Distance: 4 Distance: 5
S4 XATT-TTCCGXGA --XATTTTCCGXGA
|| || :: :||| ||
--TTAAGCC-AXT TTAATTAACC----

Distance: 6 Distance: 7
S5 AATTTACCGCC--T --AATTTACCGCCT
||| ||| | || ||| ||
---TTA-AGCCAXT TTAA-TTA--ACC-
Distance: 6 Distance: 6
Sachant que la séquence S1 dans le premier groupe est plus proche de la séquence S2 du second groupe, leur
alignement est utilisé pour ancrer l'alignement du groupe fusionné (groupe S7 et S8).

Puisque ces séquences sont alignées précédemment aux autres membres de leur groupe respectif, les nouvelles
Indels insérées dans S1 sont également insérés dans S4 et S5. En conséquence, de nouvelles indels insérées dans S2
sont également insérés dans S3.

Ces étapes et l'alignement multiples de séquences résultants sont représentés dans la figure suivante:

Grope 7 Grope 8

L’alignement multiple
final
Algorithme pour alignement
progressif
 Alignement multiple avec ClustalW

ClustalW est une méthode progressive globale de construction d’alignement multiple.

A partir d’un ensemble de séquences nucléotidiques ou protéiques , on calcule une
matrice de similarité , en comparant toutes les séquences par paires.
L’alignement utilisé est de type Needleman-Wunsch, recherche le meilleur alignement
global de chaque paire de séquences.

Cette matrice est alors utilisée pour construire un arbre de guidage.

L’arbre de guidage est ensuite parcouru pour déterminer à chaque itération, la paire la
plus proche.
• Programme original CLUSTAL [Higgins & Sharp, 88] utilisé depuis
1988, régulièrement amélioré.

• CLUSTALW [Thompson et al, 94] = version la plus classique (W

pour Weighting) ; les séquences et les paramètres sont pondères

• CLUSTAL Omega « ClustalΩ »[Sievers et al, 11] = version la plus

récente ; amélioration en terme d’échelle et de qualité des aln

• Fonctionnalités : ajout d’une séq ou d’un ali à un ali.,

production d’un arbre phylogénétique,, . . .
Alignement avec ClustalW
Étant donné un ensemble de séquences S = {S1, S2,. . . , Sk}, chacune a une longueur de L(n). ClustalW
effectue les trois étapes suivantes.

1ère Etape
Tout d'abord, ClustalW calcule l'alignement global optimal pour chaque paire de séquences Si et Sj,
Ensuite, la distance de Si et Sj est réglée pour être une 1- où x est le nombre de positions « non-gap »
et y le nombre de positions identiques, dans l'alignement entre Si et Sj.

Exemple
Soit l’alignement suivant:
S1: PPGVKSDCAS
S2: PPDGKSD--S
l'alignement de S1 et S2. Il ya 8 positions non-Gap et 6 positions identiques. Par conséquent, la
distance est de 1 – (6/8 )= 0,25.
2ème Etape
ClustalW construit l'arbre de guidage à partir de la matrice de distances en utilisant l'algorithme
neighbor joining

3ème Etape
Selon l'arbre de guidage, nous effectuons une série d'alignements d'aligner des groupes de
séquences. Pour les séquences sur la figure suivante, et selon l'arbre de guidage.

4ème étapes de l'alignement

(a) aligner S1 avec S3, (b) aligner S4 et S5, (c) aligner l'alignement des (S1,
S3) avec S2, et (d) aligner l'alignement des (S1, S2 , S3) avec l'alignement
des (S4, S5).
A chaque étape, deux ensembles d'alignements (groupes) sont alignées en
introduisant de nouvelles brèches.
En outre, les brèches qui sont présents dans les alignements originaux
ne seront pas supprimés.
Tel alignement est connu comme l'alignement profil profil.

 Après les trois étapes, ClustalW rapporte l'alignement multiple final.

Alignement Profil-Profil

L'étape 3 le ClustalW calcule l'alignement de deux alignements. L'entrée se compose de deux ensembles
de séquences (deux groupes) S6 et S7et les alignements multiples A1 et A2 correspondants,
L'alignement profil-profil présente des brèches en A1 et A2 pour générer l'alignement multiple pour S6
∪ S7.

Par exemple, sur la figure ci-contre , les deux alignements A1 et A2 sont alignées par l'introduction d'une
brèche de deux extension entre les colonnes 5 et 6 de A2.

A1

A2
Algorithme pour alignement progessif
local
Alignement multiple avec DIALIGN
DIALIGN combine les caractéristiques globales et locales d'alignement et il est
donc particulièrement utile pour aligner des séquences distantes mais qui
partagent des homologies locales isolées.
 Alignement multiple avec DIALIGN
C’est un programme d’alignement multiple qui repose sur une méthode très différente de celle employée
par ClustalW.
Il s’agit ici d’une méthode progressive utilisant une approche locale et globale pour calculer les
alignements multiples.
Principe de fonctionnement:
Dans un premier tempe on compare toutes les paires de séquences. Dans le cas de DIALIGN, cette étape
consiste à rechercher tous les fragments pour ne retenir que ceux qui sont compatible (même longueur
et se croisent pas).

Un fragment (la plus grand possible) comporte une suite de résidus consécutif (bases, AA) résultants,
similaires entre deux premières séquences proche.

Selon cette définition on constate qu’un fragments ne peut pas contenir d’indels.

Ensuite, en ne retient que ceux qui sont compatible, c’est-à-dire des fragments qui ne se croisent
pas.
 Exemple pour comprendre les fragments compatible

Dans cet exemple les deux séquences IAVLFA et LACVIFG sont similaires mais de longueur
différentes; donc ne sont pas des fragments compatibles (présence d’indel).

En revanche, IA/IA et VLFA/VIFG sont des fragments similaire ont mêmes longueurs,
mais le problème que IA n’est pas compatible puisqu’à gauche dans la deuxième séquence et à droite
dans la première (ils se croisent).

Y I A V L F A E D

L A C V I F G I A
NOTE
Les fragments de DIALING s’appellent des mots dans d’autres programmes comme
Blast ou FASTA
 Après avoir repéré tous les fragments compatible dans l’exemple précèdent sont IA/LA
Suite
et VLFA/VIFG (dans la première paire),
d’exemple
Les séquences sont triées en fonction du nombre total de fragments communs entre elles.

La dernière étape de l’algorithme consiste à aligner itérativement les séquences c’est-à-dire de la première
à la dernière séquence de la liste.

A chaque Alignement , des brèches sont ajoutées de manière à ce que les différents résidus soient
correctement alignés. La figure ci- contre montre le cas d’un alignement de trois séquences protéiques

Y I A V L F A E D Y I A V L F A E D Y I A V L F A E D

L A C V I F G S L A C V I F G S L A C V I F G S

P W D D V T F D A E P W D D V T F D A E
YIA-VLFAED
-LACVIFGS- YIA-VLF-AED
1 Fragments compatibles -LACVIF-GS-
PWDDVTFDAE-
2 Alignement 1
3 Alignement 2 final
Exemple de sortie d’alignement effectué sur site web de DIALIGN
 Comparaison de DIALIGN avec ClustalW:

Si nous réalisons un alignement multiple de ces mêmes séquence avec le programme

ClustalW, nous obtenons bien l’alignement de la région HIGH, mais pas de la région
KMSKS, comme le met en évidence la figure suivante.

On constate donc que si DIALIGN est capable d’aligner correctement ces séquences , ce
n’est pas le cas de ClustalW.

La raison de cet échec est liée à la difficulté trouvé par ClustalW pour traiter les longues
Brèches ,
 METHODE ITERATIVE
D’ALIGNEMENT MULTIPLE
DEFINITION
L'inconvénient majeur de la méthode progressive est bien décrite par la paraphrase
"une fois une brèche, toujours une brèche”, “once a gap, always a gap”ce qui signifie que
si un écart erronée est insérée à un stade précoce, il se propage au résultat final sans
aucune chance de correction.

 Une méthode pour contourner ce défaut est d'utiliser une approche efficace repose
sur le processus post connu comme raffinement itératif ou " iterative refinement”
Un raffinement itératif se compose de quatre étapes:

(1) Construction d’un AMS initial par une méthode, par exemple progressive.
(2) Diviser Horizontalement l’AMS en deux groupes (Profils). Supprimer seulement les colonnes composées
de caractères nuls de chacun des deux groupes.
(3) Aligner les deux groupes par un procédé d'alignement par paires; d’une séquence à un groupe ou d'un
groupe à un autre groupe.
(4) Répétition les étapes (2) et (3) jusqu'à ce qu'aucune amélioration du score d'alignement est prévu, soit
par un nombre de fois prédéfini.

divide sequences pairwise

into 2 groups profile
Profile 1 alignment Refined
Initial
multiple alignment alignment

Global Score
progressif improvement ?
Profile 2

no
Note importante

Les algorithme d’alignement multiple peuvent donc aussi être subdivisés en deux grandes classes: les
alignement globaux et les alignements locaux.
Schématiquement, une méthode globale sera plus apte a aligner des séquences de longueurs
homogènes, tandis qu’une méthode locale sera plus adaptée a l’alignement de séquences de longueurs
variables .
Il vaut mieux aligner des séquences protéiques plutôt que des séquences nucléotidiques. lorsque cela
est possible.
 Examples algorithms Itératifs

MAFFT (Multiple Alignment using

Fast Fourier Transform) est un
algorithme d'alignement multiple de
séquences à grande vitesse.