Lecture in Computational Biology on 21 March 2002

Lecture in Computational Biology on 21 March 2002

Content of a lecture on 21 March 2002

We considered two main approaches to Physical Mapping:

Restriction Site Mapping;
Hybridization Mapping.

Within Restriction Site Mapping we considered two possible approaches and the corresponding models:

Partial Digest;
Double Digest.

We informally discussed about the computational complexity of both models.

Within Hybridization Mapping, we came to consider two models from algorithmic graph theory and combinatorics which prove to be of pertinence.

Interval Graph Recognition;
Recognition of matrices with the consecutive ones property.

In the next lecture we will expose an algorithm for the recognition of matrices with the consecutive ones property. To be more prepared to appreciate this algorithm, I suggest you to consider the third exercise in the list here below.

Homeworks

We assigned the following homeworks:

Give an NP-completeness proof of the fact that the Double Digest Problem is NP-complete;
Find a $2$-approximation algorithm for the MAX-CUT problem;
Find a polynomial-time algorithm to decide whether a given input graph is bipartite.

An extremely good introduction to the problems arisen by Physical Mapping in the context of Computational Molecular Biology is given in Chaper 5 of the book recommended as a companion for this introductory course:

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

Have a nice reading and self-study!

20-March-2002