Consecutive Ones Property

The Consecutive Ones Property is as follows. You have a set of elements, and subsets of these elements that must be kept consecutive. Is there a linear ordering of the elements that respects these consecutivity constraints?

Example: let A, B, C, D, E be the elements, and ABE, CD, ADE be the subsets. In this case, the ordering CDAEB satisfies all the constraints.

Why is it called Consecutive Ones Property? Because if we write the elements vs. sets matrix, putting 1's exactly where an element belongs to a set, the problem becomes: find a permutation of the elements (rows) so that each set (column) has the 1's in consecutive positions.

In 1976, Booth and Lueker invented a data structure called PQ tree that can be built in linear time and stores efficiently all linear orderings that satisfy a group of constraints. "Linear time" here means proportional to N+M+R, where N is the number of elements, M is the number of constraints, and R is the sum of the sizes of the constraints.

What happens when there is no solution? Then there is no PQ tree either. However, my students and I invented an extended structure, called PQR tree, that coincides with the PQ tree when there are solutions, and exists even when there are no solutions.

There is a way of looking at the problem that makes sense regardless of the existence of a solution. There are some algebraic rules that allows one to construct more constraints from a group of constraints. For instance, the intersection of two sets must be consecutive if the two sets are consecutive in a linear ordering. There are more rules like that. We call a set collection COMPLETE when it is closed under such rules. Then PQR trees can be seen as alternative representations of complete collections.

I started looking at this problem because of DNA fragment assembly, which leads to interval graphs, which lead into the Consecutive Ones Property. Then I saw it applied to DNA physical mapping problems. But what attracted me was that Booth and Lueker's algorithm did not seem to me to be the final word on the problem.

Here are some of our papers on the subject:

• J. Meidanis, G. P. Telles. Building PQR trees in Almost-Linear Time. Accepted for GRACO, 2005. Improved, shortened version of tech report below. Download ps
• J. Meidanis, G. P. Telles. Building PQR trees in Almost-Linear Time. Technical Report 03-26. Institute of Computing, University of Campinas, 2003. Download gunzipped ps
• Guilherme Pimentel Telles. Um algoritmo quase-linear para árvores PQR e um esquema para clustering de seqüências expressas de cana-de-açúcar (In Portuguese) PhD Thesis, University of Campinas, December 2002. 90 pp. Download gunzipped ps
• J. Meidanis, O. Porto, G. P. Telles. On the consecutive ones property. Discrete Applied Mathematics, 88 (1998) 325-354. Doi reference. Early draft: Download gunzipped ps
• Guilherme Pimentel Telles. Propriedade dos Uns Consecutivos e Árvores PQR. (In Portuguese) Msc Thesis, University of Campinas, December 1997. 88 pp. Download gunzipped ps
• J. Meidanis and Erasmo G. Munuera. A theory for the consecutive ones property. Proceedings of WSP'96 - Third South American Workshop on String Processing. August, 8-9, 1996, pp. 194-202. Recife, Brazil. Early draft: Download gunzipped ps
• Erasmo G. Munuera. Propriedade dos Uns Consecutivos e Reconhecimento de Grafos Intervalo. (In Portuguese) MSc Thesis, University of Campinas, 1996. (I don't have a .ps of this work.)