 Smith–Waterman algorithm

The Smith-Waterman algorithm finds an optimal local sequence alignment for a specified additive scoring scheme. For a linear gap penalty $e>0$, a dynamic programming score satisfiesZero permits an alignment to restart; tracing back from the largest entry to zero recovers a highest-scoring segment pair. Every optimal ending must have one of the listed final steps, which proves the recurrence by induction over the table. Optimality concerns this score, not guaranteed biological ancestry. ^[ref]

The Smith-Waterman algorithm is a dynamic programming algorithm used for local sequence alignment in bioinformatics. It helps to find the most similar regions between two biological sequences, such as DNA, RNA, or protein sequences. Unlike global alignment algorithms (like the Needleman-Wunsch algorithm), which align entire sequences, the Smith-Waterman algorithm focuses on identifying the best matching subsequences.