de taille m par une matrice
triangulaire supérieure 
:
Jean-Paul Comet
INRIA Domaine du Voluceau
Rocquencourt BP 105
78153 Le Chesnay cedex
La comparaison et l'alignement de séquences biologiques
(recherche des similarités locales entre deux chaines
de caractères) constituent un point clefs de la biologie
moléculaire. La méthode la plus rigoureuse, reste la
programmation dynamique: sa complexité est quadratique.
Les algorithmes de Needleman-Wunsch et de Smith-Waterman
peuvent être vus comme une suite d'opérations élémentaires
dans l'algèbre (max,+).
Lors de la comparaison de deux séquences A[1,n] et
B[1,m], de longueurs respectives n et m, on itère
n fois la multiplication dans l'algèbre (max,+) d'un
vecteur ligne de taille m par une matrice
triangulaire supérieure :
Le semi-groupe engendré par l'ensemble des matrices
est fini ou projectivement fini. Il s'en suit
que l'ensemble des produits consécutifs des matrices
peut être précalculé et qu'un automate peut être
construit pour répondre au problème de l'alignement de
séquences par programmation dynamique.