Multiple Sequence Alignment (MSA)

The primary goal of MSA is to establish homology—the inference that sequences share a common evolutionary ancestor. By aligning three or more sequences, algorithms distinguish between orthologs (speciation events) and paralogs (duplication events). This distinction is critical because structural conservation is far stronger in homologous proteins than in analogous ones. The resulting alignment columns represent positional homology, where each column is hypothesized to derive from the same position in the ancestral sequence. This evolutionary grounding is what allows AlphaFold's Evoformer to extract meaningful structural constraints from sequence data alone.

MSA algorithms rely on two fundamental parameters to evaluate alignment quality. Substitution matrices (e.g., BLOSUM62, PAM250) assign log-odds scores to amino acid replacements based on observed frequencies in trusted alignments. BLOSUM62, the default for most tools, is optimized for detecting distant relationships. Gap penalties control insertions and deletions (indels):

• Affine gap costs: A higher penalty for opening a gap than extending it, reflecting biological reality where a single mutational event can insert or delete multiple residues.
• Terminal gap penalties: Often reduced or eliminated to avoid penalizing incomplete sequences. The interplay between these parameters determines whether the algorithm prioritizes global alignment (end-to-end) or local alignment (conserved motifs).

The most widely used heuristic for MSA construction is the progressive alignment method, implemented in tools like Clustal Omega and MAFFT. The algorithm proceeds in three stages:

1. Pairwise distance calculation: All-vs-all pairwise alignments are computed to generate a distance matrix.
2. Guide tree construction: A neighbor-joining or UPGMA phylogenetic tree is built from the distance matrix.
3. Progressive assembly: Sequences are aligned sequentially following the tree's branching order, starting with the most closely related pairs. The key limitation is its greedy nature—errors introduced at early internal nodes propagate to the final alignment and cannot be corrected later.

To overcome the error-propagation problem of progressive alignment, iterative methods like MAFFT's L-INS-i and MUSCLE incorporate refinement cycles. After an initial alignment is built, the algorithm:

• Re-estimates the guide tree based on the current alignment.
• Re-aligns subsets of sequences using more accurate but computationally expensive algorithms.
• Repeats until convergence or a fixed number of iterations. This approach significantly improves accuracy for datasets with highly divergent sequences. Consistency-based methods (e.g., T-Coffee) further enhance quality by building a library of pairwise alignments and finding the MSA that best agrees with all pairwise constraints.

An MSA is not just a static arrangement of letters—it is a probabilistic model of a protein family. Each column is converted into a Position-Specific Scoring Matrix (PSSM) or profile, encoding the frequency of each amino acid at that position. Profiles are used to:

• Search sequence databases for remote homologs (PSI-BLAST).
• Score how well a new sequence fits the family (profile HMMs in HMMER).
• Generate input features for AlphaFold, where the MSA profile captures coevolutionary information. Profile Hidden Markov Models (HMMs) extend this concept by modeling position-specific insertion and deletion probabilities, providing a more sensitive statistical framework for sequence searching.

The most powerful structural signal embedded in deep MSAs is residue coevolution. When two amino acid positions are in close spatial contact in the folded protein, a mutation at one position often triggers a compensatory mutation at the other to maintain structural integrity. This statistical coupling is detected using methods like Direct Coupling Analysis (DCA) or mutual information with appropriate corrections for phylogenetic noise. The resulting contact predictions—pairs of columns with high coupling scores—provide distance restraints that revolutionized protein structure prediction. AlphaFold2's Evoformer block is explicitly designed to extract and refine these coevolutionary signals from the MSA representation.