We will see in the first half of the course that biologists cannot read the 3 billion nucleotides of a human genome like a book from beginning to end. They can, however, read shorter DNA fragments. In this course, we'll look at how graph theory can be used to piece together genomes from these short pieces, resulting in the largest jigsaw puzzle ever assembled.
We'll talk about antibiotics in the second half of the course, which is important because antimicrobial-resistant bacteria like MRSA are on the rise. Antibiotics are drugs, but on a molecular level, they are short mini-proteins that bacteria have engineered to kill their enemies. Determining the sequence of amino acids that make up one of these antibiotics is a significant research problem, and it is similar to sequencing a genome by assembling tiny fragments of DNA. We'll see how brute force algorithms that try every possible solution can identify naturally occurring antibiotics and synthesise them in a lab.
Finally, you'll learn how to use popular bioinformatics software to sequence the genome of a dangerous Staphylococcus bacterium that has developed antibiotic resistance.
1. Introduction to Genome Sequencing
- What Is Genome Sequencing?
- Exploding Newspapers
- The String Reconstruction Problem3m
- String Reconstruction as a Hamiltonian Path Problem
- String Reconstruction as an Eulerian Path Problem
- Similar Problems with Different Fates
2. Applying Euler's Theorem to Assemble Genomes
- De Bruijn Graphs
- Euler's Theorem
- Assembling Read-Pairs
- De Bruijn Graphs Face Harsh Realities of Assembly
- Returning to Konigsberg
3. Sequencing Antibiotics
- The Discovery of Antibiotics
- How Do Bacteria Make Antibiotics?
- Sequencing Antibiotics by Shattering Them into Pieces
- A Brute Force Algorithm for Cyclopeptide Sequencing
- Cyclopeptide Sequencing with Branch and Bound
4. From Ideal to Real Spectra for Antibiotics Sequencing
- Adapting Sequencing for Spectra with Errors
- From 20 to More than 100 Amino Acids
- The Spectral Convolution Saves the Day
- The Truth About Spectra