Algorithms for DNA Sequencing 

Module 1 Introduction

Lecture: Why study this?

Lecture: DNA sequencing past and present

Lecture: Genomes as strings, reads as substrings

Lecture: String definitions and Python examples

Practical: String basics

Practical: Manipulating DNA strings

Practical: Downloading and parsing a genome

Lecture: How DNA gets copied

Optional lecture: How second-generation sequencers work

Optional lecture: Sequencing errors and base qualities

Lecture: Sequencing reads in FASTQ format

Practical: Working with sequencing reads

Practical: Analyzing reads by position

Lecture: Sequencers give pieces to genomic puzzles

Lecture: Read alignment and why it's hard

Lecture: Naive exact matching

Practical: Matching artificial reads

Practical: Matching real reads

Welcome to Algorithms for DNA Sequencing

Pre Course Survey

Syllabus

Setting up Python (and Jupyter)

Getting slides and notebooks

Using data files with Python programs

Programming Homework 1 Instructions (Read First)

Module 1

Programming Homework 1

Week 2 Introduction

Lecture: Boyer-Moore basics

Lecture: Boyer-Moore: putting it all together

Lecture: Diversion: Repetitive elements

Practical: Implementing Boyer-Moore

Lecture: Preprocessing

Lecture: Indexing and the k-mer index

Lecture: Ordered structures for indexing

Lecture: Hash tables for indexing

Practical: Implementing a k-mer index

Lecture: Variations on k-mer indexes

Lecture: Genome indexes used in research

Lecture: Approximate matching, Hamming and edit distance

Lecture: Pigeonhole principle

Practical: Implementing the pigeonhole principle

Programming Homework 2 Instructions (Read First)

Module 2

Programming Homework 2

Module 3 Introduction

Lecture: Solving the edit distance problem

Lecture: Using dynamic programming for edit distance

Practical: Implementing dynamic programming for edit distance

Lecture: A new solution to approximate matching

Lecture: Meet the family: global and local alignment

Practical: Implementing global alignment

Lecture: Read alignment in the field

Lecture: Assembly: working from scratch

Lecture: First and second laws of assembly

Lecture: Overlap graphs

Practical: Overlaps between pairs of reads

Practical: Finding and representing all overlaps

Programming Homework 3 Instructions (Read First)

Module 3

Programming Homework 3

Module 4 introduction

Lecture: The shortest common superstring problem

Practical: Implementing shortest common superstring

Lecture: Greedy shortest common superstring

Practical: Implementing greedy shortest common superstring

Lecture: Third law of assembly: repeats are bad

Lecture: De Bruijn graphs and Eulerian walks

Practical: Building a De Bruijn graph

Lecture: When Eulerian walks go wrong

Lecture: Assemblers in practice

Lecture: The future is long?

Lecture: Computer science and life science

Lecture: Thank yous

Post Course Survey

Programming Homework 4

Module 4