Find a middle edge in the alignment graph in linear space. Input: A match score m, a mismatch penalty ?, a gap penalty ?, and two DNA strings s and t. Output: The maximum alignment score of s and t followed by an alignment achieving this maximum score.
The quadratic memory required to store the entire alignment matrix can become overly massive for long DNA strings. However, keep in mind that, during the alignment algorithm, we only need two rows (i.e., linear space) at any given time in order to compute the optimal score. It turns out that we can exploit this phenomenon to compute the entire optimal alignment in linear space as well.