ExoCo-LMD
Sciences de la Nature et de la Vie - SNV => L3 SNV (Les modules de troisième année) => Bioinformatique => Discussion démarrée par: sabrina le Décembre 24, 2018, 12:52:28 PM
3. Bioinformatique Alignement de séquences multiples
L'approche de programmation dynamique peut
être étendue pour aligner 3 séquences.
Construction d'une matrice d'alignement
tridimensionnelle.
Le meilleur score de chaque cellule est
calculé sur base des cellules précédentes
dans les 3 directions.
On peut étendre le concept à N séquences en
utilisant un hypercube à N dimensions.
Problème : la taille de la matrice (mémoire
occupée) et le temps d'exécution augmentent
exponentiellement avec le nombre de
séquences:
2 séquences L1 x L2
3 séquences L1 x L2 x L3
4 séquences L1 x L2 x L3 x L4
n séquences L1 x L2 x ... x Ln ~ Ln
Aligner N séquences en programmation
dynamique requiert O(Ln) opérations, ce qui
devient très vite impraticable.
L'efficacité peut être améliorée en ne
considérant qu'un sous-espace de la matrice à
N-dimension. Cependant, le nombre de
séquences praticable reste très limité (~8
séquences max).
Une approche alternative pour aligner des séquences multiples est de réaliser
un alignement progressif.
L'algorithme procède en plusieurs étapes:
Calculer une matrice de distances, qui indique la distance entre chaque paire de
séquences.
Construire un arbre guide qui regroupe en premier lieu les séquences les plus
proches, et remonte en regroupant progressivement les séquences les plus éloignées.
Utiliser ce arbre pour aligner progressivement les séquences.
Il s'agit d'une approche heuristique
Cette approche est praticable pour un grand nombre de séquences, mais ne peut pas
garantir de retourner l'alignement optimal.