Multiple Sequence Alignment: Principles, Scoring, and Algorithms

Definition and Evolutionary Context of Multiple Sequence Alignment (MSA)

Definition of Multiple Sequence Alignment: * A collection of three or more protein or nucleic acid sequences that are either partially or completely aligned.
Alignment Logic: * The core objective is to align homologous residues into columns across the entire length of the sequences. * Homology in this context applies in two primary ways: * Evolutionary Sense: Residues descend from a common ancestor. * Structural Sense: Residues occupy equivalent positions in the three-dimensional protein fold.

Properties and Evolution of Protein Sequences and Structures

Non-Uniqueness of Alignments: * For any given protein family, there is not necessarily a single "correct" alignment.
Structural vs. Sequence Divergence: * As protein sequences evolve, their corresponding three-dimensional structures also change. * It may be fundamentally impossible to identify amino acid residues that align properly in a structural sense throughout a multiple sequence alignment.
Numerical Thresholds for Structural Similarity: * For two protein sequences sharing approximately $30\%$ amino acid identity, only about $50\%$ of individual amino acids are usually superposable in their respective 3D structures.

Core Features and Components of Multiple Sequence Alignments

Conservation Patterns: * Specific residues may be highly conserved, such as cysteines involved in the formation of disulfide bridges.
Motifs and Domains: * Alignments often reveal conserved motifs, such as those forming a transmembrane domain.
Secondary Structure: * There may be identifiable and conserved secondary structure features across the sequences.
Indels: * Alignments frequently contain regions with consistent patterns of insertions or deletions (indels).

Critical Uses of Multiple Sequence Alignment

Homolog Detection: * MSA is significantly more sensitive than pairwise alignment for detecting distant homologs.
Database Searching: * A single query sequence can be searched against a database composed of MSAs, such as PFAM.
Regulatory Analysis: * MSA can identify consensus sequences within the regulatory regions of genes.

Mathematical Scoring Models for MSA

Statistical Independence Assumption: * Scoring typically assumes that individual columns within an alignment are statistically independent. * The total score $S(m)$ for a multiple alignment $m$ is the sum of the scores of individual columns $m_i$ : * $S(m) = \sum_{i} S(m_i)$
Minimum Entropy Scoring: * The probability of a column $m_i$ is defined as $P(m_i) = \prod_{a} p_{ia}^{c_{ia}}$ , where $p_{ia}$ is the probability of residue $a$ in column $i$ , and $c_{ia}$ is the count of residue $a$ in that column. * The column score is defined as: $S(m_i) = -\sum_{a} c_{ia} \log(p_{ia})$ * Interpretation: A highly variable column results in higher entropy ( $S$ ). The goal of the alignment algorithm is to minimize the total entropy: $\min \sum_{i} S(m_i)$ .
Sum of Pairs (SP) Scoring: * The column score is the sum of the scores of all possible pairwise alignments in that column: * $S(m_i) = \sum_{k < l} s(m_i^k, m_i^l)$ * Pairwise scores $s(a, b)$ are derived from substitution matrices like PAM or BLOSUM. * Gap Costs: * $s(a, -)$ or $s(-, a)$ represents the gap cost. * The score for aligning two gaps $s(-, -)$ is defined as $0$ .

Progressive Methods for Multiple Sequence Alignment

Concept of Progressive Alignment: * These methods utilize a "guide tree" (related to a phylogenetic tree) to determine the order in which sequences and sub-alignments are combined. * Pairwise alignments are combined one by one to build the final MSA. * Key Softwares: ClustalW and MUSCLE.
Feng-Doolittle Algorithm (Three Stages): 1. Global Pairwise Alignment: Every sequence is aligned with every other sequence using the Needleman-Wunsch dynamic programming algorithm. 2. Guide Tree Construction: Similarity scores are converted to distance scores to build a tree (using clustering methods like UPGMA). 3. Progressive Alignment: Sequences are added to the alignment following the branching order of the guide tree.
The "Once a Gap, Always a Gap" Rule: * In progressive alignment, gaps introduced in early stages are maintained throughout the process as new sequences or groups are added.

Distance Calculations and Guide Trees

Distance Measure Formula: * $D = -\log(S_{eff}) = -\log\left(\frac{S_{obs} - S_{rand}}{S_{max} - S_{rand}}\right)$ * Definitions: * $S_{obs}$ : The observed pairwise alignment score. * $S_{max}$ : The maximum possible score (average score of a sequence aligned to itself). * $S_{rand}$ : The expected score between two random sequences of the same lengths and residue composition.
Guide Tree Case Study: Distantly vs. Closely Related Globins: * In the analysis of human globin (NP_000509), Pan troglodytes (XP_508242), Canis familiaris (XP_537902), Mus musculus (NP_058652), and Gallus gallus (XP_444648): * Human and Chimpanzee (Pan) share a score of $100$ (Distance $0.00000$ ). * Dog (Canis) shows a score of $89$ (Distance $0.04932$ ). * Mouse (Mus) shows a score of $80$ (Distance $0.12075$ ). * Chicken (Gallus) shows a score of $69$ (Distance $0.21259$ ).

Profile Alignment and Scoring

Process of Alignment: * Sequence-to-Group: Align a sequence to each sequence in an existing profile. The highest scoring pairwise alignment determines the final positioning. * Group-to-Group (Profile-to-Profile): Two profiles are aligned without changing the internal alignment of either profile.
Mathematical Representation of Profile Alignment Score: * If one profile contains sequences $1$ to $n$ and the second contains $n+1$ to $N$ : * $\sum_{i} S(m_i) = \sum_{i} \sum_{k < l \le N} s(m_i^k, m_i^l)$ * This expands into three components: * $\sum_{i} \sum_{k < l \le n} s(m_i^k, m_i^l)$ (Intra-profile 1) * $\sum_{i} \sum_{n < k < l \le N} s(m_i^k, m_i^l)$ (Intra-profile 2) * $\sum_{i} \sum_{k \le n, n < l \le N} s(m_i^k, m_i^l)$ (Cross terms between profiles) * The optimal global alignment is found by optimizing the last sum (cross terms) because the first two sums are fixed once the profiles are formed.

ClustalW: Procedural Steps and Parameters

Procedural Steps: 1. Construct a distance matrix for all $\frac{N(N-1)}{2}$ pairs via pairwise alignment. 2. Convert similarity scores into distances. 3. Construct a guide tree via a clustering algorithm. 4. Progressively align at nodes in order of decreasing similarity using sequence-sequence, sequence-profile, and profile-profile methods.
Configurable Parameters in ClustalW Implementation: * KTUP (Word Size): Default. * Window Length: Default. * Score Type: Percent. * Gap Open / Gap Extension: Variable penalties. * Gap Distances: Default. * Matrix: Selection of substitution matrix (e.g., BLOSUM). * Phylogenetic Tree Output: Option to generate tree files.

Iterative Refinement Methods

Addressing the Frozen Sub-alignment Problem: * Progressive alignments suffer because errors made early in the process (sub-alignments) are "frozen" and cannot be corrected later. * Iterative methods resolve this by repeatedly realigning sequences to the group profile.
Iterative Refinement Process: 1. Generate an initial alignment. 2. Remove one or more sequences from the alignment. 3. Realign the removed sequence to the profile of the remaining sequences. 4. Repeat until the score converges or reaches a maximum.
Barton-Sternberg Algorithm: 1. Align the two most similar sequences using pairwise dynamic programming. 2. Progressively align the next most similar sequence to the profile of the previous ones. 3. Once all sequences are included, remove sequence $x_1$ and realign to the profile of sequences $x_2 \dots x_N$ . 4. Repeat the removal/realignment for every sequence in the group. 5. Continue cycles until the score converges.
Common Iterative Programs: * MAFFT * INTERALIGN * PRALINE * MUSCLE

Comparative Evaluation of MSA Algorithms (Globin Example)

Study Objective: Comparing five prominent programs using five globin proteins (Beta globin, Myoglobin, Neuroglobin, Soybean, Rice).
Algorithms Compared: * ClustalW: Traditional progressive alignment. * Praline: Iterative refinement tool. Includes a "Consistency" score row (values ranging from $0$ to asterisks * for high conservation). * MUSCLE: Rapid iterative refinement. * ProbCons: Utilizes probabilistic consistency. * TCoffee: Combines global and local alignments.
Example Focus: The alignment of a critical Histidine ( $H$ ) residue used for oxygen binding. * Conclusion: Programs frequently yield different results (e.g., in Praline vs. ProbCons). There is no single best approach to MSA, as evidenced by the introduction of dozens of programs in recent years.