Overview
Needleman-Wunsch scores matches, mismatches, and gaps to find the best end-to-end alignment between two sequences.
CoreSource checked
Needleman-Wunsch
Globally aligns two sequences with dynamic programming.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Sequence Alignment
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pattern comparisonalignment scoredynamic programmingsequence alignmentsequence scanpattern statematch verification
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(nm)
Average
O(nm)
Worst
O(nm)
Space
O(nm)
When to Use
- Use Needleman-Wunsch when you need to fill a sequence alignment table.
- Use it for bioinformatics with inputs like two sequences.
- Use it when exact, fuzzy, or structured patterns must be found in sequences.
- Use it when the Sequence Alignment tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when the state table would exceed available memory.
- Avoid it when preprocessing cost is larger than a one-off simple scan.
- Avoid it when the required output is not best global alignment.
What It Does
- Fills a sequence alignment table
- Backtracks to recover a global alignment
Use Cases
- Bioinformatics
- DNA or protein alignment
- Sequence comparison
Inputs
- Two sequences
- Scoring scheme
- Gap penalty
Outputs
- Best global alignment
- Alignment score
Key Formulas (1)
Alignment recurrence
score[i][j] = max(score[i−1][j−1] + match, score[i−1][j] + gap, score[i][j−1] + gap)
score[i][j] = max(score[i-1][j-1] + match, score[i-1][j] + gap, score[i][j-1] + gap)Builds a global alignment score table from neighboring cells.
Pseudocode
- 1.Initialize a scoring matrix with gap penalties
- 2.Fill each cell from diagonal, up, and left choices
- 3.Choose the best score for each prefix pair
- 4.Backtrack from the bottom-right cell
- 5.Return the global alignment
Canonical Example
- Input
- sequence A = "GATT", sequence B = "GCT"
- Output
- a minimum-cost global alignment
- Explanation
- The dynamic program aligns entire prefixes of both sequences, including gaps when needed.
Implementation Notes
- Initialize the first row and column with cumulative gap costs.
- Fill the table from diagonal, up, and left transitions.
- Trace back from the bottom-right cell to recover a global alignment.
Common Pitfalls
- Using local-alignment initialization for a global-alignment problem.
- Mixing gap penalties and substitution scores with inconsistent sign conventions.
- Forgetting traceback ties when multiple optimal alignments exist.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow an alignment matrix and the backtracked best path.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Initialize a scoring matrix with gap penalties
alignment-matrixNotes
Needleman-Wunsch aligns entire sequences, unlike local alignment methods.
Sources (2)
What each reference supports for this entry.
Needleman-Wunsch Alignment
PaperOriginal global sequence-alignment paper supporting dynamic-programming recurrence and traceback.
Open sourceBiological Sequence Analysis
BookSequence-analysis reference covering Needleman-Wunsch dynamic-programming alignment recurrence, scoring model, and traceback behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesDynamic Time Warping
Pattern Matching · Core
Dynamic Time Warping is an alternative to Needleman-Wunsch within the Sequence Alignment family.
Compare with thisAlternative toSmith-Waterman
Pattern Matching · Core
Needleman-Wunsch performs global alignment, while Smith-Waterman performs local alignment.
Compare with thisRelationships
View full relationship pageConceptual neighborLongest Common Subsequence
Both use dynamic programming over sequence pairs.
Alternative toSmith-Waterman
Needleman-Wunsch performs global alignment, while Smith-Waterman performs local alignment.
Related Algorithms
Tags
Pattern MatchingSequence AlignmentDynamic Programming