Manolis Kellis
@manoliskellis1·24.9K subscribers·255 videos
MIT CompBio Lecture 03 - Database Search
Posted
October 3, 2018
Views
5,335
Likes
48
Comments
6
Engagement
1.01%
October 3, 2018
5,335
48
6
1.01%
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.
1:16:57Now PlayingMIT Computational Biology: Genomes, Networks, Evolution, Health
Prof. Manolis Kellis
Fall 2018
Computational, Biology, Genomes, Networks, Evolution, Health, MIT, HST, Broad, CompBio
Lecture 03 - Database Search
1. Global alignment vs. Local alignment
- Needleman-Wunsch and Smith-Waterman
- Varying gap penalties and algorithmic speedups
2. Linear-time exact string matching (expected)
- Karp-Rabin algorithm and semi-numerical methods
- Hash functions and randomized algorithms
3. The BLAST algorithm and inexact matching
- Hashing with neighborhood search
- Two-hit blast and hashing with combs
4. Probabilistic foundations of sequence alignment
- Mismatch penalties, BLOSUM and PAM matrices
- Statistical significance of an alignment score
5. Deterministic linear-time exact string matching
- Key insight: gather more info from each comparison
- Pre-processing, Z-algorithm, Boyer-More, KMP
Slides for Lecture 3:
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.
