Multiple Sequence Alignment (MSA): Needleman-Wunsch and Progressive Guide Trees
How progressive multiple sequence alignment works: pairwise distance matrices, UPGMA guide trees, affine gap penalties and consensus conservation symbols.
Progressive multiple sequence alignment builds alignments sequentially using a guide tree derived from all-versus-all pairwise similarity scores.
**1. Pairwise Distance Computation:** Before aligning multi-sequence sets, every pair of sequences is aligned using global Needleman-Wunsch dynamic programming. The fraction of mismatches forms a distance matrix: D_ij = 1 − (identical residues / alignment length).
**2. Guide Tree Construction (UPGMA):** The distance matrix is clustered into a phylogenetic guide tree using the Unweighted Pair Group Method with Arithmetic Mean (UPGMA). Closely related sequence clusters are merged first.
**3. Affine Gap Penalties:** Inserting a biological gap reflects a single insertion/deletion event, while extending that gap is much more probable. We use an affine gap cost model: Penalty = g_o + (k − 1) × g_e, where g_o is the gap-opening penalty (typically 10.0) and g_e is the gap-extension penalty (typically 0.5).
**4. Consensus Conservation Notation:** - Asterisk (*): Exact match in 100% of aligned sequences. - Colon (:): Conservation across strong physical-chemical properties (e.g. basic Lys/Arg, acidic Asp/Glu). - Period (.): Conservation across weakly similar amino acid side chains.
**In SciKeep:** SciKeep's MSA engine runs Needleman-Wunsch with Gotoh affine gap penalties and a UPGMA guide tree directly in your browser, computing conservation graphs and exporting standard aligned FASTA.
**Not Clustal itself:** the Clustal programs are a family (ClustalW, ClustalX, Clustal Omega) that differ from this design — ClustalW builds its guide tree by neighbour-joining and aligns profiles against profiles, and Clustal Omega uses mBed guide trees and HMM profile alignment. SciKeep borrows only the Clustal *conservation notation* (*, :, .). For deep or highly divergent alignments, use Clustal Omega or MAFFT.