Progressive multiple sequence alignment

Sequences, one per line (S1, S2, … from the top)

1 Pairwise distances: align every pair of sequences globally (linear gap: each gap position costs the same) and turn the alignment into a distance d = (mismatches + gap columns) / alignment length. 2 Guide tree: UPGMA repeatedly joins the two closest clusters; the distance from the new cluster is the average over all pairs of sequences across the clusters. 3 Progressive alignment: visit the tree nodes in the order they were created and align the two children at each node. A child is a sequence or a profile, an alignment from an earlier step that is kept fixed (“once a gap, always a gap”); two columns score the sum over all residue pairs between them, with gap against gap = 0. Hover a matrix cell to see how it is computed; click a tab, a distance or a tree node to jump. Keys: → step, ← back, n next stage, f run all, r reset.

Pairwise scores (upper) and distances (lower)

UPGMA guide tree

diagonal: column j of A with position i of B (+σ) from above: position i of B against a gap from the left: column j of A against a gap traceback (ties: diagonal, then up, then left); faded arrows are other ties σ > 0