Overview
Hirschberg's algorithm uses forward and backward dynamic-programming rows to find a split point, then recursively reconstructs an optimal alignment with linear space.
CoreSource checked
Hirschberg Algorithm
Computes sequence alignment using divide and conquer to reduce memory.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Dynamic Programming
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
sequence alignmentdynamic programmingpattern matching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)
When to Use
- Use when an optimal alignment is needed but the full dynamic-programming table is too large.
- Use for long sequences where linear space matters more than implementation simplicity.
When Not to Use
- Avoid when the full DP table is small enough and simpler traceback is preferable.
- Avoid when affine-gap or richer scoring models are needed without adapting the recurrence.
What It Does
- Hirschberg Algorithm uses dividing the dynamic-programming table to recover an alignment in linear space for sequence alignment
- Organizes the work around sequence alignment and dynamic programming.
Use Cases
- Production and research workloads requiring dynamic programming via Computes sequence alignment using divide and conquer to reduce memory.
- Dynamic Programming pipelines where O(n + m) time and O(n + m) space fit system constraints.
- Engineering comparisons against Gotoh Algorithm and Affine Gap Alignment when tuning dynamic programming.
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Pseudocode
- 1.If either sequence is small, solve directly
- 2.Split the first sequence in half
- 3.Compute forward scores for the left half
- 4.Compute backward scores for the right half
- 5.Choose the second-sequence split maximizing combined score
- 6.Recurse on both halves and concatenate alignments
Canonical Example
- Input
- align 'AGT' with 'AT'
- Output
- alignment such as A G T / A - T
- Explanation
- The split row identifies where the optimal alignment crosses the midpoint.
Implementation Notes
- Write a helper that computes only the final DP row.
- Use recursion to split one sequence and reconstruct both halves.
- Test against a full-table Needleman-Wunsch implementation.
Common Pitfalls
- The split point must combine forward and backward scores consistently.
- Base cases for empty and single-character sequences must be exact.
- Linear space does not remove the quadratic time cost.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow dividing the dynamic-programming table to recover an alignment in linear space on a small sequence alignment example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: If either sequence is small, solve directly
pattern-matching-mechanismNotes
Hirschberg reduces memory for global alignment reconstruction, but it still performs dynamic-programming work.
Sources (2)
What each reference supports for this entry.
Hirschberg Algorithm
PaperOriginal reference for linear-space divide-and-conquer sequence alignment.
Open sourceBiological Sequence Analysis
BookSequence-analysis reference covering Hirschberg Algorithm dynamic-programming alignment recurrence, scoring model, and traceback behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toAffine Gap Alignment
Pattern Matching · Extended
Both address sequence alignment, but they make different modeling or performance tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toGotoh Algorithm
Both address sequence alignment, but they make different modeling or performance tradeoffs.
Alternative toAffine Gap Alignment
Both address sequence alignment, but they make different modeling or performance tradeoffs.
Conceptual neighborLevenshtein Distance
Both use dynamic programming ideas for related sequence alignment problems.
Related Algorithms
Tags
Pattern MatchingStringsDynamic Programming