 Needleman–Wunsch algorithm

The Needleman-Wunsch algorithm uses dynamic programming to find an optimal global sequence alignment. For a linear gap penalty $e>0$, set $F_{0j}=-je$, $F_{i0}=-ie$ andThe final entry scores the best alignment of both complete sequences. The recurrence follows because its last step must align two symbols or a symbol and a gap. Unlike local alignment, there is no zero restart, so unmatched ends contribute to the score. ^[ref]

The Needleman-Wunsch algorithm is a classic algorithm used for global sequence alignment in bioinformatics. It is particularly useful for aligning two sequences, such as DNA, RNA, or protein sequences, to identify similarities and differences between them. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch in 1970.