This lecture from Dr. Jeremy Buhler discusses the limitations of the Smith-Waterman local alignment algorithm and the heuristics used by the BLAST program in order to reduce the search space and to quickly produce high-scoring local alignments.
Developed by Dr. Anton E. Weisstein (Truman State University) and Mingchao Xie (TA for Bio 4342), this lecture and exercise introduce students to the core algorithm (dynamic programming) used by many sequence alignment tools (e.g., BLAST). The exercise includes a spreadsheet with a dynamic programming matrix that allows students to explore the impact of different types of alignments (i.e. global, semiglobal, and local) and scoring systems on the resulting sequence alignment.
