👻Intro to Computational Biology Unit 2 – Bioinformatics Algorithms

Key Concepts and Definitions

• Bioinformatics combines computer science, statistics, and mathematics to analyze and interpret biological data
• Sequence alignment arranges DNA, RNA, or protein sequences to identify regions of similarity that may indicate functional, structural, or evolutionary relationships
• Dynamic programming is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations
• Phylogenetics is the study of evolutionary relationships among organisms based on genetic and morphological similarities
• Genome assembly involves piecing together short DNA fragments (reads) into longer, contiguous sequences (contigs) to reconstruct the original genome
  • De novo assembly builds the genome from scratch without a reference, while reference-guided assembly uses a closely related genome as a guide
• Gene prediction identifies protein-coding regions within a genome using computational methods that recognize characteristic patterns and signals
• Protein structure analysis involves studying the 3D shape and folding of proteins to understand their function and interactions
• Homology refers to the similarity between sequences or structures due to common ancestry, while analogy arises from convergent evolution

Biological Data Types and Structures

• DNA sequences consist of four nucleotide bases: adenine (A), thymine (T), guanine (G), and cytosine (C)
  • DNA is double-stranded, with complementary base pairing (A-T and G-C)
• RNA sequences contain the bases adenine (A), uracil (U), guanine (G), and cytosine (C)
  • RNA is typically single-stranded and serves various roles, such as coding for proteins (mRNA), regulating gene expression (miRNA), and catalyzing reactions (ribozymes)
• Proteins are made up of 20 different amino acids linked together by peptide bonds
  • The sequence of amino acids determines the protein's structure and function
• Biological databases store and organize various types of data, including sequences (GenBank, UniProt), structures (PDB), and literature (PubMed)
• FASTA format is a text-based format for representing nucleotide or amino acid sequences, with a header line starting with ">" followed by the sequence on subsequent lines
• Sequence motifs are short, conserved patterns in DNA, RNA, or proteins that often have functional significance (transcription factor binding sites, catalytic sites)
• Sequence profiles represent the position-specific amino acid preferences in a multiple sequence alignment, capturing conserved and variable regions

Sequence Alignment Algorithms

• Pairwise alignment compares two sequences to find the best match, considering matches, mismatches, and gaps
  • Global alignment (Needleman-Wunsch) aligns the entire sequences, while local alignment (Smith-Waterman) finds the best matching subregions
• Multiple sequence alignment (MSA) aligns three or more sequences to identify conserved regions and infer evolutionary relationships
  • Progressive alignment (ClustalW) builds the MSA incrementally by aligning the most similar sequences first and then adding more divergent ones
  • Iterative refinement (MUSCLE) improves the initial alignment by repeatedly dividing the sequences into subgroups, realigning them, and merging the results
• Scoring matrices (BLOSUM, PAM) assign scores to amino acid substitutions based on their observed frequencies in alignments of related proteins
• Gap penalties discourage the introduction of gaps in the alignment, with affine gap penalties assigning different costs for opening and extending gaps
• Heuristic methods (BLAST, FASTA) sacrifice some accuracy for speed by using seed-and-extend approaches to identify high-scoring local alignments
• Hidden Markov models (HMMs) capture position-specific information and allow for insertions and deletions, making them useful for profile-based sequence analysis and homology detection

Phylogenetic Tree Construction

• Phylogenetic trees represent the evolutionary relationships among organisms or sequences, with branches indicating divergence from a common ancestor
  • Rooted trees have a designated root node representing the most recent common ancestor, while unrooted trees only show relative relationships
• Distance-based methods (UPGMA, neighbor-joining) calculate pairwise distances between sequences and cluster them based on their similarity
  • UPGMA assumes a constant evolutionary rate (molecular clock), while neighbor-joining allows for varying rates
• Maximum parsimony aims to find the tree that requires the fewest evolutionary changes to explain the observed data
  • Fitch's algorithm is a dynamic programming approach that efficiently computes the minimum number of changes needed for a given tree
• Maximum likelihood estimates the probability of observing the data given a tree and a model of evolution, seeking the tree with the highest likelihood
  • The likelihood is calculated using a substitution model (Jukes-Cantor, Kimura, GTR) that describes the rates of different types of mutations
• Bayesian inference combines the likelihood with prior probabilities to compute the posterior probability of trees, using Markov chain Monte Carlo (MCMC) sampling to explore the tree space
• Bootstrapping assesses the reliability of tree branches by resampling the data with replacement and calculating the proportion of replicates supporting each branch

Genome Assembly Techniques

• Sanger sequencing produces long, accurate reads (500-1000 bp) but is relatively low-throughput and expensive
• Next-generation sequencing (NGS) technologies (Illumina, 454, SOLiD) generate millions of short reads (50-500 bp) in parallel, enabling high-throughput and cost-effective sequencing
  • Paired-end and mate-pair sequencing provide additional information about the distance and orientation of reads, aiding in genome assembly
• Overlap-layout-consensus (OLC) assemblers (Celera, Newbler) identify overlaps between reads, construct a graph representing their relationships, and derive a consensus sequence
  • OLC works well for long, accurate reads but struggles with repetitive regions and high sequencing errors
• De Bruijn graph assemblers (Velvet, SPAdes) break reads into shorter k-mers, construct a graph where nodes represent k-mers and edges indicate overlaps, and traverse the graph to assemble contigs
  • De Bruijn graphs are more efficient for short reads and can handle higher error rates but may have difficulty resolving repeats longer than the k-mer size
• Hybrid assembly combines reads from different sequencing technologies (PacBio, Oxford Nanopore) to leverage their strengths and compensate for their weaknesses
• Scaffolding uses paired-end, mate-pair, or long-read information to order and orient contigs, potentially closing gaps and improving the assembly's continuity

Gene Prediction Methods

• Ab initio gene prediction relies on intrinsic sequence features (open reading frames, codon usage, splice sites) to identify protein-coding regions without using external evidence
  • Hidden Markov models (GENSCAN, AUGUSTUS) are commonly used to model the structure and composition of genes and predict their locations
• Evidence-based methods incorporate extrinsic data, such as RNA-seq, EST, or protein alignments, to refine and validate gene predictions
  • Spliced alignment tools (BLAT, Exonerate) map transcript or protein sequences to the genome, identifying exon-intron boundaries and alternative splicing events
• Comparative genomics approaches exploit sequence conservation between related species to identify coding regions and improve gene predictions
  • Genome alignment tools (LASTZ, BLASTZ) detect conserved segments that are more likely to be functionally important, including protein-coding genes
• Consensus gene prediction combines the outputs of multiple ab initio and evidence-based methods to produce a more accurate and comprehensive gene set
  • Tools like EVidenceModeler (EVM) and MAKER integrate predictions from various sources, weigh their evidence, and generate a unified gene annotation
• Pseudogenes are non-functional gene copies that have lost their protein-coding ability due to mutations, frameshifts, or premature stop codons
  • Pseudogene identification is important for accurate gene annotation and understanding genome evolution

Protein Structure Analysis

• Primary structure refers to the linear sequence of amino acids in a protein, which is determined by the genetic code and mRNA translation
• Secondary structure describes the local folding patterns of the polypeptide chain, such as α-helices and β-sheets, stabilized by hydrogen bonds
  • Algorithms like DSSP and STRIDE assign secondary structure elements based on hydrogen bonding patterns and geometric criteria
• Tertiary structure represents the three-dimensional arrangement of a protein's atoms, resulting from interactions between secondary structure elements and side chains
  • Homology modeling predicts a protein's 3D structure based on its sequence similarity to a protein with a known structure (template)
  • Threading (fold recognition) aligns the target sequence to known protein folds and evaluates their compatibility using statistical potentials
• Quaternary structure refers to the assembly of multiple polypeptide chains (subunits) into a functional protein complex
  • Protein-protein docking methods (ZDOCK, HADDOCK) predict the structure of protein complexes by exploring the possible binding modes and evaluating their energies
• Molecular dynamics simulations study the motion and interactions of proteins over time, based on Newtonian physics and empirical force fields
  • MD can provide insights into protein folding, conformational changes, and ligand binding, but is computationally expensive for large systems or long timescales
• Protein structure visualization tools (PyMOL, Chimera) enable the interactive display and analysis of 3D structures, facilitating the identification of functional sites and structure-based drug design

Practical Applications and Tools

• Sequence alignment tools (BLAST, HMMER) enable the rapid search for similar sequences in databases, aiding in functional annotation and evolutionary analysis
• Multiple sequence alignment viewers (Jalview, AliView) provide a graphical interface for inspecting and editing alignments, as well as calculating conservation scores and consensus sequences
• Phylogenetic tree visualization software (FigTree, iTOL) allows for the interactive exploration and customization of tree layouts, branch lengths, and taxonomic information
• Genome browsers (UCSC Genome Browser, Ensembl) integrate various types of genomic data, including sequences, annotations, and experimental tracks, facilitating data visualization and interpretation
• Variant calling pipelines (GATK, SAMtools) identify genetic variations (SNPs, indels, CNVs) from NGS data, enabling population genetics and disease association studies
• Pathway analysis tools (KEGG, Reactome) map genes and proteins to biological pathways and networks, helping to elucidate their roles in cellular processes and disease mechanisms
• Gene ontology (GO) databases (Gene Ontology, QuickGO) provide a standardized vocabulary for describing gene and protein functions, facilitating data integration and functional enrichment analysis
• Protein-ligand docking software (AutoDock, GOLD) predicts the binding pose and affinity of small molecules to protein targets, aiding in virtual screening and drug discovery efforts