L'alignement local multiplie et sans indels est une procédure classique en bioinformatique. Elle consiste à déterminer à partir d'un ensemble de séquences supposées apparentées les "n" facteurs de taille "W" qui présentent une conservation maximale. La mesure de conservation classiquement utilisée est l'entropie relative. Dans la littérature, ce problème est principalement abordé d'un point de vue statistique. Nous proposons de l'approcher sous la forme d'une optimisation combinatoire par voisinage. Nous proposons également une nouvelle fonction objectif : l'entropie recouvrante, laquelle est dédiée aux alignements de séquences protéiques. Cette fonction permet, contrairement à la fonction classique, de prendre en compte le fait que certaines substituions d'acides aminés sont plus probables que d'autres. Cette fonction présente des avantages significatifs, aussi bien du point de vue de la pertinence biologique, que de son effet favorable sur le paysage d'exploration, rendant l'optimisation par le grimpeur considérablement plus efficace.