Aligning Sequences

Global Alignment & Traceback

Traceback turns the filled global alignment matrix into one optimal end-to-end alignment.

highlighted = computed this step

Traceback walks from corner to origin

After the matrix is filled, traceback starts at the bottom-right cell and walks back to the origin, choosing the neighbour that each cell came from.

corner⟶origin\text{corner} \longrightarrow \text{origin}
Global alignment matrixNeedleman-Wunsch scores every prefix pair and keeps the best total.––GCAGCGCATGC0-2-4-6-8-10-21-1-3-5-7-4-120-2-4-6-3031-1-8-5-2120-10-7-4-121-12-9-6-303

The path is the alignment

A diagonal step aligns two bases. A step along an edge puts a gap in one row. Reading those choices forward gives GCATGC aligned with GCA-GC.

GCATGC↔GCA-GC\text{GCATGC} \leftrightarrow \text{GCA-GC}
Traceback alignmentThe traceback path spells the two aligned rows.seq 1GCATGCseq 2GCA-GC

Traceback can choose among ties

Many co-optimal alignments can share the same score. This lesson shows one deterministic traceback: it tries the diagonal move first, then the upper move, then the left move.

tie order=diagonal, upper, left\text{tie order}=\text{diagonal, upper, left}
Global alignment matrixNeedleman-Wunsch scores every prefix pair and keeps the best total.––GCAGCGCATGC0-2-4-6-8-10-21-1-3-5-7-4-120-2-4-6-3031-1-8-5-2120-10-7-4-121-12-9-6-303