Genome Sequencing (Bioinformatics II)










                                                                                                                                                                
In this course, you will learn how entire genomes are assembled from millions of short overlapping pieces of DNA. The scale of this problem (the human genome is 3 billion nucleotides long!) implies that computers must be involved. Yet the problem is even more complex than it may appear ... to solve it, we will need to travel back in time to meet three famous mathematicians, and learn about algorithms based on graph theory.

Syllabus

How Do We Assemble Genomes? (Graph Algorithms)

  • 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 Konigsberg
  • 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

How Do We Sequence Antibiotics? (Brute Force Algorithms)

  • The Discovery of Antibiotics
  • How Do Bacteria Make Antibiotics?
  • Dodging the Central Dogma
  • Sequencing Antibiotics by Shattering them into Pieces
  • A Brute Force Algorithm for Cyclopeptide Sequencing
  • A Branch-and-Bound Algorithm for Cyclopeptide Sequencing
  • Just How Fast Is This Algorithm?
  • Adapting Cyclopeptide Sequencing for Spectra with Errors
  • From 20 to More than 100 Amino Acids
  • The Spectral Convolution Saves the Day
  • Epilogue: From Simulated to Real Spectra

Bioinformatics Application Challenge: Sequencing a Staphylococcus aureus genome

Read More

In this course, you will learn how entire genomes are assembled from millions of short overlapping pieces of DNA. The scale of this problem (the human genome is 3 billion nucleotides long!) implies that computers must be involved. Yet the problem is even more complex than it may appear ... to solve it, we will need to travel back in time to meet three famous mathematicians, and learn about algorithms based on graph theory.