Bioinformatics Algorithms @ University of Kentucky

- A Journey of a Thousand 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
- Epilogue: Complications in ori Predictions
- CS: Generating the Neighborhood of a String
- Detour: Big-O Notation
- Detour: Probabilities of Patterns in a String
- Detour: The Most Beautiful Experiment in Biology
- Detour: Directionality of DNA Strands
- Detour: The Towers of Hanoi
- Detour: The Overlapping Words Paradox

- 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
- Epilogue: How Does Tuberculosis Hibernate?
- CS: Solving the Median String Problem
- Detour: Gene Expression
- Detour: DNA Arrays
- Detour: Buffon's Needle
- Detour: Complications in Motif Finding
- Detour: Relative entropy

- 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
- Epilogue: Genome Assembly Faces Real Sequencing Data
- CS: The Effect of Gluing on the Adjacency Matrix
- CS: Generating All Eulerian Cycles
- CS: Reconstructing a String from the Paired de Bruijn Graph
- CS: Maximal Non-Branching Paths in a Graph
- Detour: A Short History of DNA Sequencing Technologies
- Detour: Repeats in the Human Genome
- Detour: An Introduction to Graphs
- Detour: Hamilton's Icosian Game
- Detour: Tractable and Intractable Problems
- Detour: From Euler to Hamilton to de Bruijn
- Detour: The Seven Bridges of Kaliningrad
- Detour: The BEST Theorem
- Detour: Pitfalls of assembling double-stranded DNA

- 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
- Epilogue: From Simulated to Real Spectra
- CS: Generating the Theoretical Spectrum of a Peptide
- CS: How Fast is CyclopeptideSequencing?
- CS: Trimming the Peptide Leaderboard
- Detour: Gause and Lysenkoism
- Detour: The Discovery of Codons
- Detour: Quorum Sensing
- Detour: Molecular Mass
- Detour: Selenocysteine and Pyrrolysine
- Detour: Pseudo-polynomial Algorithm for the Turnpike Problem
- Detour: Split genes

- 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 Alignments
- From Global to Local Alignment
- The Changing Faces of Sequence Alignment
- Penalizing Insertions and Deletions in Sequence Alignment
- Space-Efficient Sequence Alignment
- Epilogue: Multiple Sequence Alignment
- Detour: Fireflies and the Non-Ribosomal Code
- Detour: Finding an LCS without Building a City
- Detour: Constructing a Topological Ordering
- Detour: PAM Scoring Matrices
- Detour: Divide-and-Conquer Algorithms
- Detour: Scoring Multiple Alignments

- Of Mice and Men
- The Random Breakage Model of Chromosome Evolution
- Sorting by Reversals
- A Greedy Algorithm for Sorting by Reversals
- Breakpoints
- Rearrangements in Tumor Genomes
- From Unichromosomal to Multichromosomal Genomes
- Breakpoint Graphs
- Computing the 2-Break Distance
- Rearrangement Hotspots in the Human Genome
- Epilogue: Synteny Block Construction
- CS: From Genomes to the Breakpoint Graph
- CS: Solving the 2-Break Sorting Problem
- Detour: Why is the Gene Content of X Chromosomes So Conserved?
- Detour: Discovery of Genome Rearrangements
- Detour: The Exponential Distribution
- Detour: Bill Gates and David X. Cohen Flip Pancakes
- Detour: Sorting Linear Permutations by Reversals

- The Fastest Outbreak
- Transforming Distance Matrices into Evolutionary Trees
- Toward An Algorithm for Distance-Based Phylogeny Construction
- Additive Phylogeny
- Using Least Squares to Construct Approximate Phylogenies
- Ultrametric Evolutionary Trees
- The Neighbor-Joining Algorithm
- Character-Based Tree Reconstruction
- The Small Parsimony Problem
- The Large Parsimony Problem
- Epilogue: Evolutionary Trees Fight Crime
- Detour: When Did HIV Jump from Primates to Humans?
- Detour: Searching for a Tree Fitting a Distance Matrix
- Detour: The Four Point Condition
- Detour: Did Bats Give Us SARS?
- Detour: Why Does the Neighbor-Joining Algorithm Work?
- Detour: Computing Limb Lengths in the Neighbor-Joining Algorithm
- Detour: Giant Panda: Bear or Raccoon?
- Detour: Where Did Humans Come From?

- An Evolutionary History of Wine-Making
- Identifying Genes Responsible for the Diauxic Shift
- Introduction to Clustering
- The Good Clustering Principle
- Clustering as an Optimization Problem
- Farthest First Traversal
- k-Means Clustering
- The Lloyd Algorithm
- Clustering Genes Implicated in the Diauxic Shift
- Limitations of k-means Clustering
- From Coin Flipping to k-Means Clustering
- Making Soft Decisions in Coin Flipping
- Soft k-Means Clustering
- Hierarchical Clustering
- Epilogue: Clustering Tumor Samples
- Detour: Whole Genome Duplication or a Series of Duplications?
- Detour: Measuring Gene Expression
- Detour: Microarrays
- Detour: Proof of the Center of Gravity Theorem
- Detour: Gene Expression Matrix to a Distance/Similarity Matrix
- Detour: Clustering and Corrupted Cliques

- What Causes Ohdo Syndrome?
- Introduction to Multiple Pattern Matching
- Herding Patterns into a Trie
- Preprocessing the Genome Instead
- Suffix Trees
- Suffix Arrays
- The Burrows-Wheeler Transform
- A First Attempt at Inverting the Burrows-Wheeler Transform
- The First-Last Property and Burrows-Wheeler Inversion
- Pattern Matching with the Burrows-Wheeler Transform
- Speeding Up Burrows-Wheeler Pattern Matching
- Where are the Matched Patterns?
- Burrows and Wheeler Set Up Checkpoints
- Epilogue: Mismatch-Tolerant Read Mapping
- CS: Constructing a Suffix Tree
- CS: Solving the Longest Shared Substring Problem
- CS: Partial Suffix Array Construction
- Detour: The Reference Human Genome
- Detour: Rearrangements, Insertions, & Deletions in Human Genomes
- Detour: The Aho-Corasick Algorithm
- Detour: Suffix Arrays and Suffix Trees
- Detour: Binary Search

- Classifying the HIV Phenotype
- Gambling with Yakuza
- Two Coins Up the Dealer's Sleeve
- Finding CG-Islands
- Hidden Markov Models
- The Decoding Problem
- Finding the Most Likely Outcome of an HMM
- Profile HMMs for Sequence Alignment
- Classifying Proteins with Profile HMMs
- Are Profile HMMs Really All That Useful?
- Learning the Parameters of an HMM
- Soft Decisions in Parameter Estimation
- Baum-Welch Learning
- The Many Faces of HMMs
- Epilogue: Nature is a Tinkerer and not an Inventor
- Detour: The Red Queen Effect
- Detour: Glycosylation
- Detour: DNA Methylation
- Detour: Conditional Probability

- Paleontology Meets Computing
- Which Proteins are Present in this Sample?
- Decoding an Ideal Spectrum
- From Ideal to Real Spectra
- Peptide Sequencing
- Peptide Identification
- Peptide Identification and the Infinite Monkey Theorem
- Spectral Dictionaries
- T. rex Peptides: Contaminants or Ancient Treasure Trove?
- Epilogue: From Unmodified to Modified Peptides (Part 1)
- Epilogue: From Unmodified to Modified Peptides (Part 2)
- Detour: Gene Prediction
- Detour: Finding All Paths in a Graph
- Detour: The Anti-Symmetric Path Problem
- Detour: Transforming Spectra into Spectral Vectors
- Detour: The Infinite Monkey Theorem
- Detour: The Probabilistic Space of Peptides in a Dictionary
- Detour: Are Terrestrial Dinosaurs Really the Ancestors of Birds?