Lecture in Computational Biology on 25 March 2002
Content of a lecture on 25 March 2002
In this lecture,
we have exposed an algorithm for the
recognition of matrices with the consecutive ones property.
The motivation for the study of this problem
came out from an approach to Physical Mapping:
Hybridization Mapping.
More precisely, within Hybridization Mapping,
two models from
algorithmic graph theory and combinatorics which prove to be of
pertinence are.
- Interval Graph Recognition;
- Recognition of matrices with the consecutive ones property.
While the first model would lead to a classic topic in algorithmic
graph theory,
in this lecture we preferred to concentrate on the second model
and tried to understand together
an algorithm for the
recognition of matrices with the consecutive ones property
as exposed in Chapter 5 of the following book.
- J.C. Setubal and J. Meidanis,
Introduction to Computational Molecular Biology,
PWS Publishing Company.
An International Thomson Publishing Company, (1997)
To better appreciate the underlying philosophy
of the algorithm, we first
managed to find out a polynomial-time algorithm to decide whether
a given input graph is bipartite and discussed
about the general stucture of this simple algorithm.
There is no relation between these two problems,
but we wanted to have a reference to what is a recognition
algorithm
in a certain sense.
We then tried to dig out some of the difficulties
of the consecutive ones property problem
to motivate the general architecture of the algorithm.
This lead us to define the components of the problem
and to suggest the following approach:
first, solve each component separately, then merge the solutions
from the different components.
We then filled in the details of the first and the second phase,
by also giving a few examples.
Homeworks
The algorithm we have seen today is by no means
a trivial algorithm.
My first ambition in today's lecture was to provided you with the key
to better appreciate the general philosophy of the algorithm.
I think it would now pay a lot if you could find the time
to come back to the algorithm and check it in its finest details.
The algorithm for the
recognition of matrices with the consecutive ones property
is exposed in Chapter 5 of the following book.
- 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!
P.S.
Some of you could not attend today's lecture
until the end.
But even if you did attend the lecture until the end,
you may be interested
in a second chance to think again about the algorithm
together with others.
We will fix such an extra lecture after Easten.
Clearly,
in that lecture we will also be free to enter further issues and topics,
as your curiosity will ask for.
|
25-March-2002
|
© Dipartimento di Matematica - Università di Trento
|