In computer science, Hirschberg's algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the optimal sequence alignment between two strings.
Optimality is measured with the Levenshtein distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string into the other.
Hirschberg's algorithm is simply described as a more space-efficient version of the Needleman–Wunsch algorithm that uses divide and conquer.
[1] Hirschberg's algorithm is commonly used in computational biology to find maximal global alignments of DNA and protein sequences.
Hirschberg's algorithm is a generally applicable algorithm for optimal sequence alignment.
BLAST and FASTA are suboptimal heuristics.
, the Needleman–Wunsch algorithm finds an optimal alignment in
Hirschberg's algorithm is a clever modification of the Needleman–Wunsch Algorithm, which still takes
space and is much faster in practice.
[2] One application of the algorithm is finding sequence alignments of DNA or protein sequences.
It is also a space-efficient way to calculate the longest common subsequence between two sets of data such as with the common diff tool.
The Hirschberg algorithm can be derived from the Needleman–Wunsch algorithm by observing that:[3]
denotes the i-th character of
denotes a substring of size
, ranging from the i-th to the j-th character of
is the reversed version of
are sequences to be aligned.
are well defined integer-valued functions.
These functions represent the cost of deleting
, which returns the last line of the Needleman–Wunsch score matrix
only requires the two most recent rows of the score matrix.
The Hirschberg algorithm follows: In the context of observation (2), assume that
{\displaystyle {\begin{aligned}X&={\text{AGTACGCA}},\\Y&={\text{TATGC}},\\\operatorname {Del} (x)&=-2,\\\operatorname {Ins} (y)&=-2,\\\operatorname {Sub} (x,y)&={\begin{cases}+2,&{\text{if }}x=y\\-1,&{\text{if }}x\neq y.\end{cases}}\end{aligned}}}
The optimal alignment is given by Indeed, this can be verified by backtracking its corresponding Needleman–Wunsch matrix: One starts with the top level call to
{\displaystyle \operatorname {Hirschberg} ({\text{AGTACGCA}},{\text{TATGC}})}
, which splits the first argument in half:
{\displaystyle \operatorname {NWScore} ({\text{AGTA}},Y)}
produces the following matrix: Likewise,
generates the following matrix: Their last lines (after reversing the latter) and sum of those are respectively The maximum (shown in bold) appears at ymid = 2, producing the partition
The entire Hirschberg recursion (which we omit for brevity) produces the following tree: The leaves of the tree contain the optimal alignment.