Bioinformatics

Algorithms and statistics for reading sequences and genomes

About this course

Computational analysis of biological sequences — alignment, scoring and BLAST, motifs and hidden Markov models, genome assembly and annotation, phylogenetics, population genomics, expression analysis, and structure and networks.

What you will be able to do

  • Compute pairwise alignments by dynamic programming and choose a substitution matrix
  • Interpret BLAST results using their statistics
  • Represent sequence families with profiles and hidden Markov models
  • Describe how genomes are assembled and annotated
  • Build phylogenetic trees and analyse expression data with false-discovery control and clustering

What this course covers

  • Genome as an information-bearing text
  • The genetic code as a redundant mapping
  • K-mer frequency and unique-word length
  • Geometric open reading frame length and the GC trap
  • The null model as a ruler, not a claim
  • Fermi estimate of long frames by chance
  • The genome as a book: capstone worked example
  • Lander-Waterman Coverage and Contig Count
  • Read Technologies and Their Trade-offs
  • De Bruijn Graph and the Eulerian Walk
  • Sequencing Errors in the De Bruijn Graph
  • N50 as an Assembly Quality Metric
  • Fermi Estimate: Human Genome at Thirty-Fold
  • Two Kinds of Gap and the Limits of Coverage
  • Frequency matrix and sequence logo
  • Weight matrix and log-odds scoring
  • Information content as a count of chance sites (2^R rule)
  • Corrections to the 2^R approximation
  • Profiles and family information content
  • Validity of the logo as a measurement
  • Fermi estimate: bits needed for uniqueness in a human genome
  • p-distance and its saturation at three-quarters
  • Jukes-Cantor correction formula
  • Neutral molecular clock and Kimura's cancellation
  • Kimura two-parameter model for transitions and transversions
  • dN/dS ratio as a measure of selection
  • Converting distance to a divergence time
  • Reliability and limits of molecular distance estimates
  • RNA-Seq counts, TPM, and normalization
  • Poisson noise vs. biological dispersion (negative binomial)
  • Multiple testing and the false discovery rate
  • Local FDR and the Q value
  • PCA by the power method
  • K-means clustering of gene profiles
  • Sequencing depth, the biological noise floor, and budget allocation
  • The human gene count and how evidence settled it
  • Codon usage bias as a coding statistic
  • Splice sites as position-weight matrices
  • Why gene-level accuracy is far lower than exon-level accuracy
  • Shape of a human gene and the HMM gene finder
  • Open reading frames versus real genes: the Fermi estimate
  • Worked Fermi: gene count, finder cost, and RNA-seq reads
  • Hidden Markov Model structure and motivation
  • Viterbi algorithm for most-probable path decoding
  • Forward algorithm and sequence probability
  • Posterior decoding and Viterbi vs. posterior comparison
  • Baum-Welch learning from unlabeled sequence
  • Dishonest casino application
  • Computational cost of HMM decoding at genomic scale
  • Levinthal's Paradox and the Folding Funnel
  • Propensity-Based Secondary Structure Prediction
  • Coevolution and Mutual Information for Contact Prediction
  • AlphaFold and the Limits of Fold Prediction
  • Degree Distributions and Preferential Attachment
  • Network Robustness: Random Failure vs. Targeted Attack
  • Worked Fermi Estimate: the Funnel in Numbers
  • The space of phylogenetic trees
  • UPGMA: clock-assuming distance method
  • Neighbor-joining: rate-corrected distance method
  • The bootstrap and its limits as a support measure
  • Parsimony as a character-based tree score
  • Likelihood-based tree scoring by Felsenstein's pruning
  • Long-branch attraction and Felsenstein's zone
  • Needleman-Wunsch global alignment recurrence
  • Edit distance as the same table
  • Smith-Waterman local alignment and affine gap costs
  • Dot plot as the table's diagonal
  • Counting alignments and dynamic programming's saving
  • Alignment scores as estimated, not arbitrary
  • Fermi estimate: genome vs. genome alignment cost
  • The Human Genome Ledger: Fractions and Composition
  • Genome Sequencing Cost Curve and Halving Time
  • Sequencing Technology Eras and the Completeness Mirage
  • Metagenomic Census and Chao's Estimator
  • The Genome Archive Deluge and the Dark Genome
  • The Course Spine: Sequence Claims as Numbers with Expectations
  • PAM matrix: counting and powering
  • Why amino acids are not interchangeable
  • Log-odds scoring and relative entropy
  • BLOSUM: counting blocks instead of extrapolating
  • Reading BLOSUM62 entry by entry
  • Central result: a score is a log odds, a matrix is a model of time
  • Matching the matrix to evolutionary distance
  • Hardy-Weinberg Equilibrium and the Chi-Square Test
  • Allele Frequency Spectrum and Variant Origins
  • Linkage Disequilibrium and Its Decay
  • GWAS Significance Threshold and the Manhattan Plot
  • Genome-Wide Association Scan
  • Statistical Power and Sample Size in GWAS
  • Winner's Curse: Inflation of First-Found Effect Sizes
  • Extreme Value Distribution of Best Local Scores
  • Lambda: the Scoring-Matrix Exchange Rate
  • The E-value: Expected Chance Hits in a Search
  • Why the Gaussian Fails for Alignment Scores
  • Seed-and-Extend Heuristic (BLAST)
  • Robustness and Limits of the E-value Null
  • The Twilight Zone: Identity, Length, and Significance

Syllabus

  1. Sequences and Alignment

    1. L1 · The Sequence as Text
    2. L2 · Pairwise Alignment
    3. L3 · Scores and Substitution Matrices
    4. L4 · BLAST and Statistics

  2. Motifs and Models

    1. L5 · Motifs, Profiles and Logos
    2. L6 · Hidden Markov Models

  3. Genomes

    1. L7 · Genome Assembly
    2. L8 · Gene Finding and Annotation

  4. Trees and Populations

    1. L9 · Distances and the Molecular Clock
    2. L10 · Phylogenetic Trees
    3. L11 · Population Genomics and Association

  5. Expression, Structure and Networks

    1. L12 · Expression: Counts, Discoveries and Clusters
    2. L13 · Structure and Networks
    3. L14 · The Genome as a Whole, and the Close