Nous étudions les problèmes mathématiques et algorithmiques liés à l'alignement de séquences. Un modèle construit sur un schéma de scores additif est utilisé par les biologistes pour comparer entre elles des séquences d'ADN ou des séquences de protéines. Dans ce modèle un score est associé à l'appariement de deux lettres de l'alphabet considéré.
Karlin et Altschul ont formalisé cette approche au moyen d'un modèle de marche aléatoire. La loi asymptotique du score de l'alignement optimal est une loi des valeurs extrêumflex;mes. Le modèle utilise la factorisation de Wiener-Hopf et l'identité de Spitzer. Nous donnons une démonstration simple dans le cas où les incréments sont discrets, ce qui est le cas des applications biologiques.
Nous étudions ensuite le cas où l'on cherche à aligner un alignement multiple, composé d'un ensemble de séquences préalablement alignées, et une séquence. Nous considérons alors le cas des protéines et construisons des graphes d'alignement qui modélisent le niveau de conservation des acides aminés pour les positions de l'alignement multiple.
L'alignement optimal recherché correspond à présent à un chemin de score maximal dans ces graphes, pour un choix donné des positions relatives de l'alignement multiple et de la séquence. Nous proposons un algorithme qui est une extension de l'algorithme d'alignement séquence à séquence BLAST. Nous vérifions expérimentalement que la loi des valeurs extrêumflex;mes reste vérifiée dans ce cadre étendu. Nous comparons l'efficacité de ce nouvel algorithme avec celles d'algorithmes classiques pour la recherche de similarités.
Nous appliquons les résultats obtenus à la base de familles de séquences protéiques ProDom. Nous utilisons l'approche de Waterman et Vingron pour montrer que la méthode des approximations Poissonniennes s'applique très efficacement aux calibrations probabilistes des familles de ProDom pour cet algorithme.