Genome assembly - Lesson Plan

Learning outcomes

• Understand why assembly is needed
• Understand the concept of an overlap graph
• Able to construct an overlap graph
• Understand the concept of a de Bruijn graph
• Able to construct a de Bruijn graph
• Able to represent a graph computationally
• Understand difference between Eulerian and Hamiltonian path problems
• Able to decide if a graph is Eulerian
• Able to describe an algorithm for constructing an Eulerian path or tour
• Understand why longer reads are better
• Understand why we are using graphs and not greedy approaches

Stop at page 166

Class activities

Go through assembly slides

Solve small assembly problem

Build a computational representation of a graph

Decide if a graph is Eulerian

Write out code to decide if a graph is Eulerian (perhaps with spanning trees)

Exercises

Rosalind section 4  (4B)