While an extinct species cannot be sequenced, if we are given a phylogeny tree containing this species we can reconstruct its genome using the data from a set of its derived, extant species. This is done by the following encoding of the genomic information of these extant species in a binary matrix: each column of the matrix represents a genomic marker (DNA sequence, etc.) that is believed to have been present and unique in the considered unsequenced genome, and each row of the matrix represents a set of markers that are believed to have been contiguous along a chromosome of the unsequenced genome. The goal is then to find one (or several if possible) total orders on the markers that respect all rows (i.e., that keep all entries 1 together in each row). This is the combinatorial problem of determining if this binary matrix has the Consecutive-Ones Property (C1P). While determining if a matrix has the C1P can be done in linear time, common problem in such applications is that matrices obtained from experiments do not have the C1P, due to small errors in this encoding.

In this talk I will first define formally the C1P, and then the various relaxations of the C1P that we have considered in order to deal with the small errors in experimental data. It turns out that, along with most of the other ways researchers have dealt with non-C1P matrices, most of the relaxed problems considered here are computationally (NP-) hard. I will present these NP-hardness results, as well as the algorithmic results, and then discuss the open problems and possible future avenues of this research.