Bienvenue à exoco-lmd.com! Partagez et consultez des solutions d'examens et d'exercices des programmes LMD et formation d'ingénieur.

3. Bioinformatique Alignement de séquences multiples

Démarré par sabrina, Décembre 24, 2018, 12:52:28 PM

« précédent - suivant »

sabrina

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.

Hors ligne Annonceur

  • Jr. Member
  • **
  • Messages: na
  • Karma: +0/-0
Re : message iportant de l'auteur
« le: un jour de l'année »





Suggestions pour vous