Read the Book
We love open education, so the first five chapters of the book are free to read here, one page per lesson. If you enjoy them, the print book and the interactive course have all eleven.
Chapter 1 · Algorithmic Warmup
Where in the Genome Does DNA Replication Begin?
How simple computational analysis of a bacterial genome can uncover the hidden messages that tell a cell where to begin copying its DNA: frequent words, clump finding, GC skew, and approximate pattern matching.
Welcome to Bioinformatics Algorithms! · A Journey of 1000 Miles... · Hidden Messages in the Replication Origin · Some Hidden Messages are More Surprising than Others · An Explosion of Hidden Messages · The Simplest Way to Replicate DNA · Asymmetry of Replication · Peculiar Statistics of the Forward and Reverse Half-Strands · Some Hidden Messages are More Elusive than Others · A Final Attempt at Finding DnaA Boxes in E. coli · Complications in ori Predictions
Chapter 2 · Randomized Algorithms
Which DNA Patterns Play the Role of Molecular Clocks?
How to find regulatory motifs, the hidden messages that help genes turn on and off: profile matrices, entropy, median strings, greedy motif search, randomized motif search, and Gibbs sampling.
Do We Have a "Clock" Gene? · Motif Finding is More Difficult Than You Think · Scoring Motifs · From Motif Finding to Finding a Median String · Greedy Motif Search · Motif Finding Meets Oliver Cromwell · Randomized Motif Search · How Can a Randomized Algorithm Perform So Well? · Gibbs Sampling · Gibbs Sampling in Action · How Does Tuberculosis Hibernate?
Chapter 3 · Graph Algorithms
How Do We Assemble Genomes?
The graph algorithms used to assemble a genome from millions of short DNA fragments: overlap graphs, de Bruijn graphs, Euler's theorem, Eulerian paths, and read-pairs.
Exploding Newspapers · The String Reconstruction Problem · String Reconstruction as a Walk in the Overlap Graph · Another Graph for String Reconstruction · Walking in the de Bruijn Graph · The Seven Bridges of Königsberg · Euler's Theorem · From Euler's Theorem to an Algorithm for Finding Eulerian Cycles · Assembling Genomes from Read-Pairs · Genome Assembly Faces Real Sequencing Data
Chapter 4 · Brute Force Algorithms
How Do We Sequence Antibiotics?
How weighing tiny peptides lets us sequence antibiotics: mass spectrometry, brute force and branch-and-bound cyclopeptide sequencing, leaderboards, and the spectral convolution.
The Discovery of Antibiotics · How Do Bacteria Make Antibiotics? · Dodging the Central Dogma of Molecular Biology · Sequencing Antibiotics by Shattering Them into Pieces · A Brute Force Algorithm for Cyclopeptide Sequencing · A Branch-and-Bound Algorithm for Cyclopeptide Sequencing · Mass Spectrometry Meets Golf · From 20 to More than 100 Amino Acids · The Spectral Convolution Saves the Day · From Simulated to Real Spectra
Chapter 5 · Dynamic Programming
How Do We Compare Biological Sequences?
The dynamic programming algorithms used to compare genes and proteins: the Manhattan Tourist Problem, longest common subsequences, global and local alignment, edit distance, affine gaps, and linear-space alignment.
Cracking the Non-Ribosomal Code · Introduction to Sequence Alignment · The Manhattan Tourist Problem · Sequence Alignment is the Manhattan Tourist Problem in Disguise · An Introduction to Dynamic Programming: The Change Problem · The Manhattan Tourist Problem Revisited · From Manhattan to an Arbitrary DAG · Backtracking in the Alignment Graph · Scoring Alignment · From Global to Local Alignment · The Changing Faces of Sequence Alignment · Penalizing Insertions and Deletions in Sequence Alignment · Space Efficient Sequence Alignment · Multiple Sequence Alignment
Chapters 6 to 11
These chapters are in the print book and the interactive course. Their lecture videos and FAQs are free.
- Chapter 6: Are There Fragile Regions in the Human Genome? (Combinatorial Algorithms). Lectures · FAQ
- Chapter 7: Which Animal Gave Us SARS? (Evolutionary Tree Reconstruction). Lectures · FAQ
- Chapter 8: How Did Yeast Become a Wine-Maker? (Clustering Algorithms). Lectures · FAQ
- Chapter 9: How Do We Locate Disease-Causing Mutations? (Combinatorial Pattern Matching). Lectures · FAQ
- Chapter 10: Why Have Biologists Still Not Developed an HIV Vaccine? (Hidden Markov Models). Lectures · FAQ
- Chapter 11: Was T. rex Just a Big Chicken? (Computational Proteomics). Lectures · FAQ