Der Smith-Waterman-Algorithmus optimiert die Kosten der Edit-Operationen nach dem gleichen DP-Schema wie der Needleman-Wunsch- bzw. der Levenshtein-Algorithmus, allerdings werden Einfüge- bzw. Lösch-Operationen am Anfang- bzw. Ende einer Sequenz mit  bewertet und im Backtrace ignoriert. D.h. der Smith-Waterman-Algorithmus berechnet das lokale „sequence alignment“. Seine Laufzeit liegt in .