Dominique Cellier

L’alignement de séquences biologiques (ADN, ARN, EST, protéines) constitue en général une première étape fondamentale dans l’analyse de ces dernières : recherche de séquences homologues dans les banques de données, détection de structures, de domaines ou de fonctions par génomique comparative, reconstruction phylogénétique.

L’approche classique de l’alignement de deux séquences est de type combinatoire : à partir d’un système de score nucléique ou de matrices de similarité protéique (PAM, BLOSUM) déterminer l’alignement (global ou local) de score maximum. Deux algorithmes de programmation dynamique (Needleman & Wunsch et Smith & Waterman) permettent de construire de manière exacte cet alignement optimal et des résultats sur les valeurs extrèmes permettent d’en déterminer la signification statistique (formule de Karlin, Z-score), base des programmes d’interrogation des banques de données (BLAST, FASTA).

Une alternative à cette approche est le développement de méthodes probabilistes dont les plus fréquentes actuellement sont celles d’alignement par chaînes de Markov cachées. Dans ce cas, pour un modèle ajusté au cours d’une phase d’apprentissage, l’alignement local ou global s’obtient par l’algorithme de Viterbi.