FASTA

Cet algorithme [34], proposé par Pearson et Lipman en 1988 se déroule en quatre étapes, et se fonde sur une recherche de mots communs (ktup) entre la séquence à analyser et toutes celles de la base. Le k de ktup est la taille des mots à comparer entre les deux séquences, c'est un paramètre que l'on peut choisir entre 1 et 6 (2 pour les protéines, 4 à 6 pour l'ADN).

Pour chaque séquence de la base de données, on la compare à la séquence à analyser en effectuant les 4 étapes suivantes :

1-

On effectue une sorte de dot-plot sur plusieurs lettres : on affecte 1 à la case correspondant à la première lettre de tout ktup commmun à deux séquences. Bien entendu, plus k est grand, plus on est sélectif.

2-

Puis on calcule les scores sur chaque diagonale de la matrice en mettant une pénalité en cas de misappariement et donc en ne prenant pas en compte les délétions et les insertions, puis on garde les 10 diagonales de score maximal.

3-

On utilise alors une matrice de score (PAM250) pour calculer le score sur les dix meilleures diagonales, entre le premier et le dernier appariement, et en utilisant éventuellement un seuil. On obtient un score init 1.

4-

On procède alors au rattachement des diagonales en affectant un score de jonction pour chacune des portions de diagonales, et en autorisant donc les délétions/insertions. On obtient donc un score init n. Ce sont les init i qui seront utilisés pour classer les séquences de la base.

5-

On peut optimiser en utilisant les algorithmes de Needleman Wunsch ou Smith Waterman, mais seulement sur la zone contenant les dix diagonales.

Cet algorithme a toutefois un inconvénient : à la deuxième étape, on a ajouté des régions de faible homologie.