Alignement de séquences - Définition

Alignement par paire

Les méthodes d'alignement par paires sont utilisées pour trouver les correspondances entre deux alignements de suites mais ne demandent pas une précision extrême.

Méthode des matrices par point

Programmation dynamique

Méthodes par mots

Alignements locaux et globaux

Les alignements globaux sont plus souvent utilisés quand les séquences mises en jeu sont similaires et de taille égale. Une technique générale, appelée algorithme de Needleman-Wunsch est basée sur la programmation dynamique.

Les alignements locaux sont plus souvent utilisés quand deux séquences dissemblables sont soupçonnées de posséder des motifs semblables malgré l'environnement. L'algorithme de Smith-Waterman est une méthode d'alignement local générale basée aussi sur la programmation dynamique.

Avec des séquences suffisamment identiques, il n'y aucune différence dans les résultats.

Des méthodes hybrides, des méthodes semi-locales, s'avèrent utiles quand ...

Alignement structurel

DALI

SSAP

Extension combinatoire

Alignement séquentiel multiple

Programmation dynamique

Méthodes progressives

Méthodes itératives

Trouver le motif

Techniques issues de l'informatique

Méthodes et algorithmes

Les alignements par paires peuvent être réalisés de manière totalement rationnelle, en utilisant les algorithmes de programmation dynamique. La méthode la plus utilisée est connue comme l'algorithme de Needleman-Wunsch (J Mol Biol. 1970 Mar;48(3):443-5) qui réalise le meilleur alignement global entre deux séquences. Pour obtenir un alignement local optimal, la méthode a été développée par Smith et Waterman (J Mol Evol. 1981;18(1):38-46). Des implémentations de ces algorithmes se retrouvent notamment dans la suite logicielle OpenSource EMBOSS, respectivement sous les noms "needle" et "water".

FPGA Version accélérée

D'autres travaux récents réalisés par Progeniq démontrent l'accélération de l'algorithme de Smith-Waterman en utilisant une plate-forme de calcul reconfigurable basée sur des morceaux de FPGA. Le FPGA a basé la version des speedups des expositions FPGA d'algorithme jusqu'à 100x au-dessus d'un processeur de 2.2 gigahertz Opteron. White Paper