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 statistiques 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.
Après une présentation comparative de ces deux approches, nous verrons comment elles peuvent être reconciliées, tant au niveau algorithmique qu'au niveau statistique, grâce aux modèles markoviens d'évolution sous-jacents aux matrices de score.
Références bibliographiques :
