BLAST কী?

Aligner une requête de $300$ résidus contre une base de $10^{11}$ par programmation dynamique complète coûterait $3\times 10^{13}$ mises à jour de cases par recherche. BLAST (Altschul et ses collègues, 1990) échange un peu de sensibilité contre une vitesse mille fois plus grande en trois étapes : (1) dresser la liste des mots de la requête (trois résidus pour les protéines, onze bases pour l’ADN) et de leurs voisins de score élevé ; (2) balayer la base à la recherche de correspondances exactes de mots — les amorces de recherche ; (3) prolonger chaque amorce dans les deux directions sans brèche jusqu’à ce que le score descende d’une quantité fixée sous son meilleur, en gardant les paires de segments à score élevé (HSP), puis joindre les HSP voisines par une programmation dynamique avec brèches dans une bande étroite. Un vrai homologue contient presque toujours au moins un mot exact de trois résidus en commun ; une ressemblance fortuite en contient rarement un, et n’est jamais prolongée.