Needleman–Wunsch algorithm

Needleman–Wunsch algorithm is a dynamic programming algorithm used for the optimal alignment of two sequences. It was developed by Saul B. Needleman and Christian D. Wunsch in 1970 and is primarily used in bioinformatics to align protein or nucleotide sequences. The algorithm identifies the best match between two sequences by inserting gaps in the sequences to achieve the highest possible alignment score.

Overview

The Needleman–Wunsch algorithm is designed to solve the global alignment problem, where the goal is to align two sequences from beginning to end, maximizing the number of matches and minimizing the number of gaps and mismatches. It uses a scoring matrix to keep track of the alignment scores and a traceback procedure to reconstruct the optimal alignment from the completed matrix.

Algorithm

The algorithm consists of three main steps:

1. Initialization: A scoring matrix is initialized with the first row and column filled based on gap penalties.
2. Matrix filling: The rest of the matrix is filled according to a scoring scheme, which typically awards points for matches, deducts points for mismatches, and applies a gap penalty.
3. Traceback: Starting from the bottom-right corner of the matrix, the path of optimal alignment is traced back to the top-left corner.

Scoring System

The Needleman–Wunsch algorithm requires a scoring system to evaluate alignments. This system includes:

• Match score: Points added for matching characters.
• Mismatch penalty: Points subtracted for non-matching characters.
• Gap penalty: Points subtracted for introducing a gap in one of the sequences.

Applications

The Needleman–Wunsch algorithm is widely used in bioinformatics for tasks such as:

• Sequence alignment
• Phylogenetic analysis
• Database searching for similar sequences

Advantages and Limitations

The main advantage of the Needleman–Wunsch algorithm is its ability to find the globally optimal alignment between two sequences. However, its computational complexity is a limitation, making it less practical for very long sequences without modifications or optimizations.

See Also

• Smith-Waterman algorithm
• Dynamic programming
• Sequence alignment
• Bioinformatics