Alignment traceback
= Alignment traceback
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 $m+n$ moves are needed after the table is built.