Les logiciels d'alignement
Alignement global
Méthode employée pour aligner des séquences dont on soupçonne l'homologie.
L'alignement est optimisé sur toute la longueur des séquences.
L'algorithme de référence est celui de Needleman & Wunsh (1970).
Alignement local
Aligne seulement les régions dont le score est supérieur à un seuil
donné. Utilisé lorsque l'on veut aligner deux séquences de taille très différente.
(par ex. dans une recherche de sous-séquence).
Beaucoup plus rapide que l'alignement global.
Smith-Waterman
Programmation dynamique avec arrêt de la procédure sur un critère de
score. Selection du meilleur alignement local.
Fasta (Lipman & Pearson, 1985)
Heuristique: recherche d'abord des segments de longueur k exactement
semblables (k-mots), raccorde ces segments si présents sur une même diagonale où sur
des diagonales proches, puis réaligne la région par programmation dynamique.
Une seule solution par couple de séquences comparées.
Blast (Lipman, Karlin, Altschul)
- k-mots également, mots approchés permis au dessus d'un certain score.
- Pré-codage de la base de données pour recherche plus rapide des k-mots.
- Calcul de la valeur statistique des scores.
- Multiples solutions possibles pour deux séquences comparées.