DNA Sequence Alignment

DNA Sequence Alignment (aka “Longest Common Subsequence”)

What is a DNA sequence

DNA similarity

Why is DNA similarity important

What is DNA sequence alignment?

Moving to English words

Naïve algorithm

Naïve Algorithm – Running Time

Dynamic Approach – A table

e.g. ‘a’ vs. ‘s’

An example

Example with solution

Pseudocode (bottom-up)

Pseudocode (top-down)

Running time

Idea of dynamic
programming