MIT CompBio Lecture 03 - Database Search

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 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: https://stellar.mit.edu/S/course/6/fa18/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture03_SequenceAlignment/Lecture03_SequenceAlignment_6up.pdf