Recherche Bioinformatique Alignement

Recherche en Bioinformatique - Alignement

Alignement multiple (Multiple Sequence Alignment)

L'algorithme de Programmation Dynamique peut être étendu dans le cadre de l'alignement de plus de 2 séquences. Cependant sa complexité spatiale est en O(n^k) et sa complexité temporelle est en O(2^k x n^k), où k est le nombre de séquences à aligner, ce qui rend cet algorithme particulièrement inadapté à l'alignement de plus de 6 à 8 séquences.

Par exemple pour un alignement global de 3 séquences avec gaps linéaires on utilise la formule suivante :

M[i,j,k] =

D[i-1,j-1,k-1]	+ w(a_i,b_j,c_k)
D[i,j-1,k-1]	+ w(-,b_j,c_k)
D[i-1,j,k-1]	+ w(a_i,-,c_k)
D[i-1,j-1,k]	+ w(a_i,b_j,-)
D[i-1,j,k]	+ w(a_i,-,-)
D[i,j-1,k]	+ w(-,b_j,-)
D[i,j,k-1]	+ w(-,-,c_k)

Exemple
Si on doit aligner 10 séquences de longueur 100, il est nécessaire d'effectuer de l'ordre de :
2¹⁰ x 100¹⁰ calculs soit environ 10²³ calculs si on était capable d'effecter l'un des calculs en 1 ns il faudrait :
10²³ x 10^-9 = 10¹⁴ s, soit 3 millions d'années

Des alternatives ont été développées afin de s'attaquer à ce problème difficile. Citons en particulier :

l'alignement progressif, approche mise en oeuvre dans Clustal W et PileUp
l'utilisation de méthodes itératives comme les Algorithmes Génétiques (SAGA)
Hidden Markov Model (HMMER)
Gibbs Sampling
Maximum Weight Trace Problem

Méthodes progressives
Les alignements multiples progressifs sont créés en commençant par aligner les séquences les plus similaires, puis en ajoutant progressivement les séquences les moins similaires.

L'ordre dans lequel les séquences sont ajoutées est donné par un guide tree ou arbre phylogénétique construit par une méthode de neighbor-joining dans le cas de Clustal, ou UPGMA dans le cas de PileUp.

Cette méthode se révèle très efficace pour construire rapidement des alignements multiples car sa complexité est linéaire en nombre de séquences à aligner.

Méthodes itératives
Ces méthodes consistent d'une part à aligner de manière répétitives des segments (ou sous-groupes de séquences) et d'autre part à aligner ces sous-groupes dans le cadre d'un alignement global. Le but de ce genre d'approche est d'améliorer la qualité globale de l'alignement.

Les logiciels qui mettent en oeuvre ce genre de méthodes sont MaultAlin (Corpoet 1988), DIALIGN (), SAGA (Notredame et Higgins, 1996).

Hidden Markov Model

Maximum Weihgt Trace problem

Sommaire

Jean-Michel Richer, 2004