6.047/6.878 Lecture 2 - Dynamic Programming (Fall 2020)

6.047/6.878/HST.507 Fall 2020 Prof. Manolis Kellis
Computational Biology: Genomes, Networks, Evolution, Health
Machine Learning in Genomics: Dissecting the circuitry of Human Disease

OVERVIEW
00:00 Evolution and comparative genomics
17:38 Lecture goals overview
18:58 Formulation(s) of sequence alignment
25:20 Formulation 1: Longest Common Substring
27:37 Formulation 2: Longest Common Subsequence
29:22 Formulation 3: Sequence alignment
36:10 Principles of Dynamic Programming
48:16 DP for sequence alignment
1:04:18 DP sequence alignment in Excel spreadsheet
1:09:44 Advanced: Linear-time and linear-space DP

[gudaguda]

Took me days to learn everything in this lecture: dynamic programming, greedy algorithm, MLE, longest substring problem. Having no CS background sucks

[jeheelee]

There is misexplanation on page 35, description of M(5, 2).
Option 2 should be "by extending S2 with G and S1 with - (gap)"

[fgfanta]

1:09:20 Why does Prof. Kellis claim that the time needed (and space needed) are O(m*n)? I start from the top-left corner, then at every step either I move right or down or both (in a diagonal); within m+n steps I will have reached the bottom right corner. I don't need to compute the cost in every cell of the matrix; I can just compute it, for every cell I traverse, for the next three candidates, and I can't traverse more than m+n.
It seems to me the time (and space) needed for the optimal solution are O(m+n). What am I missing?

[zainabasghar]

why the offset value is positive +! at first but -2 in second equation ?

[valeriebryant]

Awesome lecture! Any suggestions/resources for some practice problems?

[julius]

Great lecture. I believe the final linear space algorithm is actually Hirschberg's algorithm. 4 russians is a sub-quadratic time algorithm.

[alibrahimzada]

I guess the score at position (15, 16) should be 3.5, not 4.

[richardpetitadjakonor]

I wish i could meet you one on one for tuition which I'll pay for accordingly...i love genomics and bioinformatics