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:

Joao Meidanis
Last modified: Wed Jul 21 10:28:42 BRT 2010 by JM