What is the Hirschberg algorithm?

The Hirschberg algorithm, named after its inventor Dan Hirschberg, is a dynamic programming algorithm primarily used for sequence alignment in bioinformatics. It was introduced in 1975 as a memory-efficient alternative to traditional algorithms like Needleman-Wunsch and Smith-Waterman, which have quadratic space complexity. Hirschberg’s innovative approach reduces space complexity to linear, making it particularly useful for aligning long sequences efficiently.

Understanding sequence alignment

Before we dive into the Hirschberg algorithm, let’s understand what sequence alignment is. In bioinformatics, we often compare two sequences to see how similar they are.

Sequence alignment of two sequences.
Sequence alignment of two sequences.

Sequence alignment helps us identify regions of similarity and difference between sequences, which can provide insights into their structure, function, and evolutionary relationships.

The need for alignment algorithms

Now, imagine we have two DNA sequences:

Sequence 1: ACAGT

Sequence 2: ACCCT

We want to align these sequences to see where they match and where they differ. This is important because similar sequences may indicate evolutionary relationships or functional similarities between organisms.

The challenge of sequence alignment

The challenge of sequence alignment is that sequences can be long, and aligning them manually can be time-consuming and prone to errors. That’s where alignment algorithms like the Hirschberg algorithm come in handy. They automate the process of aligning sequences, saving time and reducing errors.

The divide-and-conquer approach

The Hirschberg algorithm uses a clever divide-and-conquer approach to align sequences efficiently. Here’s how it works:

  1. Divide: We split the alignment problem into smaller subproblems.

  2. Conquer: We solve the subproblems recursively.

  3. Combine: We combine the solutions to the subproblems to find the optimal alignment of the entire sequences.

Let's look at an example!

Example

Let’s align the sequences “ACAGT” and “ACCCT” using the Hirschberg algorithm:

  1. Divide: We divide the alignment problem into two halves.

    1. Sequence 1: "AC" | "AGT"

    2. Sequence 2: "AC" | "CCT"

  2. Conquer: We recursively align the halves, using a dynamic programming approach (e.g., Needleman-Wunsch or Smith-Waterman algorithm).

    1. Align “AC” and “AC”

    2. Align “AGT” and “CCT”

  3. Combine: We combine the alignments of the halves to find the optimal alignment of the entire sequences.

Initial sequence
Initial sequence
1 of 5

Note: We are not seeing the alignment process in detail as that is out of the scope of this answer. However, to see how to do this using dynamic programming techniques, please refer to Needleman-Wunsch algorithm or Smith-Waterman algorithm.

Let's see its implementation in Python.

Python code

To implement this algorithm in Python, we will use a library called sequence-align. To get started, first, let's install the library using the following commands:

!pip install sequence-align
Command to install library

Now, let's align our sequences used in the example above!

from sequence_align.pairwise import hirschberg
def hirschberg(seq1, seq2, match_score=1.0, mismatch_score=-1.0, indel_score=-2.0):
    def nw_score(x, y):
        m, n = len(x), len(y)
        score = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            score[i][0] = i * indel_score
        for j in range(1, n + 1):
            score[0][j] = j * indel_score
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                match = score[i - 1][j - 1] + (match_score if x[i - 1] == y[j - 1] else mismatch_score)
                delete = score[i - 1][j] + indel_score
                insert = score[i][j - 1] + indel_score
                score[i][j] = max(match, delete, insert)
        
        return score
    def hirschberg_rec(x, y):
        m, n = len(x), len(y)
        if m == 0:
            return "-" * n, y
        elif n == 0:
            return x, "-" * m
        elif m == 1 or n == 1:
            return nw_alignment(x, y)
        i = m // 2
        score_l = nw_score(x[:i], y)
        score_r = nw_score(x[i:][::-1], y[::-1])
        score_r = [row[::-1] for row in score_r[::-1]]
        k = max(range(len(y) + 1), key=lambda j: score_l[-1][j] + score_r[-1][j])
        
        print(f"Dividing at x: {i}, y: {k}")
        xl, yl = hirschberg_rec(x[:i], y[:k])
        xr, yr = hirschberg_rec(x[i:], y[k:])
        
        return xl + xr, yl + yr
    def nw_alignment(x, y):
        m, n = len(x), len(y)
        score = nw_score(x, y)
        align_x, align_y = [], []
        i, j = m, n
        while i > 0 and j > 0:
            current_score = score[i][j]
            if current_score == score[i - 1][j - 1] + (match_score if x[i - 1] == y[j - 1] else mismatch_score):
                align_x.append(x[i - 1])
                align_y.append(y[j - 1])
                i -= 1
                j -= 1
            elif current_score == score[i][j - 1] + indel_score:
                align_x.append('-')
                align_y.append(y[j - 1])
                j -= 1
            else:
                align_x.append(x[i - 1])
                align_y.append('-')
                i -= 1
        while i > 0:
            align_x.append(x[i - 1])
            align_y.append('-')
            i -= 1
        while j > 0:
            align_x.append('-')
            align_y.append(y[j - 1])
            j -= 1
        return ''.join(align_x[::-1]), ''.join(align_y[::-1])
    aligned_seq1, aligned_seq2 = hirschberg_rec(seq1, seq2)
    lcs = ''.join([a if a == b else '' for a, b in zip(aligned_seq1, aligned_seq2)])
    return aligned_seq1, aligned_seq2, lcs
seq1 = "ACAGT"
seq2 = "ACCCT"
aligned_seq1, aligned_seq2, lcs = hirschberg(seq1, seq2)
print("Aligned Sequence 1:", aligned_seq1)
print("Aligned Sequence 2:", aligned_seq2)
print("LCS:", lcs)

The explanation of the code is as follows:

  • Line 1: We are importing the hirschberg function from the sequence_align.pairwise module. This function is part of a library or module designed for pairwise sequence alignment.

  • Lines 2: We define the hirschberg function that takes in two sequences (seq1 and seq2) and scoring parameters (match_score, mismatch_score, indel_score).

  • Lines 3–19: We define another function nw_score which computes the Needleman-Wunsch score matrix for the given sequences.

  • Lines 21–41: We define the recursive function hirschberg_rec that divides the sequences into smaller subproblems and solves them recursively. It also prints the division points for debugging.

  • Lines 43–74: We define the nw_alignment function that performs the Needleman-Wunsch alignment for small subproblems. It uses the score matrix to trace back and build the aligned sequences.

  • Lines 76–78: We call the hirschberg_rec function to get the aligned sequences. We then calculate the longest common subsequence (LCS) by comparing aligned sequences.

  • Lines 80–81: We are defining our first and second sequences (seq1 and seq2) and storing them as strings.

  • Lines 84–87: We call the hirschberg function with seq1 and seq2 as arguments. The function returns the aligned sequences and the LCS, which we print to the console.

Conclusion

In summary, the Hirschberg algorithm is a fundamental tool in bioinformatics, streamlining sequence alignment tasks with its divide-and-conquer approach and recursive methodology. Its efficiency and error reduction make it indispensable for researchers, facilitating quicker and more accurate biological analyses.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved