Pairwise similarity
Over the course of evolution DNA sequences mutate:
- changes in nucleotide sequence
- insertions or deletions of nucleotides
Sequence similarity is calculated by dynamic programming
Efficiency: O(n2)
Shortcut: Lookup table
http://home.cc.umanitoba.ca/~frist/Seminars/iims02/iims02.html