Lecture 4 - Scoring Alignments and Similarity Searches

Bioinformatics Lecture 4: Scoring Alignments and Similarity Searches

• The lecture covers scoring alignments and similarity searches in bioinformatics.
• The workflow presented emphasizes the sequential steps from DNA sequencing to genome annotation and expression analysis, including marker-trait associations, population analysis, and genotyping.
• Dotplots are graphical tools used to visually represent the relationship between two sequences by plotting matching residues in a matrix.

Dotplots

• Definition: A dotplot is a graphical tool used to visualize the relationship between two sequences. Matching residues are plotted in a matrix creating a visual representation of similarity or identity regions across sequences.
• Axes representation: Sequences are assigned to the x and y axes and matches appear as dots where the sequences agree.
• Visualization: Diagonal lines on a dotplot indicate regions of high similarity or identity between sequences.
• Dotplots are useful for spotting duplications, inversions, and repeats within sequences.
• Advantages: Easy visualization of regions shared between sequences, and identification of structural features like repeats, duplications, inversions, or palindromes.
• Software: MUMmer is a widely used tool for creating dotplots, particularly in genome comparisons. Other tools such as Genard Dotter also allow for the creation of the dotplots.
• Limitations: Limited scalability as the matrix size increases exponentially, resulting in cluttered displays, sensitivity to noise in repetitive regions, and lack of quantitative measures.

Sequence Similarity

• Definition: Sequence similarity refers to the degree of likeness between two nucleotide or protein sequences. Similarity can be quantified by various methods depending on the type of sequence comparison.
• Methods to assess sequence similarity:
  • Hamming distance: Measures the number of mismatches between sequences of equal length.
  • Edit Distance/Levenshtein Distance: Measures the minimum number of operations (insertions, deletions, or substitutions) required to transform one sequence into another. Accounts for indels and substitutions.

Scoring Matrices

• Definition: Matrices that assign scores to different types of matches and mismatches based on the evolutionary or functional significance of the changes. They're commonly used in protein alignments.
• Examples: PAM (Point Accepted Mutation): Used for mutations over evolutionary time. BLOSUM (Blocks Substitution Matrix): Used for distant sequence relationships.

DNA Alignment Scoring

• Definition: DNA alignment scoring refers to assigning numerical values to matches, mismatches, and gaps. It aims to represent and maximize the best alignment with a balancing act between matches and differences.
• Importance: Provides a quantitative way to compare sequences, and measure similarity that helps identify evolutionary relationships and functional similarities between sequences.
• Identity matrix: The simplest scoring matrix that assumes all mismatches and mutations are equally likely.
• Transition-Transversion matrix: A more biologically-informed matrix that gives higher scores to transitions (changes within the purine or pyrimidine class).
• Gap Penalties: Penalizes gaps (insertions and deletions) to prevent introducing too many gaps in the alignment.
  • Constant gap penalty: A fixed penalty for every gap
  • Affine gap penalty: Penalizes gap initiation more than gap extension. This encourages fewer but longer gaps.

PAM Matrices

• Definition: PAM matrices measure the evolutionary distances using the number of mutations that have occurred in one amino acid per 100 amino acids. This matrix measures the evolutionary distance.
• Origin: 1,572 mutations observed within 71 closely related protein sequences (≥85% sequence identity) were used to build the PAM1 matrix.
• Usage: More commonly used for aligning sequences that are more closely related. For more distantly related sequences, PAM250 is commonly used.
• Key Concept: Specific mutations occurring at higher probability over time help identify a greater distance of evolutionary time between sequences.

BLOSUM Matrices

• Definition: BLOSUM matrices generate and use alignments from highly conserved regions of proteins.
• Key Concept: Created from regions (blocks) of high conservation (no significant changes over time) within proteins, meaning that these regions have been preserved in evolution, and are typically used to detect more distant evolutionary relationship.
• Usage: Primarily used to align more distantly related protein sequences. Lower BLOSUM numbers (eg, BLOSUM45) are used to compare more distantly related sequences whereas higher BLOSUM numbers (e.g., BLOSUM80) are suitable for more closely related sequences, and BLOSUM62 is the most widely used matrix.

BLAST (Basic Local Alignment Search Tool)

• Definition: A widely used algorithm that searches a database of sequences to find similar or homologous regions to a query sequence, crucial for identifying homologous sequences and assessing biological relevance.
• Works by finding potential matches in the Database (hits or Seeds) then extending them and building a HSP.

Multiple Sequence Alignment (MSA)

• Definition: Aligns three or more biological sequences to identify similar and conserved regions across sequences; revealing evolutionary relationships and functional elements.
• Objectives: Maximize similarity, reveal evolutionary relationships, and identify conserved regions for functional/structural understanding.
• Applications: Phylogenetics, functional analysis, and protein structure prediction.

Methods for MSA

• Progressive Alignment: Aligns sequences pairwise starting with those with the highest similarity. Aligns progressively, and faster but sensitive to initial alignment errors which propagate as more sequences are aligned. (e.g., ClustalW)
• Iterative Alignment: Refines an initial alignment by repeatedly realigning subsequences to improve overall score. More accurate than progressive, but computationally more intensive. (e.g., MUSCLE).
• Consensus-Based Alignment: Combines results from different alignment methods, and weights their reliability. More reliable when aligning divergent sequences but can be slower due to multiple alignment steps. (e.g., T-Coffee).

Challenges in MSA

• Gaps and Indels: Introducing gaps to incorporate or accommodate insertions/deletions, especially within sequences with varying lengths.
• Divergence: Large evolutionary distances may create a significant challenge when aligning divergent sequences.
• Computational Complexity: Aligning many sequences computationally demands more intensive calculations and processing time.

Global and Local Alignments

• These are two approaches to sequence alignment that have distinct algorithms, advantages, and usage scenarios. Global alignment (e.g., Needleman-Wunsch) is for similar-sized sequences expected to align across the entire length. Local Alignment (eg Smith-Waterman) is more flexible, and is to find and align similar segments within the sequence, even if the sequences have large dissimilar segments.

Needleman-Wunsch

• A general method of performing sequence comparison.
• Goal: To maximize the alignment score between two sequences.
• Finds the best global alignment, including all bases/amino acids from both sequences.
• Two-step dynamic programming approach:
  • All pairs of residues are scored in a matrix using a scoring system.
  • The highest scoring path is the best alignment.

Smith-Waterman

• A dynamic programming approach for identifying local regions of similarity.
• Goal: Maximizes the alignment score for local regions; rather than finding alignment across the entirety of a sequence.
• Key feature: Allows for gaps and mismatches and is optimal for substrings, ideal for dissimilar sequences.

Test your knowledge on sequence similarity and alignment algorithms in bioinformatics. This quiz covers various methods such as Hamming Distance, Needleman-Wunsch, and Smith-Waterman algorithms, as well as their applications and scoring matrices. Challenge yourself with matching terms to definitions and identifying key concepts.