Recherche Bioinformatique Alignement

Recherche en Bioinformatique - Alignement

	Sommaire
	En quoi consiste l'alignement ?
	Cadre formel
	Similarité et homologie
	Matrices de score
	Alignement par paires
	Alignement local et alignement avec gap affine
	Alignement multiple
	Logiciels
	Bibliographie

Cette page est un bref aperçu des notions de base en rapport avec l'alignement de séquences en bioinformatique.

En quoi consiste l'alignement ?

L'alignment de séquences d'ADN ou d'acides aminés est une opération de base en bioinformatique qui a pour but d'identifier des zones conservées entre séquences. L'alignement sert notamment à :

identifier des sites fonctionnels
prédire la/les fonction(s) d'une protéine
prédire la structure secondaire (voire tertiaire) d'une protéine
établir une phylogénie

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 une première séquence dont on connait le mécanisme d'action et une deuxième séquence dont on ne connait 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é.

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

l'alignement par paires qui consiste à aligner 2 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 2 séquences sur toutes leurs longueurs
- local entre une séquence et une partie de l'autre séquence
l'alignement multiple, qui est un alignement global, consiste à aligner plus de 2 séquences et nécessite un temps de calcul et un espace de stockage exponentiel en fonction de la taille des données.

Exemple : soit les séquences S1 = { ACATT } et S1 = { AAGTT }, un alignement de S1 et S2 est par exemple :

S1 :	`A`	`C`	`A`	`-`	`T`	`T`
S2 :	`A`	`-`	`A`	`G`	`T`	`T`
Consensus :	`A`	`.`	`A`	`.`	`T`	`T`

Cadre formel

Définition 1 - Alphabet

Un alphabet

est un ensemble fini de symboles disctincts. Dans le cas de séquences d'ADN ou d'acides aminés on définit le symbole vide ou gap par -.

L'alphabet de l'ADN est composé par les symboles :

-, A, C, G, T

L'alphabet des acides aminés est composé des symboles :

-, A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y

Définition 2 - Séquence, segment

On appelle séquence S une suite ordonnée de caractères pris dans un alphabet

:
S = { x₁, x₂, ... , x_n } On note |S| = n la longueur de la séquence.

on appelle segment tout ou partie d'une séquence.
les séquences étant des mots sur un alphabet on utilise les termes de préfixe et suffixe pour désigner respectivement un segment de début ou de fin de la séquence.

Définition 3 - Alignement

Soit S = { S₁, S₂, ..., S_k } un ensemble de k séquences.
Un alignement de S, noté A(S₁, S₂, ..., S_k) est une matrice :

telle que

avec

telle que , la séquence { a₁^u, a₂^u, ... , a_q^u } dans laquelle on a supprimé tous les gaps correspond à la séquence S_u.

Sommaire

Jean-Michel Richer, 2004