Molecular Biophysics & Biochemistry 447b3 / 747b3Bioinformatics

Aligning Text Strings

Dynamic Programming

Step 1 -- Make a Dot Plot (Similarity Matrix)

A More Interesting Dot Matrix

Step 2 -- Start Computing the Sum Matrix

Step 3 -- Keep Going

Step 4 -- Sum Matrix All Done

Step 5 -- Traceback

Step 6 -- Alternate Tracebacks

Key Idea in Dynamic Programming

Computational Complexity

Gap Penalties

Step 2 -- Computing the Sum Matrix with Gaps

Similarity (Substitution) Matrix

Where do matrices come from?

The Score

Molecular Biology Information:Macromolecular Structure

Molecular Biology Information: Protein Structure Details

Sperm Whale Myoglobin

Structural Alignment of Two Globins

Immunoglobulin Alignment (Harder)

Some Similarities are Readily Apparent others are more Subtle

Automatic Structural Alignment

Generalized Similarity Matrix

Similarity Matrixfor Structural Alignment