Lecture in Computational Biology on 21 March 2002
Content of a lecture on 21 March 2002
We considered two main approaches to Physical Mapping:
Within Restriction Site Mapping we considered two
possible approaches and the corresponding models:
- Restriction Site Mapping;
- Hybridization Mapping.
We informally discussed about the computational complexity of both
- Partial Digest;
- Double Digest.
Within Hybridization Mapping,
we came to consider two models from
algorithmic graph theory and combinatorics which prove to be of pertinence.
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.
- Interval Graph Recognition;
- Recognition of matrices with the consecutive ones property.
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
- Find a polynomial-time algorithm to decide whether
a given input graph is bipartite.
An extremely good introduction to the problems
by Physical Mapping in the context of Computational Molecular Biology
is given in Chaper 5 of the book recommended as a companion for this
- 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!
© Dipartimento di Matematica - Università di Trento