Ce site est en cours de reconstruction certains liens peuvent ne pas fonctionner ou certaines images peuvent ne pas s'afficher.

1. Recherche en Bioinformatique - Alignement

Sommaire

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

1.1. 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 :

A 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 $S_1 = { \text"ACATT" }$ et $S_2 = { \text"AAGTT" }$, un alignement de $S_1$ et $S_2$ est par exemple :

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

1.2. Cadre formel

Définition : 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 : Définition 2 - Séquence, segment

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

$$ S = \{ x_1, x_2, ... , 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 : Définition 3 - Alignement

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

$$ (a_u^v)^{1 ≤ u ≤ k}_{1 ≤ v ≤ q} $$

telle que

$$ (a_u^v) ∈ Σ ∪ \{ \text"-" \} $$

avec

$$ max^{u=k}_{u=1}(|S_u|) ≤ q ≤ ∑_{u=1}^{u=k} (|S_u|) $$

telle que $∀u, 1 < u < k$ la séquence $\{ a_1^u, a_2^u, ... , a_q^u \}$ dans laquelle on a supprimé tous les gaps correspond à la séquence $S_u$.