Oct 24th 2016

Comparing Genes, Proteins, and Genomes (Bioinformatics III) (Coursera)

After sequencing genomes, we would like to compare them. We will see that dynamic programming is a powerful algorithmic tool when we compare two genes (i.e., short sequences of DNA) or two proteins. When we "zoom out" to compare entire genomes, we will employ combinatorial algorithms.

Once we have sequenced genomes in the previous course, we would like to compare them to determine how species have evolved and what makes them different.

In the first half of the course, we will compare two short biological sequences, such as genes (i.e., short sequences of DNA) or proteins. We will encounter a powerful algorithmic tool called dynamic programming that will help us determine the number of mutations that have separated the two genes/proteins.

In the second half of the course, we will "zoom out" to compare entire genomes, where we see large scale mutations called genome rearrangements, seismic events that have heaved around large blocks of DNA over millions of years of evolution. Looking at the human and mouse genomes, we will ask ourselves: just as earthquakes are much more likely to occur along fault lines, are there locations in our genome that are "fragile" and more susceptible to be broken as part of genome rearrangements? We will see how combinatorial algorithms will help us answer this question.

Finally, you will learn how to apply popular bioinformatics software tools to solve problems in sequence alignment, including BLAST.

Part of the Bioinformatics: Journey to the Frontier of Computational Biology Specialization.

Who is this class for:

This course is primarily aimed at undergraduate-level learners in computer science, biology, or a related field who are interested in learning about how the intersection of these two disciplines represents an important frontier in modern science.



Introduction to Sequence Alignment

If you joined us in the previous course in this Specialization, then you became an expert at assembling genomes and sequencing antibiotics. The next natural question to ask is how to compare DNA and amino acid sequences. This question will motivate this week's discussion of sequence alignment, which is the first of two questions that we will ask in this class (the algorithmic methods used to answer them are shown in parentheses):

  1. How Do We Compare DNA Sequences? (Dynamic Programming)

  2. Are There Fragile Regions in the Human Genome? (Combinatorial Algorithms)

Graded: Week 1 Quiz

Graded: Open in order to Sync Your Progress: Stepik Interactive Text for Week 1


From Finding a Longest Path to Aligning DNA Strings

Last week, we saw how touring around Manhattan and making change in a Roman shop help us find a longest common subsequence of two DNA or protein strings.

This week, we will study how to find a highest scoring alignment of two strings. We will see that regardless of the underlying assumptions that we make regarding how the strings should be aligned, we will be able to phrase our alignment problem as an instance of finding the longest path in a directed acyclic graph.

Graded: Week 2 Quiz

Graded: Open in order to Sync Your Progress: Stepik Interactive Text for Week 2


Advanced Topics in Sequence Alignment

Last week, we saw how a variety of different applications of sequence alignment can all be reduced to finding the longest path in a Manhattan-like graph.

This week, we will conclude the current chapter by considering a few advanced topics in sequence alignment. For example, if we need to align long strings, our current algorithm will consume a huge amount of memory. Can we find a more memory-efficient approach? And what should we do when we move from aligning just two strings at a time to aligning many strings?

Graded: Week 3 Quiz

Graded: Open in order to Sync Your Progress: Stepik Interactive Text for Week 3


Genome Rearrangements and Fragility

You now know how to compare two DNA (or protein) strings.  But what if we wanted to compare entire genomes? When we "zoom out" to the genome level, we find that substitutions, insertions, and deletions don't tell the whole story of evolution: we need to model more dramatic evolutionary events known as genome rearrangements, which wrench apart chromosomes and put them back together in a new order. A natural question to ask is whether there are "fragile regions" hidden in your genome where chromosome breakage has occurred more often over millions of years. This week, we will begin addressing this question by asking how we can compute the number of rearrangements on the evolutionary path connecting two species.

Graded: Week 4 Quiz

Graded: Open in order to Sync Your Progress: Stepik Interactive Text for Week 4


Applying Genome Rearrangement Analysis to Find Genome Fragility

Last week, we asked whether there are fragile regions in the human genome. Then, we took a lengthy detour to see how to compute a distance between species genomes, a discussion that we will continue this week.

It is probably unclear how computing the distance between two genomes can help us understand whether fragile regions exist. If so, please stay tuned -- we will see that the connection between these two concepts will yield a surprising conclusion to the class.

Graded: Week 5 Quiz

Graded: Open in order to Sync Your Progress: Stepik Interactive Text for Week 5


Week 6: Bioinformatics Application Challenge

In the sixth and final week of the course, we will apply sequence alignment algorithms to infer the non-ribosomal code.

Graded: Bioinformatics Application Challenge

Suggested Readings:
Bioinformatics Algorithms An Active Learning Approach