Multiple Sequence Alignment (MSA)

• Multiple Sequence Alignment (MSA) involves computational methods for aligning three or more sequences of DNA, RNA, or proteins, while preserving homology relationships.
• A fundamental assumption of MSA is that each column of the alignment represents a homologous position across the sequences.

Biological Context

• Conserved residues and regions can indicate a shared evolutionary history among the sequences.
• Conserved motifs can predict important functional or structural features of proteins.
• Key applications of MSA include comparative genomics, gene annotation, structure prediction, evolutionary analysis, molecular biology applications, and drug design.

Challenges of MSA

• It can be a tedious analysis with little direct interest.
• Alignment space increases significantly with more sequences.
• Methods are easy to perform but can be sensitive to parameters resulting in poor suboptimal alignments.
• No definitive way exists to assess alignment accuracy.
• Alignments need to be biologically relevant and can not be just mathematically optimal.

Scoring MSAs

• Sum-of-Pair Scoring: An objective scoring metric for MSA algorithms that gives an overall alignment score using a substitution matrix.
• Consistency Scoring: An evaluation of agreement between all pairwise alignments, typically assessed on sequence triplets.
• Log-Expectation Scoring: A method that measures the logarithm of the expected alignment accuracy between all aligned pairs based on posterior probability.

MSA Approaches

• Complete: Dynamic programming to find the most optimal solution, usually using a matrix to produce the ideal result.
• Heuristic: Progressive global strategies like Clustal, iterative MSA using MUSCLE, and combined methods via MAFFT.

Dynamic programming

• While comprehensive, multidimensional dynamic programming requires O(L^N) time, with N sequences and length L, making it impractical for large datasets.

Progressive Alignment Methods

• Aligns pairs of sequences optimally and rapidly using dynamic programming.
• The aligned sequences are treated as a single sequence in the form of a profile.
• This profile is aligned to sequences or other profiles using dynamic programming.
• The methods involve identifying and aligning the most similar sequence pairs to generate a profile, then aligning the subsequent similar pairs or profiles until completion.
• All gaps that were previously inserted are maintained.
• While quicker, progressive alignments are greedy meaning that any initial mistakes propagate through the whole alignment.

Clustal Alignment

• A progressive alignment method with parameters like pairwise global alignments, k-tuple or dynamic programming, and affine gap penalties.
• A distance matrix determines and computes a guide tree using methods like Neighbor-Joining.
• Dynamic Programming (DP) then performs profile alignment using sequence-sequence, sequence-profile, or profile-profile techniques.
• Clustal uses a sum-of-pairs method for scoring, averaging pairwise match scores, with scoring occurring only between, not within, profiles.
• Dynamic substitution matrices are made that uses dynamic weights to reduce that are introduced by evolutionary history.
• Common settings adjusted for Clustal alignments are gap penalties adjusted for more divergent sequences, specific positions, and types of residues.

Key notes for ClustalX

• Highly divergent sequences were delayed until the very end of the process
• Sequences with matching pairwise identity get aligned initially irrespective of their place in the guide tree.
• Weight values are assigned to the amount of weight for transitions in the scoring matrix.
• Negative weights penalize mismatches more than matches, but it can be useful for detecting any biologically significant alignments.

Iterative Multiple Sequence Alignment Methods

• Addresses limitations of progressive MSAs by revisiting and refining the alignment.
• Involves realigning sequences and rebuilding guide trees.
• Aims to maximize the objective function (log-expectation score = Sum-of-Pair scores) to improve overall data quality.
• An example is MUSCLE: Multiple Sequence Comparison by Log-Expectation

MAFFT (Multiple Alignment using Fast Fourier Transform)

• MAFFT offers several multiple alignment strategies classified into progressive refinement methods.
• Includes iterative refinement with a WSP score or consistency scores to improve the progressive alignment.
• Techniques include an FFT approximation to deal with memory restrictions, and improved UPGMA.
• Uses FFT approximation.

Aligning Protein-Coding Sequences

• It is generally more reliable to use translated protein sequence to align data.
• Selection is much more conserved and also has selective constraints.
• Can use protein databases after the DNA is sent back that may identify the initial DNA alignment.

MSA Warning

• MSA algorithms assume that sequences are homologous and will align sequences even if they are not.

Multiple Sequence Alignment (MSA) uses methods for aligning sequences of DNA, RNA, or proteins, preserving homology. Conserved regions indicate shared evolutionary history. MSA has key applications in comparative genomics, gene annotation, structure prediction, and drug design.