Lecture in Computational Biology on 13 March 2002

Lecture in Computational Biology on 13 March 2002

Content of the lecture on 13 March 2002

First, Riccardo has completed the introductive biological discussion on the basic mechanisms in cells which consent to duplicate and transmit the information of life. In particular, he has discussed the role of the genetic code. If you are interested in knowing more about these topics, we refer to Chapter 1 of the book:

J.C. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company. An International Thomson Publishing Company, (1997)

More notions, references and details on the aspects touched upon in the talk of Riccardo can be found in this .pdf file

Next, I have informally introduced the notions of algorithm, problem, space and time computational complexity, polynomial algorithm. We have mentioned the notion of NP-completeness. We have introduced and discussed two important algorithm design techniques:

divide & impera;
Dynamic Programming.

We have introduced the maximum length common subsequence problem. We have considered a few natural self-reductions of the problem. We have observed that these self-reductions were not good enough to obtain a poly-time algorithm through the divide & impera methodology.
However, by recursion with memoization, we have solved the problem in O(mn) time and O(mn) space. We have also indicated how to derive from this approach a Dynamic Programming solution to the problem.

Homeworks

A very nice and quite high challange that we posed as possible homework is the following: can you reduce the space complexity for finding a common subsequence of maximum length?

More modestly, we proposed also to try to put the algorithms discussed during the lecture 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 presented in this lecture:

simple recursion (exponential);
recursion with memoization (polynomial);
Dynamic Programming (polynomial).

At the same page you can also find the same three levels of solution and coding for another example (chain matrix multiplication) of Dynamic Programming as discussed in the Cormen et al. book (see reference here below). At the same page you can also find the proposal of coding one of the three (or all the three approaches) for the editing distance problem.

More notions, references and details on the aspects touched upon in this lecture can be found in

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L., Introduction to Algorithms, MIT Press, Cambridge, MA; McGraw-Hill Book Co., New York (1990) ISBN 0-262-03141-8

In particular, we are recommending the chapter on Dynamic Programming.

Have a nice reading and self-study!

14-March-2002