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:

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:

Hirschberg's innovative solution appeared in:


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