Alignements multiples

	Documents en bioinformatique
	Introduction à la bioinfo
	Historique
	Recherche de similarités dans les banques
	Alignements multiples
	Phylogénie


	Documents en informatique

	Tutoriaux

	Tables et Standards

Accueil

Documents en bioinformatique - Alignements multiples



	INTRODUCTION

	ALGORITHMES Needleman et Wunsch \| Méthode heuristique

	CLUSTALW Multiple Alignments Menu Pairwise Alignment Parameters Multiple Alignment Parameters Protein Gap Parameters Profiles and Structure Alignment Menu Secondary Structure Options Phylogenetic Tree Menu

	CONCLUSION

Introduction

La comparaison de séquences est un traitement de base en biologie moléculaire. L'alignement multiple peut révéler des fonctions que l'on n'a pas visualiser en comparant les séquences deux à deux. Il permet de :


		Détecter des résidus identiques ou similaires pouvant jouer un rôle clé dans la fonction de la molécule ou dans sa structure tridimensionnelle.

		Caractériser de nouvelles familles de protéines.

		Détecter ou démontrer une homologie entre différentes séquences

		Trouver un PRIMER concensus pour des PCR

		Etablir une phylogénie

		Aider à la modélisation : les algorithmes de prédiction de structure secondaire exploitent très bien les alignements multiples. Le traitement est très long et dépend de trois paramètres : le volume de données à traiter, la puissance de calcul des ordinateurs et les algorithmes utilisés.

Algorithmes

Il existe deux grandes classes d'algorithmes pour réaliser des alignements multiples, soit une généralisation de l'algorithme de Neeedleman et Wunsch, soit des méthodes heuristiques.


	1. Généralisation de l'algorithme de Needleman et Wunsch

On recherche l'alignement multiple qui maximise la somme des scores de chaque alignement pour chaque paire (pour n séquences, il y a n(n-1)/2 paires). Cependant, la taille du problème, en temps et en place mémoire dans l'ordinateur, est proportionnelle au produit des longueurs des séquences : si les N séquences sont de longueur L, la complexité est en LN. Cette complexité croit de façon exponentielle avec le nombre de séquences, elle est donc utilisable avec un petit nombre de séquences mais ne peut répondre à la plupart des besoins.


	2. Méthode heuristique

C'est l'approche la plus commune. Cette méthode est rapide et dans la plupart des cas, donne de bons résultats. Elle est utilisée par le programme Clustalw.
Clustalw commence par aligner deux à deux les séquences et construit l'arbre des relations évolutives entre les séquences. Les noeuds entre les branches représentent les alignements deux à deux et la racine représente l'alignement complet.
Une fois cet arbre construit, le programme prend les deux séquences les plus proches et commence l'alignement multiple (l'alignement des séquences les plus proches est le plus fiable). Puis il progresse vers les séquences plus distantes, et remonte ainsi l'arbre.
Ce programme est rapide pour un nombre raisonnable de séquences longues et plus lent si on aligne un grand nombre de séquences courtes.

Exemple
Soit 4 séquences S1, S2, S3 et S4

Réalisation de l'alignement deux à deux des séquences avec calcul d'un score : on obtient donc une distance pour chaque couple.

Construction d'une matrice de distances.

S1 S2 S3 S4

S1

S2 d3

S3 d1 d4

S4 d5 d2 d6

Elaboration d'un dendrogramme qui donnera l'ordre de l'alignement multiple

On considère que d1 < d2 < d3 < d4 <d5 < d6

                          S4
S3                      /
\      S1           /
    \    / S2      /
    C1       \    /
       \       C2
          \      /
            \ /
           C3

Construction successives de consensus permettant de remonter dans l'arbre

a. -------------------------- S3
-------------------------- S1
------------------------- C1

b. -------------------------- S2
-------------------------- S4
------------------------- C2

c. ------------------------- C1
--------------------- ---- C3
-------------------------- C3

CLUSTALW

**************************************************************
******** CLUSTAL W (1.83) Multiple Sequence Alignments ********
**************************************************************

     1. Sequence Input From Disc
     2. Multiple Alignments
     3. Profile / Structure Alignments
     4. Phylogenetic trees

     S. Execute a system command
     H. HELP
     X. EXIT (leave program)

Your choice:

****** MULTIPLE ALIGNMENT MENU ******

    1. Do complete multiple alignment now (Slow/Accurate)
    2. Produce guide tree file only
    3. Do alignment using old guide tree file

4. Toggle Slow/Fast pairwise alignments = SLOW

5. Pairwise alignment parameters
6. Multiple alignment parameters

    7. Reset gaps before alignment? = OFF
    8. Toggle screen display          = ON
    9. Output format options

    S. Execute a system command
    H. HELP
    or press [RETURN] to go back to main menu

Your choice:


	Do alignment using old guide tree file

On peut utiliser un ancien dendrogramme pour guider l'alignement initial ou seulement produire ce dendrogramme sans aller jusqu'à l'alignement multiple (Produce guide tree file only).


	Pairwise alignment parameters

contrôle la vitesse et la sensibilité de l'alignement initial.


	Multiple alignment parameters

contrôle les gaps dans l'alignement multiple final.
Dans ce menu, on peut choisir la vitesse avec laquelle on veut que l'alignement se fasse :
- Méthode lente mais précise : cette méthode est très lente pour un grand nombre (> 100) de longues séquences (>1000 résidus).
- Méthode rapide mais plus approximative : le programme n'utilise que les meilleures diagonales, c'est à dire celles présentant le plus de fragments d'appariements exacts.


	Reset gaps before alignment ?

cela permet d'effacer tous les gaps d'un alignement et de le refaire en modifiant certaines options (ON). Si cette option est OFF, les nouveaux gaps seront conservés si un second alignement est réalisé (Parfois, un deuxième passage voire un troisième améliore la qualité de l'alignement).


	Toggle screen display

Les résultats sont envoyés à la fois à l'écran et dans un fichier de sortie.

********* PAIRWISE ALIGNMENT PARAMETERS *********

Slow/Accurate alignments:

     1. Gap Open Penalty       :10.00
     2. Gap Extension Penalty :0.10
     3. Protein weight matrix :Gonnet series
     4. DNA weight matrix      :IUB

Fast/Approximate alignments:

     5. Gap penalty            :3
     6. K-tuple (word) size    :1
     7. No. of top diagonals   :5
     8. Window size            :5

9. Toggle Slow/Fast pairwise alignments = SLOW

H. HELP

Enter number (or [RETURN] to exit):

Slow/Accurate alignments:

Si on augmente les pénalités d'ouverture et d'extension des gaps, ceux-ci seront moins fréquents (Gap open Penalty) et plus courts (Gap Extension Penalty).


	Protein weight matrix

Matrice de scores donnant la similarité des acides aminés les par rapport aux autres. On peut choisir entre BLOSUM 30,PAM 35, Gonnet 250, la matrice identité ou une matrice personnelle.


	DNA weight matrix

Matrice de scores pour les acides nucléiques.

Fast/Approximate alignments:

Si on augmente la taille des k-tuples, la vitesse augmente tandis que si on la diminue, c'est la précision qui augmente. [les maximum sont de 2 pour les protéines et 4 pour les acides nucléiques].


	Gap penalty

Cela n'a que peut d'influence sur la rapidité de l'alignement sauf pour des valeurs extrêmes.


	No. of top diagonals

Nombre de k-tuples qui matchent sur chaque diagonale (dans un dotplot imaginaire) et seuls les meilleurs sont utilisés pour l'alignement. Une diminution de ce paramètre rend l'alignement plus rapide tandis qu'une augmentation améliore la sensibilité.

********* MULTIPLE ALIGNMENT PARAMETERS *********

     1. Gap Opening Penalty              :10.00
     2. Gap Extension Penalty            :0.20
     3. Delay divergent sequences        :30 %

4. DNA Transitions Weight :0.50

     5. Protein weight matrix            :Gonnet series
     6. DNA weight matrix                :IUB
     7. Use negative matrix              :OFF

8. Protein Gap Parameters

H. HELP

Enter number (or [RETURN] to exit):


	Delay divergent sequences

donne le seuil au-dessus duquel l'alignement est retardé : ainsi, si une séquence donnée est plus de 30% différentes des autres, son alignement est remis à plus tard.


	DNA Transitions Weight

(poids des transitions A <-> G, C <-> T) : Un poids de zéro signifie que les transitions seront considérées comme des mismatches. Pour des séquences éloignées, ce poids doit être proche de zéro tandis qu'il est égal à 1 pour des séquences très proches.

********* Format of Alignment Output *********

     1. Toggle CLUSTAL format output     = ON
     2. Toggle NBRF/PIR format output    = OFF
     3. Toggle GCG/MSF format output     = OFF
     4. Toggle PHYLIP format output      = OFF
     5. Toggle NEXUS format output       = OFF
     6. Toggle GDE format output         = OFF

     7. Toggle GDE output case           = LOWER
     8. Toggle CLUSTALW sequence numbers = OFF
     9. Toggle output order              = ALIGNED

0. Create alignment output file(s) now?

T. Toggle parameter output = OFF

H. HELP

Enter number (or [RETURN] to exit):

Clustal offre 6 formats de sortie et l'on peut en choisir un ou plusieurs.


	Toggle GDE output case

pour le format GDE, les caractères peuvent être soit en majuscules soit en miniscules.


	Toggle CLUSTALW sequence numbers


	Toggle output order

si ce paramètre est sur ALIGNED, l'ordre des séquences dans le fichier de sortie sera le même que celui du dendrogramme servant à guider l'alignement. Si ce paramètre est sur INPUT, l'ordre des séquences dans le fichier de sortie sera le même que celui du fichier d'entrée.

********* PROTEIN GAP PARAMETERS *********

1. Toggle Residue-Specific Penalties :ON

2. Toggle Hydrophilic Penalties :ON
3. Hydrophilic Residues :GPSNDQEKR

4. Gap Separation Distance :4
5. Toggle End Gap Separation :OFF

H. HELP

Enter number (or [RETURN] to exit):


	Toggle Residue-Specific Penalties

Ce sont des pénalités sur certains acides aminés. Ces pénalités augment ou diminuent la probabilité d'ouverture d'un gap selon la position sur la séquence. Par exemple, les positions riches en glycine seront plus souvent adjacentes à un gap que les positions riches en valine.


	Toggle Hydrophilic Penalties

augmente la probabilité d'avoir des gaps dans les régions hydrophiles correspondant souvent à des boucles ou des "coils"


	Gap Separation Distance

ce paramètre tente de diminuer les risques d'avoir des gaps trop proches les uns des autres. Les gaps qui sont plus proches que cette distance sont plus pénalisés que les autres. Cela n'empêche pas d'avoir des gaps très proches, cela les rend seulement moins fréquents, donnant une apparence de blocs à l'alignement.


	Toggle End Gap Separation

Si ce paramètre est sur OFF, les gaps en fin de séquences sont ignorés, ce qui est utile lorsque l'on veut aligner des fragments où les gaps terminaux n'ont pas de signification biologique.

****** PROFILE AND STRUCTURE ALIGNMENT MENU ******

1. Input 1st. profile
2. Input 2nd. profile/sequences

3. Align 2nd. profile to 1st. profile
4. Align sequences to 1st. profile (Slow/Accurate)

5. Toggle Slow/Fast pairwise alignments = SLOW

6. Pairwise alignment parameters
7. Multiple alignment parameters

    8. Toggle screen display                = ON
    9. Output format options
    0. Secondary structure options

    S. Execute a system command
    H. HELP
    or press [RETURN] to go back to main menu

Your choice:


	Align 2nd. profile to 1st. profile

permet d'aligner deux alignements déjà existants (même si chacun d'eux ne contient qu'une séquence)


	Align sequences to 1st. profile (Slow/Accurate)

permet d'ajouter une (ou une série de ) nouvelle séquence à un alignement déjà existant.
L'intérêt de ce choix est double :
- on peut ainsi construire un alignement de façon progressive en ajoutant de nouvelles séquences (souvent, seul un petit nombre de séquences sont à l'origine de nombreux mésappariements : on pourra les ajouter seulement à la fin).
- on peut avoir un alignement de référence sur lequel on aligne les nouvelles séquences.

********* SECONDARY STRUCTURE OPTIONS *********

1. Use profile 1 secondary structure / penalty mask = YES
2. Use profile 2 secondary structure / penalty mask = YES

3. Output in alignment = Secondary Structure

     4. Helix gap penalty                     :4
     5. Strand gap penalty                    :4
     6. Loop gap penalty                      :1
     7. Secondary structure terminal penalty :2
     8. Helix terminal positions       within :3      outside :0
     9. Strand terminal positions      within :1      outside :1

H. HELP

Enter number (or [RETURN] to exit):

Si une structure secondaire est disponible, elle peut être utilisée pour guider l'alignement ( les gaps seront préférenciellement introduits dans les régions dépourvues de structure secondaire) et cela augmentera la justesse de l'alignement.

****** PHYLOGENETIC TREE MENU ******

    1. Input an alignment
    2. Exclude positions with gaps?        = OFF
    3. Correct for multiple substitutions? = OFF
    4. Draw tree now
    5. Bootstrap tree
    6. Output format options

    S. Execute a system command
    H. HELP
    or press [RETURN] to go back to main menu

Your choice:

La méthode utilisée est la méthode du Neigbour-Joining (NJ) développée par Saitou et Nei : on calcule d'abord la distance (proportionnelle à la divergence) entre toutes les paires de séquences de l'alignement puis on applique la méthode de NJ sur la matrice de distance.


	Exclude positions with gaps?

si ce paramètre est sur ON, alors toutes les positions auxquelles n'importe laquelle des séquences possède un gaps seront ignorées : cela a pour conséquence de perdre une grande quantité d'informations si l'alignement contient de nombreux gaps.


	Correct for multiple substitutions?

pour des séquences faiblement divergentes (<10%), cette option n'a pas d'intérêt. pour des divergences plus importante, cela corrige le fait que les distances observées sous-estiment les distances évolutives. Cette option à pour effet de raccourcir les longues branches d'un arbre et doit toujours être utilisée mais il faut savoir que pour des séquences très divergentes, les distances ne peuvent pas être relier de façon convenable.


	Bootstrap tree

cette méthode statistique permet d'estimer la confiance que l'on peut avoir dans l'arbre obtenu. Cette méthode génère un échantillonnage aléatoire à partir des données initiales puis compte combien de fois chaque regroupement de l'arbre initial se retrouve dans l'échantillonnage.

Conclusion

La comparaison simultanée de plusieurs séquences est un outil très utile pour mieux comprendre la structure et l'évolution des protéines et des acides nucléiques mais il faut rester critique au niveau des résultats : l'alignement optimal calculé par ordinateur est rarement le meilleur au sens biologique.
Il faut toujours vérifier un alignement avant de passer à l'étape suivante (phylogénie par exemple) et il peut être nécessaire de le corriger.
Il faut également savoir que l'ordre des séquences dans le fichier d'entrée joue un rôle important.

	FTP Documents


	Bioinformatique Homologies-alignements Analyse Alignements



	ClustalW ClustalX



	A Gentle Guide to Multiple Alignment


		L'utilisation des services Infobiogen ne peut-être exploitée à des fins industrielles et / ou commerciales

	© Infobiogen