Skip to content
Close this search box.
Home ยป Dynamic Programming

Dynamic Programming

From Smith-Waterman to BLAST

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.

Introduction to Dynamic Programming

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.