Murray Patterson

Department of Computer Science, University of British Columbia

Variants of the Consecutive-Ones Property Motivated by the Reconstruction of Ancestral Species

The polynomial-time decidable Consecutive-Ones Property (C1P) of binary matrices, formally introduced in 1965 by Fulkerson and Gross, has since found applications in many areas. A binary matrix M has the C1P if the columns of M can be permuted such that for each row, the set of columns containing 1 in this row appear consecutively in this order. Here we consider the C1P in the context of the reconstruction of Ancestral Gene Orders (AGOs) [Ma et al., 2006; Chauve and Tannier, 2008]. The problem with the reconstruction of AGOs, as is the case with many other applications of the C1P, is that it often involves handling matrices that do not have the C1P. Here we propose and study three ways of generalizing the C1P in order to address this problem.

We first propose the Gapped C1P, or the (k,delta)-C1P: a binary matrix M has the (k,delta)-C1P for integers k and delta if the columns of M can be permuted such that each row contains at most k blocks of 1's and no two neighboring blocks of 1's are separated by a gap of more than delta 0's. The C1P is equivalent to the (1,0)-C1P. Here we show that for every bounded and unbounded k >= 2, delta >= 1, (k,delta) =/= (2,1), deciding the (k,delta)-C1P is NP-complete [Goldberg, 1995]. We also provide an algorithm for a relevant case of the (2,1)-C1P. We then study the (k,delta)-C1P with a bound d on the maximum number of 1's in any row (the maximum degree of M). We show that the (d,k,delta)-C1P is polynomial-time decidable when all three parameters are fixed constants. We then show that the remaining non-trivial cases of the (d,k,delta)-C1P are NP-complete to decide. The third generalization of the C1P we introduce is a variant where columns of M may appear multiple times in a permutation. We show that this problem is NP-complete to decide, and then give a tractability result that is motivated by handling telomeres in the reconstruction of ancestral species.