Smith–Waterman algorithm

The Smith–Waterman algorithm, described by Temple Smith and Michael Waterman in 1981, finds the best local alignment between two DNA, RNA or protein sequences. Instead of forcing the sequences to match from end to end, it picks out the region where they are most alike, such as a shared domain inside two otherwise different proteins, and it is guaranteed to find the optimal local match for the scoring scheme used.

It fills a scoring grid in the same way as the Needleman–Wunsch algorithm, with one key change: no cell may fall below zero. When the running score would turn negative, it resets to zero, so a poorly matching stretch cannot drag down a good one that follows. The traceback starts from the highest-scoring cell anywhere in the grid and stops at the first zero. In 1982 Osamu Gotoh showed how to handle gap penalties with separate opening and extension costs efficiently, and the combined method is often called Smith–Waterman–Gotoh.

Like its global relative, it takes time proportional to the product of the sequence lengths, which makes exact database searches slow. BLAST trades guaranteed optimality for speed, while versions accelerated with parallel processor instructions or graphics cards keep the exact method practical. It is also built into many tools that map short sequencing reads to a reference genome.