A binary matrix M has the Consecutive-Ones Property (C1P) if its columns can be ordered in such a way that all 1's in each row are consecutive. We consider here a variant of the C1P where columns can appear multiple times in the ordering (the multiplicity of a column is the number of times it appears in M). Although the general problem of deciding the C1P with multiplicity is NP-complete, we present here a case of interest in comparative genomics that is tractable.

We first give a tractability result for a family of matrices M where every row of M has (i) at most one entry 1 in columns with multiplicity greater than one, or (ii) exactly two entries 1 in columns with multiplicity greater than one and no other entries. This result is motivated by handling telomeres in ancestral gene order reconstruction. Our proofs rely on two classical concepts: PQ-trees and Eulerian cycles in graphs.