MIT CompBio Lecture 02 - DynamicProgramming (Part2)

MIT Computational Biology: Genomes, Networks, Evolution, Health Prof. Manolis Kellis http://compbio.mit.edu/6.047/ Fall 2018 Computational, Biology, Genomes, Networks, Evolution, Health, MIT, HST, Broad, CompBio Lecture 02 - Sequence Alignment / Dynamic Programming 1. Introduction to sequence alignment - Comparative genomics and molecular evolution - From Bio to CS: Problem formulation - Why it’s hard: Exponential number of alignments 2. Introduction to principles of dynamic programming - Computing Fibonacci numbers: Top-down vs. bottom-up - Repeated sub-problems, ordering compute, table lookup - DP recipe: (1) Parameterization, (2) sub-problem space, (3) traversal order, (4) recursion formula, (5) trace-back 3. DP for sequence alignment - Additive score, building up a solution from smaller parts - Prefix matrix: finite subproblems, exponential paths - Duality: each entryprefix alignment score; pathaligmnt 4. Advanced topics: Dynamic Programming variants - Linear-time bounded DP(heuristic). Better than O(n2)? - Linear-space DP: Four-Russians algorithm. Total time? Slides for Lecture 2: https://stellar.mit.edu/S/course/6/fa18/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture02_DynamicProgramming/Lecture02_DynamicProgramming_6up.pdf