Le but est à présent de trouver une région de forte homogénéité. On va donc privilégier les alignements locaux, et donc empêcher le non-aligné en affectant des poids négatifs en cas de trous ou de misappariements. Ce sont Smith et Waterman qui proposent un algorithme en 1980 [35]. Après avoir réalisé la matrice de score élémentaire, que l'on appellera , on complète la matrice de score avec la formule suivante :
La matrice obtenue permet de repérer les alignements locaux. Et l'algorithme se fait en temps cubique sur la taille des 2 séquences: quadratique pour visiter toutes les cases de la matrice, et linéaire pour calculer .