Bioinformatics: Sequence Alignment Techniques

Bioinformatics Overview

• Bioinformatics uses computational methods to analyze biological data.
• It involves computational biology, data analysis, and more.
• Key areas of study include sequence analysis, multiple sequence alignments (PSI-BLAST, Clustal-W), and genome annotation (HMM).

Sequence Analysis

• Methods for global and local sequence alignment are important (Needleman-Wunsch, Smith-Waterman).
• Penalty functions and substitution matrices play a crucial role in defining alignments.
• Heuristic methods like BLAST (Basic Local Alignment Search Tool) are used for faster sequence analysis.
• Genome annotation using Hidden Markov Models (HMMs) also plays a role.

Goals of the Module

• Understanding sequence analysis methods: global and local alignments, penalty functions, and substitution matrices
• Learning heuristic methods for sequence analysis (BLAST)
• Understanding multiple sequence alignments (PSI-BLAST, Clustal-W)
• Mastering genome annotation using HMMs

Challenges in Computational Biology

• Genome Assembly: Reconstructing the complete genome sequence from fragmented data.
• Gene Finding: Determining the location and boundaries of genes within a genome.
• Sequence Alignment: Comparing and aligning sequences to identify similarities and differences
• Database Lookup: Searching databases for similar sequences or structures.
• Comparative Genomics: Studying the evolution and relationships between genomes
• Evolutionary Theory: Using evolutionary relationships to provide insight into structure and function
• Gene Expression Analysis: Studying the activity of genes and their interactions.
• RNA transcript: Analyzing RNA information for gene expression
• Cluster Discovery: Grouping similar sequences or data points.
• Gibbs Sampling: Used to analyze and sample from probability distributions.
• Protein network analysis: Examining interactions between proteins
• Regulatory network inference: Identifying relationships between genes and gene regulatory factors
• Emerging Network properties: Understanding properties of complex biological networks.

Evolution of Functional Elements

• Evolutionary analysis reveals preserved functional elements.
• Specific examples of sequences and their functional elements
• Tools like those developed by Kellis et al. (Nature 2003) are used in the analysis of conserved sequences.

Gene Alignment

• Methods for aligning genes are critical for understanding evolutionary relationships and gene function.
• Aligning sequences involves identifying similarities and differences between the sequences.
• This process is often guided by established biological principles (e.g., mutations, deletions, insertions).

Genomes Change Over Time

• Mutations (changes in single nucleotide).
• Deletions.
• Insertions.

Goal of Alignment

• Determining the sequence variations (edit operations) between two sequences.

Formalizing the Problem

• Defining operations (insertion, deletion, mutation).
• Establishing optimality measures: minimum number of edits or minimum cost .
• Designing applicable algorithms

Dotplots in Bioinformatics

• Dotplots are visual tools for identifying sequence similarities.
• Two sequences are plotted on a grid.
• Diagonal lines in the dotplot indicate regions of similarity.
• Different types (e.g., perfect match, repeats, etc.)

Formulations of String Similarity

• Longest Common Substring: Finding the longest contiguous matching sequence in two strings (no gaps).
• Longest Common Subsequence: Finding the longest matching sequence in two strings (gaps are allowed).

Sequence Alignment

• Varying gap penalties (linear, affine) affect how gaps are treated in sequence alignments.
• Gap penalties are important to account for the varying costs of insertions and deletions in a sequence.
• This variation from uniform penalties to varying costs accounts for actual genome variation.

Substitution Matrices

• PAM (Percent Accepted Mutations) substitution matrices.
• BLOSUM (BLOcks SUbstitution Matrix) substitution matrices.
• Different matrices are needed to account for the different evolutionary relationships between sequences

Scoring Matrices

• Aligned sequences are rated based on the sum of positional scores from a matrix
• They derive from the observed mutations and similarities between amino acids sequences.

Position-Specific Scoring Matrices (PSSMs)

• Position-specific scoring matrices (PSSMs) contain the probability of amino acid (or nucleotide) occurrence at each position of a multiple sequence alignment
• Calculating and using PSSM involves defining a method for assigning scores
• A specific method of determining the scores is to calculate the log-odds
• These calculated values are used in calculations to see how a particular amino acid or nucleotide fits into the matrix

Heuristic Methods

• BLAST is a heuristic method, which means it uses approximations to produce results relatively quickly
• It does so by searching databases for sequences with significant similarity to a query sequence (the unknown)
• BLAST allows for faster database searches compared to global alignment

BLAST Algorithm

• This is a two-step heuristic algorithm:
  • Identifying potentially significant regions (words) within the query sequence.
  • Identifying alignments within the word list to those in the database.

Multiple Sequence Alignments (MSAs)

• Methods for comparing multiple sequences simultaneously
• Tools like ClustalW use progressive alignment that builds on phylogenetic trees
• The goal is to identify regions of conservation.

Annotation of Genomes

• Identifying coding regions and functional elements of genomes.
• Methods often are based on Hidden Markov models (HMMs).

Eukaryotic Gene Structure Features

• Exon structure and functions in eukaryotes
• The elements and role of start codons (ATG sequence)
• The elements and function of stop codons (TAG/TGA/TAA)
• Role of splice sites
• The general structure of a eukaryotic gene

Gene Prediction

• Predicting coding regions from genome sequences.
• Methods are based on characteristics of coding segments such as specific nucleotide sequence patterns, such as start and stop codons, or characteristic length changes. (HMMs).

Content Regions

• Features of the sequences in coding regions
• Nucleotide order and how they relate to gene function
• Probability of certain hexanucleotides found in coding sequences

Generalized HMMs (GHMMs)

• GHMMs are complex HMMs that extend the simple concept of HMMs by explicitly modeling the variable lengths of relevant sequence features
• These can be used to define and predict segments within genetic sequences such as coding or non-coding regions

Training Models

• Obtaining training data from a gene set in an organism
• Using the gene set to develop a statistical model (HMM or GHMM model) for finding other genes
• Validating the model through evaluation

Gene Prediction Accuracy

• Measuring the performance of a gene finder
• Quantifying how effectively a method identifies genes
• Using true/false positives and negatives in calculations of accuracy rates

This quiz covers essential concepts in bioinformatics, focusing on sequence alignment techniques, including BLASTn and TBLASTn. It explores alignment scoring, complexities, and the theoretical aspects of local alignments. Test your understanding of these critical topics in molecular biology and computational analysis.