On the identification of conflicting contiguities in ancestral genome reconstruction

In computional biology, up-to-date homology-based methods for the reconstruction of ancestral gene orders usually rely on two phases. First, potential ancestral co-localizations of some genomic markers are detected from homologies between extant species. Next, the assembling phase mainly consists in resolving the conflicts between the potential ancestral features. This can be done using many methods, but one of the most advanced solutions is to identify and discard from the set of potential features those that belong to inclusivewise minimal conflicting sets of features. It relies on the consecutive ones property (C1P), and the notion of minimal conflicting set (MCS), widely used in physical mapping problems. Let C be a finite set of n elements and R= {r(1)‚ r(2)‚ . . . ‚ r(m)} a family of m subsets of C. A subset X of R satisfies the C1P if there exists a permutation P of C such that each r(i) in X is an interval of P. An MCS S ⊆ R is a subset of R that does not satisfy the C1P, but such that any of its proper subsets does. In this article, we present a new simpler and faster algorithm to decide if a given element r ∈ R belongs to at least one MCS. Our algorithm runs in O(n(2)m(2) + nm(7)), largely improving upon the current O(m(6)n(5)(m + n)(2) log(m + n)) fastest algorithm. The new algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs instead of Tucker matrices.