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