Hirschberg algorithm

The Hirschberg algorithm calculates the pairwise sequence alignment and has a linear memory requirement for input . The algorithm developed by Dan Hirschberg in the 1970s uses the method of dynamic programming and the divide-and-conquer principle.

General

The Hirschberg algorithm is a generally applicable and optimal algorithm for finding a sequence alignment. The well-known BLAST algorithm and the FASTA algorithm are only suboptimal heuristics. If you compare the Hirschberg algorithm with the Needleman Wunsch algorithm , the Hirschberg algorithm is less a completely new algorithm, but rather a clever strategy that cleverly uses the Needleman Wunsch algorithm to reduce memory consumption linearize, which is also the special thing about this algorithm: The calculations for a sequence alignment only require a lot of memory space linearly, so the space complexity of the algorithm is in O (n). To calculate an alignment of two character strings and with and , the algorithm has a running time of and a memory consumption of . OBdA should apply in the following so that the space requirement is in . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle m=|x|}$ ${\displaystyle n=|y|}$ ${\displaystyle \Theta (mn)}$ ${\displaystyle \Theta (\min\{m,n\})}$ ${\displaystyle n\leq m}$ ${\displaystyle \Theta (n)}$

The algorithm is used, for example, in bioinformatics to compare different DNA or protein sequences .

In a slightly modified form Hirschbergs algorithm is also used to in a graph parallel connected components with effort to compute processors. ${\displaystyle \Theta (\log ^{2}n)}$ ${\displaystyle \Theta (n^{2})}$

Calculation of the Levenshtein distance on linear storage space

To understand the Hirschberg algorithm, it is first important to understand that the Levenshtein distance can be calculated on a linear storage space:

01  ${\displaystyle T_{0}}$ := 0
02 for j in 1..n loop
03        ${\displaystyle T_{j}}$ :=  ${\displaystyle T_{j-1}}$ +  ${\displaystyle Ins(y_{j})}$
04 end loop
05 for i in 1..m loop
06       s :=  ${\displaystyle T_{0}}$
07        ${\displaystyle T_{0}}$ :=  ${\displaystyle T_{0}}$ +  ${\displaystyle Del(x_{i})}$
08       c :=  ${\displaystyle T_{0}}$
09       for j in 1..n loop
10             c :=  ${\displaystyle \min {\begin{cases}s&+Sub(x_{i},y_{j})\\T_{j}&+Del(x_{i})\\c&+Ins(y_{j})\end{cases}}}$
11             s :=  ${\displaystyle T_{j}}$
12              ${\displaystyle T_{j}}$ := c
13       end loop
14 end loop

In lines 1–4, the one-dimensional field is initialized with n places memory requirements. In line 6, the initialization of the first element is in saved. Then and are initialized with the start value for the next line. The figure below shows a snapshot of a line run. In the inner loop, it always points to the result previously calculated, while the result that is still required is saved in the last line. After line 14, the Levenshtein distance is the result in . ${\displaystyle T}$ ${\displaystyle T_{0}}$ ${\displaystyle s}$ ${\displaystyle T_{0}}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle s}$ ${\displaystyle T_{n}}$

  ε  ${\displaystyle y_{1}}$  ${\displaystyle y_{2}}$  ${\displaystyle y_{3}}$  ${\displaystyle y_{4}}$ ...
ε    0  1  2  3  ...
 ${\displaystyle x_{1}}$   1
 ${\displaystyle x_{2}}$
...

s = 0
c =  ${\displaystyle T_{0}}$ = 1

It should be clear that this calculation can also be performed backwards. The imaginary matrix is ​​not run through from left to right and from top to bottom, but from bottom right to top left:

01  ${\displaystyle T_{n}}$ := 0
02 for j in n-1..0 loop
03        ${\displaystyle T_{j}}$ :=  ${\displaystyle T_{j+1}}$ +  ${\displaystyle Ins(y_{j+1})}$
04 end loop
05 for i in m-1..0 loop
06       s :=  ${\displaystyle T_{n}}$
07        ${\displaystyle T_{n}}$ :=  ${\displaystyle T_{n}}$ +  ${\displaystyle Del(x_{i+1})}$
08       c :=  ${\displaystyle T_{n}}$
09       for j in n-1..0 loop
10             c :=  ${\displaystyle \min {\begin{cases}s&+Sub(x_{i+1},y_{j+1})\\T_{j}&+Del(x_{i+1})\\c&+Ins(y_{j+1})\end{cases}}}$
11             s :=  ${\displaystyle T_{j}}$
12              ${\displaystyle T_{j}}$ := c
13       end loop
14 end loop

Calculation of the alignment on linear storage space

The Divide & Conquer algorithm from Hirschberg calculates an alignment of the character strings and , by combining forward and backward passages with one another (line specifications refer to the pseudocode specified below): ${\displaystyle |x|}$ ${\displaystyle |y|}$

1. If or there is a trivial alignment problem (lines 14-22). A string consisting of only one character must be aligned with another string and an alignment is returned. Is and you go to step 2. ${\displaystyle |x|=1}$ ${\displaystyle |y|=1}$ ${\displaystyle |x|>1}$ ${\displaystyle |y|>1}$

2. A forward pass computes an alignment of and the first half of (lines 27-40). The result of the forward run is a field whose elements indicate the cost of a run from to (with ). ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle T^{\ell }}$ ${\displaystyle (0,0)}$ ${\displaystyle (|x|/2,j)}$ ${\displaystyle 0\leq j\leq n}$

3. A backward pass computes an alignment of with the second half of (lines 42-55). The result is another field , the elements of which indicate the cost of a run back . ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle T^{r}}$ ${\displaystyle (n,m)}$ ${\displaystyle (|x|/2,j)}$

4. In the field elements and the two Levenshtein distances stand for the global alignments of and the respective halves of . The remaining elements of are the distances from the first half to all prefixes of . Correspondingly, the remaining elements of contain the distances from the second half to all suffixes of . ${\displaystyle T^{\ell }(n)}$ ${\displaystyle T^{r}(0)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle T^{\ell }}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle T^{r}}$ ${\displaystyle x}$ ${\displaystyle y}$

5. The Levenshtein distance from zu can now be calculated by walking along the middle row of the alignment matrix and looking for a smallest sum of corresponding - and - elements. If such a minimum sum has been found, a position has been found in the middle line in which the optimal alignment intersects the middle line or the middle of . At this point it is divided into two parts and thus the alignment problem can also be divided into two smaller alignment problems (lines 59-65). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle T^{\ell }}$ ${\displaystyle T^{r}}$ ${\displaystyle x}$ ${\displaystyle y}$

6. Step 1 is called recursively on both parts of and . The two recursive calls return partial alignments that are combined into a single alignment. The alignment is returned (lines 68 and 69). ${\displaystyle x}$ ${\displaystyle y}$

01 --
02 -- Der Divide & Conquer-Algorithmus von Hirschberg zur
03 -- Berechnung des globalen Alignments auf linearem Speicher.
04 --
05 -- Bei  ${\displaystyle m=|x|,n=|y|,n\leq m}$ besitzt der Algorithmus eine Laufzeit von  ${\displaystyle \Theta (nm)}$
06 -- und einen Speicherverbrauch von  ${\displaystyle \Theta (n)}$.
07 --
08 function HirschbergAlignment(x,y : string) return A is
09        function SubAlignment( ${\displaystyle i_{1}}$, ${\displaystyle j_{1}}$, ${\displaystyle i_{2}}$, ${\displaystyle j_{2}}$ : integer) return A is
10                mitte,cut : integer
11                s,c : real
12                 ${\displaystyle T^{\ell },T^{r}}$ : array( ${\displaystyle j_{1}}$.. ${\displaystyle j_{2}}$) of real
13        begin
14                if  ${\displaystyle i_{1}+1=i_{2}}$ or  ${\displaystyle j_{1}=j_{2}}$ then
15                        -- Konstruiere Matrix T für die Teil-Strings
16                        -- x( ${\displaystyle i_{1}+1}$.. ${\displaystyle i_{2}}$) und y( ${\displaystyle j_{1}+1}$.. ${\displaystyle j_{2}}$)
17                        -- Achtung: Nur linearer Speicherplatz erforderlich!
18                        T := ...
19                        -- Berechne triviales Alignment auf Matrix T
20                        -- in linearer Laufzeit
21                        return Alignment(T,x( ${\displaystyle i_{1}+1}$.. ${\displaystyle i_{2}}$),y( ${\displaystyle j_{1}+1}$.. ${\displaystyle j_{2}}$))
22                end if
23
24                mitte :=  ${\displaystyle (i_{1}+i_{2})/2}$
25                -- finde ausgehend von  ${\displaystyle (i_{1},j_{1})}$ den minimalen Pfad
26                -- mit dem Vorwärtsalgorithmus:
27                 ${\displaystyle T^{\ell }(j_{1})}$ := 0
28                for j in  ${\displaystyle j_{1}+1}$.. ${\displaystyle j_{2}}$ loop
29                         ${\displaystyle T^{\ell }(j)}$ :=  ${\displaystyle T^{\ell }(j-1)+Ins(y_{j})}$
30                end loop
31                for i in  ${\displaystyle i_{1}+1}$..mitte loop
32                        s :=  ${\displaystyle T^{\ell }(j_{1})}$
33                        c :=  ${\displaystyle T^{\ell }(j_{1})+Del(x_{i})}$
34                         ${\displaystyle T^{\ell }(j_{1})}$ := c
35                        for j in  ${\displaystyle j_{1}+1}$.. ${\displaystyle j_{2}}$ loop
36                                c :=  ${\displaystyle \min {\begin{cases}T^{\ell }(j)&+Del(x_{i})\\s&+Sub(x_{i},y_{j})\\c&+Ins(y_{j})\end{cases}}}$
37                                s :=  ${\displaystyle T^{\ell }(j)}$
38                                 ${\displaystyle T^{\ell }(j)}$ := c
39                        end loop
40                end loop
41                -- finde minimalen score-pfad nach  ${\displaystyle (i_{2},j_{2})}$
42                 ${\displaystyle T^{r}(j_{2})}$ := 0
43                for j in  ${\displaystyle j_{2}-1}$.. ${\displaystyle j_{1}}$ loop
44                         ${\displaystyle T^{r}(j)}$ :=  ${\displaystyle T^{r}(j+1)+Ins(y_{j+1})}$
45                end loop
46                for i in  ${\displaystyle i_{2}-1}$..mitte loop
47                        s :=  ${\displaystyle T^{r}(j_{2})}$
48                        c :=  ${\displaystyle T^{r}(j_{2})+Del(x_{i+1})}$
49                         ${\displaystyle T^{r}(j_{2})}$ := c;
50                        for j in  ${\displaystyle j_{2}-1}$.. ${\displaystyle j_{1}}$ loop
51                                c :=  ${\displaystyle \min {\begin{cases}T^{r}(j)&+Del(x_{i+1})\\s&+Sub(x_{i+1},y_{j+1})\\c&+Ins(y_{j+1})\end{cases}}}$
52                                s :=  ${\displaystyle T^{r}(j)}$
53                                 ${\displaystyle T^{r}(j)}$ := c
54                        end loop
55                end loop
56                -- finde den Punkt aus  ${\displaystyle j_{1}}$.. ${\displaystyle j_{2}}$ in dem der Minimale Pfad die
57                -- mittlere Zeile schneidet:
58                --  ${\displaystyle cut:=_{def}{\mbox{argmin}}_{j_{1}\leq j\leq j_{2}}(T^{\ell }(j)+T^{r}(j))}$
59                for j in  ${\displaystyle j_{1}}$.. ${\displaystyle j_{2}}$ loop
60                        if j= ${\displaystyle j_{1}}$ then
61                                cut :=  ${\displaystyle j_{1}}$
62                        elsif  ${\displaystyle T^{\ell }(j)+T^{r}(j)<T^{\ell }(cut)+T^{r}(cut)}$ then
63                                cut := j
64                        end if
65                end loop
66                -- Alignment entsteht durch Konkatenation von linkem und
67                -- rechtem Teil-Alignment:
68                return SubAlignment( ${\displaystyle i_{1}}$, ${\displaystyle j_{1}}$,mitte,cut)
69                                 ${\displaystyle \star }$ SubAlignment(mitte,cut, ${\displaystyle i_{2}}$, ${\displaystyle j_{2}}$)
70        end SubAlignment
71        m,n : integer
72 begin
73        m :=  ${\displaystyle |x|}$; n :=  ${\displaystyle |y|}$
74        -- Sonderbehandlung:  ${\displaystyle x}$ ist der leere String und lässt keine Zerteilung zu:
75        if m=0 then
76                return  ${\displaystyle {\begin{pmatrix}-\\y_{1}\end{pmatrix}}\star {\begin{pmatrix}-\\y_{2}\end{pmatrix}}\star \cdots \star {\begin{pmatrix}-\\y_{n}\end{pmatrix}}}$
77        else
78                return SubAlignment(0,0,m,n)
79        end if
80 end HirschbergAlignment

literature

• DS Hirschberg: A linear space algorithm for computing maximally common subsequences . In: Communications of the ACM . tape 18 , no. 6 , 1975, p. 341-343 ( PDF ).
• Chao, KM, Hardison, RC and Miller, W .: Recent developments in linear-space alignment methods: a survey . In: Journal of Computional Biology . No. 4 , 1994, pp. 271-291 ( PDF ).