Hirschberg's algorithm

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, Hirschberg's algorithm, named after its inventor, <a href="/facts/Dan_Hirschberg/h7jDwjtK">Dan Hirschberg</a>, is a <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that finds the optimal <a href="/facts/Sequence_alignment/p8GQfF7b">sequence alignment</a> between two <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a>. Optimality is measured with the <a href="/facts/Levenshtein_distance/F0otyNSl">Levenshtein distance</a>, 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 <a href="/facts/Needleman%25E2%2580%2593Wunsch_algorithm/B3HJ8xU5">Needleman–Wunsch algorithm</a> that uses <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a>. Hirschberg's algorithm is commonly used in <a href="/facts/Computational_biology/GxgNfwcX">computational biology</a> to find maximal global alignments of <a href="/facts/DNA/nB89Iauz">DNA</a> and <a href="/facts/Protein/Jxmagu3E">protein</a> sequences.
</p>

Hirschberg's algorithm open-in-new

Hirschberg's algorithm