Lecture in Computational Biology on 14 March 2002
Content of the lecture on 14 March 2002
First, I have exposed in detail the Dynamic Programming solution to the maximum length common subsequence problem introduced during the previous lecture.
Next, I have both informally and formally introduced some problems of similarity among strings. We saw three main kinds of such problems:
A very nice and quite high challange that we posed as possible homework already for the last time was the following: can you reduce the space complexity for finding a common subsequence of maximum length?
We decided that you can rest on this problem for the week-end.
I proposed an open research problem: find the minimum number of brakes to make a given line system good (in poly-time, of course). More details on this open problem, as well as other intriguing open problems in Computational Biology can be found in this paper (.pdf file) appeared in 2000 on Journal of Algorithms.
There is another problem that we begun proposing already in the previous lecture: try to put the algorithms seen for the maximum length common subsequence problem into real code. If you did not, then you can download from this Dynamic Programming codes page the c++ coding, done by Marco Rospocher, of the three solutions considered:
A last possible homework that we proposed was to design a dynamic programming algorithm for the global comparison among two strings problem as formalized through the notions of alignments and scores of alignments. Let me repeat what the formulation of the problem actually is: given two sequences, produce an alignment for them which achieves the maximum score.
More notions, references and details on Dynamic Programming can be found in the "Dynamic Programming" chapter of the book
Have a nice reading and self-study!
© Dipartimento di Matematica - Università di Trento