MIT CompBio Lecture 03 - Hashing BLAST Database Search (Fall'19)

MIT Computational Biology: Genomes, Networks, Evolution, Health
http://compbio.mit.edu/6.047/
Prof. Manolis Kellis

Full playlist with all videos in order is here: https://www.youtube.com/playlist?list=PLypiXJdtIca6U5uQOCHjP9Op3gpa177fK

All slides from Fall 2019 are here: https://stellar.mit.edu/S/course/6/fa19/6.047/materials.html

Outline for this lecture:
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

Видео MIT CompBio Lecture 03 - Hashing BLAST Database Search (Fall'19) канала Manolis Kellis