Alignement séquentiel

En bio-informatique, l'alignement de séquences (ou alignement séquentiel) est une manière de disposer les composantes (nucléotides ou acides aminés) des ADN, des ARN, ou des séquences primaires de protéines pour identifier les zones de concordance qui traduisent des similarités ou dissemblances de nature historique. Les séquences alignées sont traditionnellement représentées comme des lignes d'une matrice. Des trous sont disposés de manière à aligner les caractères communs sur des colonnes successives.

L'alignement sert notamment à :

• identifier des sites fonctionnels
• prédire la ou les fonctions d'une protéine
• prédire la structure secondaire (voire tertiaire) d'une protéine
• établir une phylogénie

Lorsque deux séquences dans un alignement partagent un ancêtre commun, les discordances s'interprètent comme des points de mutation ou des lieux d'insertion ou de délétion.

Sommaire 1 Utilisation 2 Représentations 3 Score et matrices de comparaison 4 Alignements locaux et globaux 5 Alignement par paire 5.1 Méthode des matrices par point 5.2 Programmation dynamique 5.3 Méthodes par mots 6 Alignement séquentiel multiple 6.1 Programmation dynamique 6.2 Méthodes progressives 6.3 Méthodes itératives 6.4 Trouver le motif 6.5 Techniques issues de l'informatique 7 Alignement structurel 7.1 DALI 7.2 SSAP 7.3 Extension combinatoire 8 Analyse phylogénétique 9 Méthodes et algorithmes 10 FPGA Version accélérée

Utilisation

Dans la compréhension du fonctionnement de la vie, les protéines jouent un rôle essentiel. On part donc de l'hypothèse que des protéines comportant des séquences similaires risquent fort de posséder des propriétés physico-chimiques identiques. À partir de l'identification de similarités entre la séquence d'une première protéine dont on connaît le mécanisme d'action et celle d'une deuxième protéine dont on ne connaît pas le mécanisme de fonctionnement, on peut inférer des similarités structurelles ou fonctionnelles sur la séquence non connue et proposer de vérifier de manière expérimentale le comportement d'action supposé.

Représentations

Les alignements sont habituellement représentés soit graphiquement soit en format texte. Dans la plupart des représentations des alignements séquentiels, les séquences sont écrites en lignes, disposées pour que les composantes communes apparaissent dans des colonnes successives. En format texte, les colonnes alignés contiennent des caractères identiques ou similaires, indiqués par un système cohérent de symboles. Un astérisque est utilisé pour montrer l'identité entre colonnes. Beaucoup de programmes utilisent de la couleur pour différencier l'information. Pour les ADN ou ARN, l'utilisation de couleur permet de différencier les nucléotides. Pour les alignements de protéines, elle permet d'indiquer les propriétés des acides aminés, ce qui aide à conclure sur la conservation du rôle d'un acide aminé substitué.

Lorsque plusieurs séquences sont mises en jeu, une dernière ligne est ajoutée pour conclure un consensus.

On distingue deux types d'alignements qui diffèrent suivant leur complexité :

• l'alignement par paires qui consiste à aligner deux séquences peut être réalisé grâce à un algorithme de complexité polynomiale. Il est possible de réaliser un alignement :
  • global, c'est-à-dire entre les deux séquences sur toute leur longueur (FASTA)
  • local, entre une séquence et une partie de l'autre séquence (BLAST)
• l'alignement multiple, qui est un alignement global, consiste à aligner plus de deux séquences et nécessite un temps de calcul et un espace de stockage exponentiels en fonction de la taille des données.

Les alignements séquentiels peuvent être fournis dans une large variété de formats de fichiers, dépendant par exemple du programme spécifique utilisé : FASTA format, GenBank, ... Toutefois, dans les laboratoires de recherche, l'utilisation spécifique d'outils techniques peut réduire le choix de format.

Score et matrices de comparaison

La plupart des méthodes d'alignement de séquences biologiques, et en particulier les méthodes d'alignement de séquence de protéines cherchent à optimiser un score d'alignement. Ce score est relié au taux de similarité entre les deux séquences comparées. Il tient compte d'une part du nombre d'acide aminés identiques entre les deux séquences et d'autre part du nombre d'acides aminés similaires sur le plan physico-chimique. Lorsque dans les deux séquences, on trouve ainsi alignés deux acides aminés très proches, comme Lysine (K) et Arginine (R), on parle de remplacement conservatif (les chaînes latérales de ces deux acides aminés portent toutes les deux une charge positive).

Ceci a nécessité la définition formelle d'un score d'identité ou de similarité entre deux acides aminés donnés. Ceci a donné naissance à des Matrices de similarité, M, qui recensent l'ensemble des scores M(a,b) obtenus lorsqu'on substitue l'acide aminé a par l'acide b. Il existe plusieurs de ces matrices 20 x 20 (pour les 20 acides aminés), avec des modes de construction différents. On peut citer les plus classiques :

• Les matrices de Dayhoff, appelées PAM (probability of acceptable mutations), basées sur des distances évolutives entre espèces
• Les matrices de Henikoff, appelées BLOSUM, basées sur le contenu en information des substitutions

Dans chaque famille, il existe plusieurs séries de matrices, de stringence variable, et donc plus ou moins tolérantes aux substitutions d'acides aminés.

Alignements locaux et globaux

Les alignements globaux sont plus souvent utilisés quand les séquences mises en jeu sont similaires et de taille égale. Une technique générale, appelée algorithme de Needleman-Wunsch est basée sur la programmation dynamique.

Les alignements locaux sont plus souvent utilisés quand deux séquences dissemblables sont soupçonnées de posséder des motifs semblables malgré l'environnement. L'algorithme de Smith-Waterman est une méthode d'alignement local générale basée aussi sur la programmation dynamique.

Avec des séquences suffisamment identiques, il n'y aucune différence dans les résultats.

Des méthodes hybrides, des méthodes semi-locales, s'avèrent utiles quand ...

Alignement par paire

Les méthodes d'alignement par paires sont utilisées pour trouver les correspondances entre deux alignements de suites mais ne demandent pas une précision extrême.

Méthode des matrices par point

Programmation dynamique

Méthodes par mots

Alignement séquentiel multiple

Programmation dynamique

Méthodes progressives

Méthodes itératives

Trouver le motif

Techniques issues de l'informatique

Alignement structurel

DALI

SSAP

Extension combinatoire

Analyse phylogénétique

Méthodes et algorithmes

Les alignements par paires peuvent être réalisés de manière totalement rationnelle, en utilisant les algorithmes de programmation dynamique. La méthode la plus utilisée est connue comme l'algorithme de Needleman-Wunsch (J Mol Biol. 1970 Mar;48(3):443-5) qui réalise le meilleur alignement global entre deux séquences. Pour obtenir un alignement local optimal, la méthode a été développée par Smith et Waterman (J Mol Evol. 1981;18(1):38-46). Des implémentations de ces algorithmes se retrouvent notamment dans la suite logicielle OpenSource EMBOSS, respectivement sous les noms "needle" et "water".

FPGA Version accélérée

D'autres travaux récents réalisés par Progeniq démontrent l'accélération de l'algorithme de Smith-Waterman en utilisant une plate-forme de calcul reconfigurable basée sur des morceaux de FPGA. Le FPGA a basé la version des speedups des expositions FPGA d'algorithme jusqu'à 100x au-dessus d'un processeur de 2.2 gigahertz Opteron. White Paper

Algorithme de manipulation de texte
Algorithme de recherche de sous-chaîne	Algorithme d'Aho-Corasick  -  Algorithme de Boyer-Moore  -  Algorithme de Knuth-Morris-Pratt  -  Algorithme de Rabin-Karp
Algorithmes d'alignement de chaînes	Algorithme de Needleman-Wunsch
Algorithmes de mesure de similarité	Distance de Jaro-Winkler  -  Distance de Levenshtein  -  Distance de Hamming

• Portail de la biologie cellulaire et moléculaire