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(ai,bj,ck) D[i,j-1,k-1] + w(-,bj,ck) D[i-1,j,k-1] + w(ai,-,ck) D[i-1,j-1,k] + w(ai,bj,-) D[i-1,j,k] + w(ai,-,-) D[i,j-1,k] + w(-,bj,-) D[i,j,k-1] + w(-,-,ck)

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