Lecture in Computational Biology on 18 March 2002
Content of the lecture on 18 March 2002
We have found together a Dynamic Programming solution
to the problem of the global comparison between two strings
introduced in the previous lecture.
This problem has other equivalent names like:
- computing the edit distance between two strings;
- find an optimal global alignment of two given strings.
The algorithm we have found (as also described in the Setubal and
Meidanis book)
uses O(mn) time and O(mn) space.
We then considered a faster algorithm for the case
when the two input strings are similar.
Finally, with reference to the maximum common subsequence problem,
we exposed Hirshberg solution to reduce the space complexity
from O(mn) to O(min{m,n}) while at most doubling the running time
requirements.
The content of our lecture is covered in Chapter 3
of the book:
- J.C. Setubal and J. Meidanis,
Introduction to Computational Molecular Biology,
PWS Publishing Company.
An International Thomson Publishing Company, (1997)
Hirschberg's innovative solution appeared in:
- D. Hirschberg,
A linear space algorithm for computing maximal common
subsequences,
Communications of the ACM, 18: 341-343 (1975)
Homework
Come back to Hirschberg solution and make sure
you understand as much as possible of it.
To prompt your insight,
try to apply Hirschberg solution to the global comparison
between two strings problem as well.
Have a nice investigation!
|
18-March-2002
|
© Dipartimento di Matematica - Università di Trento
|