Sequence Alignment Significance, Multiple Sequence Alignment, and Heuristic Methods

Vocabulary flashcards covering alignment significance testing (permutation tests), rules of sequence alignment, multiple sequence alignment (MSA) methods, progressive and iterative heuristics (ClustalW, MUSCLE, MAFFT), and profile scoring functions (PSP and Log-Expectation).

Homology

An evolutionary inference of common descent based on the examination of sequence similarity and its biological meaning. Sequence similarity alone does not guarantee homology, as similarity can also arise from chance, convergence, or analogy.

Sequence Similarity

The observable structural or chemical likeness between two biological sequences, which may result from homology, evolutionary convergence, analogy, or pure chance.

Double Colon (::) in Alignment Output

A notation marker used in alignment programs (such as ALIGN) denoting pure sequence identity between aligned residues.

Single Dot (.) in Alignment Output

A notation marker used in alignment programs indicating that the two aligned amino acids have very similar biochemical properties rather than an identical match.

Permutation Test (Sequence Alignment)

A statistical procedure used to test the null hypothesis by randomly shuffling one sequence, realigning the sequences, recording the score, and repeating this many times to build an empirical score distribution for random sequences of identical length and amino-acid composition.

Permutation Score

An alignment score generated by aligning randomly shuffled sequence data against another sequence to establish background score expectations.

Statistical Significance of Alignment Scores

The likelihood that an alignment did not arise by chance alone; an alignment score falling far beyond the bulk of the permuted background scores indicates statistical significance, whereas a score within the bulk indicates the alignment is likely due to chance.

Affine Gap Penalties

A gap scoring approach based on the rule that the occurrence of an insertion/deletion (gap opening) and the length of the gap (gap extension) are distinct quantities that must be assigned different numerical penalty weights.

End Gap Rule

The guideline stating that if two sequences have no obvious biological relationship at their left and right ends, terminal gaps (end gaps) should not be penalized.

Local vs. Global Alignment Selection Rule

The standard rule indicating that unless two sequences are known to be homologous across their entire lengths, a local alignment is preferable to a global alignment.

Pairwise alignment

2 pairs of sequences make an alignment that maximizes the alignment score by optimizing matches, mismatches, and gaps.

Multiple Sequence Alignment (MSA)

An alignment constructed among three or more sequences simultaneously to resolve pairwise ambiguities, demonstrate sequence conservation over evolutionary time, assemble contigs from multiple reads, or reconstruct phylogenies.

types of multiple sequence alignments (MSA)

1. Rigorous algorithms (dynamic programming)

2. Approximation algorithms (guaranteed to be within X of the answer)

3. Heuristic methods

   1. progressive global alignments

   2. iterative

4. Probabilistic methods (HMM - local alignment)

Dynamic Programming Computational Complexity in MSA

The exponential computational requirement of applying the Needleman-Wunsch dynamic programming algorithm to multiple sequences, which scales as $N^m$, where $N$ is the sequence length (number of nucleotides/residues) and $m$ is the number of sequences.

Approximation Algorithms (MSA)

Multiple sequence alignment algorithms designed to find near-optimal solutions with a mathematical guarantee that the resulting score is within a predefined factor $x$ of the mathematically best answer.

Heuristic Methods (MSA)

Approximation strategies that use practical shortcuts or guided rules rather than full mathematical optimization to assemble multiple alignments rapidly (e.g., progressive alignment, iterative alignment).

Progressive Global Alignment

A heuristic shortcut method (introduced by Higgins & Sharp, 1988) that builds an MSA by :

1. first calculating all pairwise alignments

2. constructing a phylogenetic guide tree from a distance matrix

3. progressively aligning sequences and profiles from leaves to root.

Does the scoring method affect the final alignment during ClustalW

YES: different scoring matrices depending on the distance between the sequences (closely / distantly / related)

pros and cons of progressive global alignment

PROS:

• fast and efficient at forming a sequence

CONS:

• can produce less accurate alignments, sensitive to errors in pairwise alignments.

• ex. if an error is introduced early in the process (pairwise alignment) the error gets locked in forever

example of progressive global alignment

ClustalW

Guide Tree

A tree built from a distance matrix of all pairwise sequence alignment scores used in progressive multiple sequence alignment to determine the hierarchical order in which sequences and profiles are merged.

• The guide tree visually represents how sequences are related and indicates the order in which they should be aligned based on their similarity scores.

• the tree is not a representation of the actual evolutionary history but rather a simplified scheme to facilitate alignment.

Profile-Profile Alignment

• Align a sequence to a pair of sequences that have already been aligned

An alignment method that treats already aligned sequence groups as fixed structures (retaining embedded gaps) and aligns them to another sequence or another aligned group using dynamic programming scoring functions.

Profile Sum of Pair (PSP) Score

A profile comparison score used in CLUSTAL that determines the similarity between column $i$ of alignment $A_1$ and column $j$ of alignment $A_2$ via the formula $PSP(A_1[i], A_2[j]) = \sum_x \sum_y g_{i,x} g_{j,y} \delta(x, y)$, where $g$ represents observed character frequencies and $\delta(x, y)$ is the residue similarity score, ignoring gaps.

does profile-profile alignment scores aligned sites according to PSP?

YES; and it will introduce gaps according too the affine gap penalties

• does not remove gaps already introduced

Log-Expectation (LE) Score

A profile comparison score implemented in MUSCLE that explicitly factors in gap frequencies, defined as $LE(A_1[i], A_2[j]) = (1 - f_i)(1 - f_j) \log \sum_x \sum_y g_{i,x} g_{j,y} \delta(x, y)$, where $f_i$ and $f_j$ are observed gap frequencies in columns $i$ and $j$.

MUSCLE (Multiple Sequence Comparison by Log-Expectation)

An iteratively improved multiple sequence alignment tool developed by R.C. Edgar (2004) that utilizes $k$-mer clustering, UPGMA tree construction, progressive alignment, and tree-dependent iterative profile realignment using log-expectation scoring.

• MUSCLE does NOT ignore gaps and instead uses LE score not PSP

K-mer Clustering (in MUSCLE)

An alignment-free method using words of length $k$ to cluster sequences and build an initial UPGMA tree without requiring an initial round of full pairwise sequence alignments.

Tree-Dependent Refinement (MUSCLE Step 3)

An iterative optimization step in MUSCLE where the multiple alignment is bipartitioned according to branches of a fixed tree, the two sub-profiles are realigned, and changes are kept only if they improve the overall alignment score.

MAFFT

A multiple sequence alignment method developed by Katoh et al. (2002) that uses Fast Fourier Transform (FFT) algorithms to rapidly identify homologous regions.

Clustal Omega

A multiple sequence alignment program developed by Sievers et al. (2011) that utilizes Hidden Markov Model (HMM) profile-profile alignments, providing superior accuracy over older Clustal versions like ClustalW.