Hirschberg's algorithm, named after its inventor Dan Hirschberg, is a dynamic programming algorithm that finds the optimal sequence alignment between two strings, measuring optimality by Levenshtein distance, which quantifies the total cost of the insertions, replacements, deletions and null actions needed to transform one string into another. It is a more space efficient variant of the Needleman-Wunsch algorithm and is widely used in computational biology to find maximal global alignments of DNA and protein sequences.
Facts
Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 2 Classification
Design Technique Connections
In Field
Source Hirschberg's algorithm (Wikipedia)
Uses Design Technique
Sources
1. Hirschberg's Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/Hirschberg's_algorithmQuote, https://en.wikipedia.org/wiki/Hirschberg's_algorithm
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.
2. Hirschberg's algorithm (Wikipedia)
Article body
Hirschberg's algorithm is a clever modification of the Needleman-Wunsch Algorithm, which still takes O ( n m )
In Field: Algorithms and Complexity Theory, Lead sentence
Hirschberg's algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the optimal sequence alignment between two strings.
In Group: Edit Distance and Sequence Alignment Algorithms, Lead section
finds the optimal sequence alignment
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.