Store a maximizing predecessor at each dynamic programming table entry. A diagonal predecessor emits a pair of letters; a vertical or horizontal predecessor emits a letter opposite a gap. Construct the columns in reverse and then reverse the output. For global sequence alignment without mismatches, start at the full-prefix entry and stop at the origin. For local sequence alignment without mismatches, start at any largest entry and stop at a zero entry. Each move decreases a prefix index, so at most moves are needed after the table is built.
New to topics? Read the docs here!