Multiple Sequence Alignment (MSA)

• Multiple Sequence Alignment(MSA) is a set of computational approaches aligning three or more sequences, preserving homology relationships among DNA, RNA, or proteins.
• The fundamental assumption is that each MSA column represents a homologous position.

Biological Context

• Conserved residues and regions suggest a shared evolutionary history.
• Conserved motifs can predict critical functional or structural protein features.
• MSAs are key for comparative genomics, gene annotation, structure prediction, evolutionary analysis, molecular biology applications (like primer prediction), and drug design.

Challenges

• Performing MSAs can be a nuisance analysis, requiring performance but with little direct interest.
• Alignment space dramatically increases with the number of sequences.
• It can be easy to perform poorly; methods are sensitive to parameters.
• No single correct alignment exists, making it difficult to know how to determine if an alignment has been performed correctly.
• Alignments need to be biologically meaningful, going beyond mere mathematical optimization.

Scoring MSAs

• MSAs can be scored with methods like sum-of-pair scoring, consistency scoring, and log-expectation scoring.

Sum-of-Pair Scoring

• It serves as an objective function for many MSA algorithms.
• This scoring assesses the quality of each alignment column.
• Higher scores indicate a better alignment.
• Sum-of-pairs scoring uses a substitution matrix.
• MSAs maximize their total alignment score by maximizing the sum-of-pairs score of each column.

Consistency Scoring

• It evaluates the degree of agreement (i.e., consistency) between all pairwise alignments.
• Evaluation is typically based on all sequence triplets: if sequence A aligns to B and B aligns to C in a region, A should also align to C in that region.
• Inconsistent diagonals would affect scoring depending on the alignment of particular sequences.

Log-Expectation Scoring

• Measures the logarithm of the expected alignment accuracy between all aligned sequence pairs.
• Alignment accuracy relies on the posterior probability (confidence) of observed residue pairs being correctly aligned.
• Posterial probabilities are based on a substitution matrix normalized across all possible substitutions.
• It provides a probabilistic framework for evaluating alignment quality.

MSA Approaches

• Approaches include complete methods such as Dynamic Programming, and Heuristic methods which include Progressive global via Clustal, Iterative MSA via MUSCLE, and combined methods via MAFFT.

Multidimensional Dynamic Programming

• Requires the use of N sequences of length L.
• Needs O(LN) time to produce a dynamic programming matrix.
• If sequences of L = 1000 residues and only N = 2 can be processed in 1 msec, this isn't practical.

Progressive Alignment

• Any pair of sequences can be optimally and rapidly aligned via dynamic programming.
• After the alignment is complete, the aligned set of sequences can be treated as one sequence, referred to as a profile.
• Profiles are optimally and rapidly aligned to other sequences or profiles via dynamic programming.
• The steps include identifying and aligning the most similar pair of sequences to create a profile, then identifying and aligning the next most similar pair of sequences or profiles to create a new profile, and repeating this process until complete.
• When profiles are aligned, all gaps inserted in previous steps are maintained.
• Progressive alignments find the best immediate solution at each step without concern for the overall problem.
• An example of immediate solutions is made regardless of later consequences; therefore, greedy algorithms may not find the globally optimal solution.
• Early mistakes get propagated throughout the rest of the alignment.

Clustal Alignment

• It involves computing all pairwise global alignments using a fast k-tuple or slow dynamic programming matrices with affine gap penalties to calculate pairwise distances.
• It is followed by using a distance matrix to calculate a guide tree, using methods like Neighbor-Joining, or Midpoint rooting
• The order of alignment is determined based on the alignment with another sequence, followed by another.
• DP profile alignment is performed with sequence-sequence, sequence-profile, or profile-profile alignments.
• With Clustal, existing gaps are fixed in a profile with new gap penalties.
• Sum-of-pairs scoring is used to score each alignment column.
• The pairwise scores average to determine the match score.
• Scoring only occurs between profiles, with within-profile scores being 0.
• It uses dynamic substitution matrices and distances among sequences to determine the substitution matrix.
• Weights are assigned to sequences to reduce biases caused by evolutionary history.
• Gap penalties include gap opening penalty and extension penalty. -The gap opening increases for more divergent sequences. -The Extension penalty varies based on differences in length.
• Position specific gap penalties lower OP and EP if a gap already exists at a given position and increases if gaps nearby.
• Residue specific gap penalties adjust OP adjusted by residue and OP decreases within runs of hydrophilic residues and are associated with loops.
• The lowest penalties relate sequences, gaps, hydrophilic stretches.
• Highest penalties occur within 8 aaf gap.
• The rest of variation relates to the residue specific gap penalties.

Iterative Alignment Methods

• Iterative methods revisit the initial refined alignments:
• By realigning sequences
• Rebuilding guide trees
• Maximize the objective function
• They reduce the impact of early errors and improve overall alignment quality.
• MUSCLE offers an iterative method for improving alignment.
• By Log-Expectation.

Combined Methods

• MAFFT (Multiple Alignment using Fast Fourier Transform) is a multiple sequence alignment program for Unix operating systems, offering a range of multiple alignment methods, classified into three types to reach a tradeoff between speed and accuracy.
• The first one is the progressive method, the second is the iterative refinement method with WSP score and third, is the iterative refinement method using both WSP and consistently scores..
• The order of speed is a>b>c whereas the order of accuracy is a0 by default) of close homologs (E=1e−10 by default) of the input sequences.
• Align the input sequences and homologs all together using the L-INS-i strategy.
• Remove the homologs.

Protein-Coding Sequences

• Proteins are usually more reliably aligned than DNA due to the amino acid alphabet being larger and a slower mutational saturation.
• Proteins are often more conserved than DNA sequences by retaining many coding sequence mutations that won't change the protein.
• This leads to more amino acid substitutions that are physiochemically conservative due to selective constraints.
• Translating DNA sequences into protein sequence and then back-translating permits greater conservation to allow for better alignments and allows to insert the gap only between codons.

Multiple Sequence Alignment (MSA) aligns three or more sequences to identify homology. Conserved residues suggest shared evolutionary history and predict protein features. MSAs are crucial for comparative genomics, gene annotation, and evolutionary analysis.