About this course: In Spring 2011, thousands of people in Germany were hospitalized with a deadly disease that started as food poisoning with bloody diarrhea and often led to kidney failure. It was the beginning of the deadliest outbreak in recent history, caused by a mysterious bacterial strain that we will refer to as E. coli X. Soon, German officials linked the outbreak to a restaurant in Lübeck, where nearly 20% of the patrons had developed bloody diarrhea in a single week. At this point, biologists knew that they were facing a previously unknown pathogen and that traditional methods would not suffice – computational biologists would be needed to assemble and analyze the genome of the newly emerged pathogen. To investigate the evolutionary origin and pathogenic potential of the outbreak strain, researchers started a crowdsourced research program. They released bacterial DNA sequencing data from one of a patient, which elicited a burst of analyses carried out by computational biologists on four continents. They even used GitHub for the project: https://github.com/ehec-outbreak-crowdsourced/BGI-data-analysis/wiki The 2011 German outbreak represented an early example of epidemiologists collaborating with computational biologists to stop an outbreak. In this Genome Assembly Programming Challenge, you will follow in the footsteps of the bioinformaticians investigating the outbreak by developing a program to assemble the genome of the E. coli X from millions of overlapping substrings of the E.coli X genome.

Created by: University of California, San Diego, Higher School of Economics

Taught by: Alexander S. Kulikov, Visiting Professor
Department of Computer Science and Engineering
Taught by: Michael Levin, Lecturer
Computer Science
Taught by: Pavel Pevzner, Professor
Department of Computer Science and Engineering
Taught by: Neil Rhodes, Adjunct Faculty
Computer Science and Engineering

Basic Info	Course 6 of 6 in the Data Structures and Algorithms Specialization
Level	Advanced
Language	English
How To Pass	Pass all graded assignments to complete the course.
User Ratings	4.3 stars Average User Rating 4.3See what learners said

Syllabus

WEEK 1

The 2011 European E. coli Outbreak

In April 2011, hundreds of people in Germany were hospitalized with a deadly disease that often started as food poisoning with bloody diarrhea. It was the beginning of the deadliest outbreak in recent history, caused by a mysterious bacterial strain that we will refer to as E. coli X. Within a few months, the outbreak had infected thousands and killed 53 people. To prevent the further spread of the outbreak, computational biologists all over the world had to answer the question “What is the genome sequence of E. coli X?” in order to figure out what new genes it acquired to become pathogenic. The 2011 German outbreak represented an early example of epidemiologists collaborating with computational biologists to stop an outbreak. In this Genome Assembly Programming Challenge, you will follow in the footsteps of the bioinformaticians investigating the outbreak by developing a program to assemble the genome of the deadly E. coli X strain. However, before you embark on building a program for assembling the E. coli X strain, we have to explain some genomic concepts and warm you up by having you solve a simpler problem of assembling a small virus.

2 videos, 1 reading

Video: 2011 European E. coli outbreak
Video: Assembling phage genome
Reading: Project Description

Graded: What does it mean to assemble a genome?

Graded: What does it mean to assemble a genome from error-prone-reads?

Graded: Programming Assignment 1: Assembling the phi 174X Genome Using Overlap Graphs

WEEK 2

Assembling Genomes Using de Bruijn Graphs

DNA sequencing approach that led to assembly of a small virus in 1977 went through a series of transformations that contributed to the emergence of personalized medicine a few years ago. By the late 1980s, biologists were routinely sequencing viral genomes containing hundreds of thousands of nucleotides, but the idea of sequencing a bacterial (let alone the human) genome containing millions (or even billions) of nucleotides remained preposterous and would cost billions of dollars. In 1988, three biologists (independently and simultaneously!) came up with an idea to reduce sequencing cost and proposed the futuristic and at the time completely implausible method of DNA arrays. None of these three biologists could have possibly imagined that the implications of his own experimental research would eventually bring him face-to-face with challenging algorithmic problems. In this module you will learn about the algorithmic challenge of DNA sequencing using information about short k-mers provided by DNA arrays. You will also travel to the 18the century to learn about the Bridges of Konigsberg and solve a related problem of assembling a jigsaw puzzle!

5 videos

Video: DNA arrays
Video: Assembling genomes from k-mers
Video: De Bruijn graphs
Video: Bridges of Königsberg and universal strings
Video: Euler theorem

Graded: Programming Assignment 2: Assembling the phi 174X Genome Using De Bruijn Graphs

WEEK 3

Genome Assembly Faces Real Sequencing Data

Our discussion of genome assembly has thus far relied upon various assumptions. In this module, we will face practical challenges introduced by quirks in modern sequencing technologies and discuss some algorithmic techniques that have been devised to address these challenges. Afterwards, you will assemble the smallest bacterial genome that lives symbiotically inside leafhoppers. Its sheltered life has allowed it to reduce its genome to only about 112,091 nucleotides and 137 genes. And afterwards, you will be ready to assemble the E. coli X genome!

3 videos

Video: Splitting the genome into contigs
Video: From reads to read-pairs
Video: Genome assembly faces real sequencing data

Graded: Programming Assignment 3: Genome Assembly Faces Real Sequencing Data

FAQs

How It Works

Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from Your Peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Creators

University of California, San Diego

UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory.

Higher School of Economics

National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more. Learn more on www.hse.ru

Pricing

	Audit	Purchase Course
Access to course materials	Available	Available
Access to graded materials	Not available	Available
Receive a final grade	Not available	Available
Earn a shareable Course Certificate	Not available	Available

Ratings and Reviews

Rated 4.3 out of 5 of 25 ratings

Good course and final capstone project. Would recommend anyone from beginner to professional.

Really tough and enjoyable Project. Learnt something very special.

Great challenge, requires quite a lot of time, patience and dedication. But in the end, if you eventually come through all of the trials - you will become a better programmer, for sure.

I've put 4 of 5 because of the mismatches in tasks description for the capstone project, when i had to guess, where the mismatch is, spending extra hours of my time

Really Challenging course, will make the mind to work.

Enjoyed taking the course, was much harder than expected and loved it anyway.

Worth the time ,effort and resources.

The course was much less guided compared to other the course but instructor mentioned it that it was on purpose for developing self learning and facing real life sitituations.

Share