Manolis Kellis
@manoliskellis1·24.9K subscribers·255 videos
MIT CompBio Lecture 02 - DynamicProgramming (Part2)
Posted
October 3, 2018
Views
5,312
Likes
41
Comments
2
Engagement
0.81%
October 3, 2018
5,312
41
2
0.81%
Every word spoken in this episode is indexed. Type any phrase to jump straight to the moment it was said.
Type any word or phrase that may have been spoken. Click a result to seek the player to that exact moment.
Try a name, a topic, or a quoted line
See what was published immediately before and after this episode.
21:59Now PlayingMIT Computational Biology: Genomes, Networks, Evolution, Health
Prof. Manolis Kellis
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 entryprefix alignment score; pathaligmnt
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
Sentinel Indexing in Progress
Metadata and chapters are available. Claim extraction for this episode is pending.
All video content is delivered via YouTube embedded players in accordance with the YouTube Terms of Service. Sentinel provides research tools that promote discovery and accountability across political media.
