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:
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:
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.
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:
More notions, references and details on the aspects touched upon in this lecture can be found in
Have a nice reading and self-study!
© Dipartimento di Matematica - Università di Trento