**
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)

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).

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*

Have a nice reading and self-study!

14-March-2002 |
© Dipartimento di Matematica - Università di Trento |