Overview
Smith-Waterman fills a dynamic-programming table with match, mismatch, and gap scores while resetting negative paths to zero.
CoreSource checked
Smith-Waterman
Finds the best local alignment between two sequences.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Advanced
- Family
- Sequence Alignment
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
local alignmentgap penaltydynamic programmingtraceback
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n m)
Average
O(n m)
Worst
O(n m)
Space
O(n m)
When to Use
- Use when text search needs local alignment.
- Use when the input matches the assumptions behind sequence Alignment.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Finds the best local alignment between two sequences
- Uses local alignment and gap penalty to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
Smith-Waterman recurrence
H[i][j] = max(0, H[i−1][j−1] + score, H[i−1][j] − gap, H[i][j−1] − gap)
H[i][j] = max(0, H[i-1][j-1] + score, H[i-1][j] - gap, H[i][j-1] - gap)Keeps only positive local alignment scores.
Pseudocode
- 1.Prepare the inputs and state needed for Smith-Waterman.
- 2.Apply the local alignment step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- two DNA strings with a shared local motif
- Output
- highest-scoring local alignment region
- Explanation
- The dynamic program resets negative scores to zero so unrelated prefixes do not drag down the best local match.
Implementation Notes
- Initialize table borders to zero.
- At each cell, take the maximum of zero, match/mismatch, insertion, and deletion transitions.
- Trace back from the maximum cell until a zero score is reached.
Common Pitfalls
- Forgetting the zero reset that distinguishes local from global alignment.
- Tracing back from the wrong maximum-scoring cell.
- Using scoring parameters that make biologically meaningful matches disappear.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for Smith-Waterman.
pattern-matching-mechanismNotes
Smith-Waterman should be used with the assumptions and tradeoffs of sequence Alignment in mind.
Sources (2)
What each reference supports for this entry.
Smith-Waterman Alignment
PaperOriginal local sequence-alignment paper supporting dynamic-programming recurrence and local traceback.
Open sourceBiological Sequence Analysis
BookSequence-analysis reference covering Smith-Waterman dynamic-programming alignment recurrence, scoring model, and traceback behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborLevenshtein Distance
Both use dynamic programming over edit-like sequence operations.
Alternative toNeedleman-Wunsch
Smith-Waterman computes local sequence alignment.
Related Algorithms
Tags
Pattern MatchingSequence AlignmentDynamic ProgrammingEdit Distance