Homework 3 for Algorithms in Bioinformatics
- Out: Nov. 21, 2001
- Due: 1 week
- Problem 1
In Lecture 7 we defined the edit distance
of two strings A and B to be the minimum
number of insertions, deletions, and replacements required to
turn A into B. Prove that computing
the edit distance of two trings is a special case of the
string alignment problem. (That is, you have to prove
that a particular "alignment score table" corresponds to the
edit distance problem.)
- Problem 2
Give and justify an algorithm for computing an optimal
end-space free alignment of two strings A
and B in O(|A||B|) time and
O(|B|) space. You may assume that
an optimal alignment of A and B can be obtained
in O(|A||B|) time and
O(|B|) space.
- Problem 3
Give and justify an algorithm for computing an optimal
local alignment of two strings A
and B in O(|A||B|) time and
O(|B|) space. You may assume that
an optimal alignment of A and B can be obtained
in O(|A||B|) time and
O(|B|) space.
This set of webpages is maintained by Hsueh-I Lu
Number of accesses since August 11, 2001.
FastCounter by bCentral