Comparing Strings By Edit Distance
Motivation: The Human Genome Project. I.e., Do two genetic strings (E.g., DNA or Proteins) match? How are they related?
Abstraction: What is the cost of transforming s into t given a cost for
- insertion
- deletion
- substitution