Incomputer science,Hirschberg's algorithm, named after its inventor,Dan Hirschberg, is adynamic programmingalgorithm that finds the optimalsequence alignment between twostrings. Optimality is measured with theLevenshtein 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 theNeedleman–Wunsch algorithm that usesdynamic programming.^[1] Hirschberg's algorithm is commonly used incomputational biology to find maximal global alignments ofDNA andprotein sequences.

Hirschberg's algorithm is a generally applicable algorithm for optimal sequence alignment.BLAST andFASTA are suboptimalheuristics. If${\displaystyle X}$ and${\displaystyle Y}$ are strings, where${\displaystyle \mathrm{length}(X)=n}$ and${\displaystyle \mathrm{length}(Y)=m}$, theNeedleman–Wunsch algorithm finds an optimal alignment in${\displaystyle O(nm)}$ time, using${\displaystyle O(nm)}$ space. Hirschberg's algorithm is a clever modification of the Needleman–Wunsch Algorithm, which still takes${\displaystyle O(nm)}$ time, but needs only${\displaystyle O(min\{n,m\})}$ 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 thelongest common subsequence between two sets of data such as with the commondiff tool.

The Hirschberg algorithm can be derived from the Needleman–Wunsch algorithm by observing that:^[3]

1. one can compute the optimal alignment score by only storing the current and previous row of the Needleman–Wunsch score matrix;
2. if${\displaystyle (Z,W)=\mathrm{NW}(X,Y)}$ is the optimal alignment of${\displaystyle (X,Y)}$, and${\displaystyle X=X^l+X^r}$ is an arbitrary partition of${\displaystyle X}$, there exists a partition${\displaystyle Y^l+Y^r}$ of${\displaystyle Y}$ such that${\displaystyle \mathrm{NW}(X,Y)=\mathrm{NW}(X^l,Y^l)+\mathrm{NW}(X^r,Y^r)}$.

${\displaystyle X_i}$ denotes thei-th character of${\displaystyle X}$, where${\displaystyle 1⩽i⩽\mathrm{length}(X)}$.${\displaystyle X_{i:j}}$ denotes a substring of size${\displaystyle j-i+1}$, ranging from thei-th to thej-th character of${\displaystyle X}$.${\displaystyle \mathrm{rev}(X)}$ is the reversed version of${\displaystyle X}$.

${\displaystyle X}$ and${\displaystyle Y}$ are sequences to be aligned. Let${\displaystyle x}$ be a character from${\displaystyle X}$, and${\displaystyle y}$ be a character from${\displaystyle Y}$. We assume that${\displaystyle \mathrm{Del}(x)}$,${\displaystyle \mathrm{Ins}(y)}$ and${\displaystyle \mathrm{Sub}(x,y)}$ are well defined integer-valued functions. These functions represent the cost of deleting${\displaystyle x}$, inserting${\displaystyle y}$, and replacing${\displaystyle x}$ with${\displaystyle y}$, respectively.

We define${\displaystyle \mathrm{NWScore}(X,Y)}$, which returns the last line of the Needleman–Wunsch score matrix${\displaystyle \mathrm{S}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}(i,j)}$:

function NWScore(X, Y)    Score(0, 0) = 0 // 2 * (length(Y) + 1) arrayfor j = 1to length(Y)        Score(0, j) = Score(0, j - 1) + Ins(Yj)for i = 1to length(X) // Init array        Score(1, 0) = Score(0, 0) + Del(Xi)for j = 1to length(Y)            scoreSub = Score(0, j - 1) + Sub(Xi, Yj)            scoreDel = Score(0, j) + Del(Xi)            scoreIns = Score(1, j - 1) + Ins(Yj)            Score(1, j) = max(scoreSub, scoreDel, scoreIns)end        // Copy Score[1] to Score[0]        Score(0, :) = Score(1, :)endfor j = 0to length(Y)        LastLine(j) = Score(1, j)return LastLine

Note that at any point,${\displaystyle \mathrm{NWScore}}$ only requires the two most recent rows of the score matrix. Thus,${\displaystyle \mathrm{NWScore}}$ is implemented in${\displaystyle O(min\{\mathrm{length}(X),\mathrm{length}(Y)\})}$ space.

The Hirschberg algorithm follows:

function Hirschberg(X, Y)    Z = ""    W = ""if length(X) == 0for i = 1to length(Y)            Z = Z + '-'            W = W + Yiendelse if length(Y) == 0for i = 1to length(X)            Z = Z + Xi            W = W + '-'endelse if length(X) == 1or length(Y) == 1        (Z, W) = NeedlemanWunsch(X, Y)else        xlen = length(X)        xmid = length(X) / 2        ylen = length(Y)        ScoreL = NWScore(X1:xmid, Y)        ScoreR = NWScore(rev(Xxmid+1:xlen), rev(Y))        ymid =arg max ScoreL + rev(ScoreR)        (Z,W) = Hirschberg(X1:xmid, y1:ymid) + Hirschberg(Xxmid+1:xlen, Yymid+1:ylen)endreturn (Z, W)

In the context of observation (2), assume that${\displaystyle X^l+X^r}$ is a partition of${\displaystyle X}$. Index${\displaystyle \mathrm{y}\mathrm{m}\mathrm{i}\mathrm{d}}$ is computed such that${\displaystyle Y^l=Y_{1:\mathrm{y}\mathrm{m}\mathrm{i}\mathrm{d}}}$ and${\displaystyle Y^r=Y_{\mathrm{y}\mathrm{m}\mathrm{i}\mathrm{d}+1:\mathrm{length}(Y)}}$.

Let

The optimal alignment is given by

 W = AGTACGCA Z = --TATGC-

Indeed, this can be verified by backtracking its corresponding Needleman–Wunsch matrix:

T   A   T   G   C0  -2  -4  -6  -8 -10A-2  -1   0  -2  -4  -6G-4  -3  -2  -1   0  -2T  -6-2  -4   0  -2  -1A  -8  -40  -2  -1  -3C -10  -6  -2-1  -3   1G -12  -8  -4  -31  -1C -14 -10  -6  -5  -13A -16 -12  -8  -7  -31

One starts with the top level call to${\displaystyle \mathrm{Hirschberg}(\text{AGTACGCA},\text{TATGC})}$, which splits the first argument in half:${\displaystyle X=\text{AGTA}+\text{CGCA}}$. The call to${\displaystyle \mathrm{NWScore}(\text{AGTA},Y)}$ produces the following matrix:

T   A   T   G   C    0  -2  -4  -6  -8 -10A -2  -1   0  -2  -4  -6G -4  -3  -2  -1   0  -2T -6  -2  -4   0  -2  -1A -8  -4   0  -2  -1  -3

Likewise,${\displaystyle \mathrm{NWScore}(\mathrm{rev}(\text{CGCA}),\mathrm{rev}(Y))}$ generates the following matrix:

C   G   T   A   T    0 -2  -4  -6  -8 -10A -2 -1  -3  -5  -4  -6C -4  0  -2  -4  -6  -5G -6 -2   2   0  -2  -4C -8 -4   0   1  -1  -3

Their last lines (after reversing the latter) and sum of those are respectively

 ScoreL      = [ -8 -4  0 -2 -1 -3 ] rev(ScoreR) = [ -3 -1  1  0 -4 -8 ] Sum         = [-11 -51 -2 -5 -11]

The maximum (shown in bold) appears atymid = 2, producing the partition${\displaystyle Y=\text{TA}+\text{TGC}}$.

The entire Hirschberg recursion (which we omit for brevity) produces the following tree:

               (AGTACGCA,TATGC)               /               \        (AGTA,TA)             (CGCA,TGC)         /     \              /        \     (AG, )   (TA,TA)      (CG,TG)     (CA,C)              /   \        /   \                  (T,T) (A,A)  (C,T) (G,G)

The leaves of the tree contain the optimal alignment.

• Longest common subsequence

• Sequence alignment algorithms
• Bioinformatics algorithms
• Dynamic programming

• Articles with short description
• Short description is different from Wikidata
• Articles with example pseudocode