On matrices that do not have the consecutive ones property

A binary matrix has the consecutive ones property if its columns can be ordered in such a way that, in each row, all 1s are consecutive. This classical combinatorial notion has been central in genomic problems such as physical mapping or paleogenomics. In these fields, genomes that cannot be sequenced are represented by a matrix that has the consecutive ones property, but are inferred from an initial matrix that does not have this property due to errors. In this work, we study combinatorial and algorithmic characterizations of matrices that do not have the consecutive ones property. We review existing results and propose new results centered around the notion of minimal conflicting sets.