A Branch & Price algorithm for the minimum cost clique cover problem in max-point tolerance graphs

A point-interval (Iv , pv ) is a pair constituted by an interval Iv of R and
a point pv ∈ Iv . A graph G = (V, E) is a Max-Point-Tolerance (MPT) graph if
each vertex v ∈ V can be mapped to a point-interval in such a way that (u, v) is
an edge of G iff Iu ∩ Iv ⊇ {pu , pv }. MPT graphs constitute a superclass of interval
graphs and naturally arise in genetic analysis as a way to represent specific rela-
tionships among DNA fragments extracted from a population of individuals. One
of the most important applications of MPT graphs concerns the search for an asso-
ciation between major human diseases and chromosome regions from patients that
exhibit loss of heterozygosity events. This task can be formulated as a minimum
cost clique cover problem in a MPT graph and gives rise to a N P-hard combi-
natorial optimization problem known in the literature as the Parsimonious Loss
of Heterozygosity Problem (PLOHP). In this article, we investigate ways to speed
up the best known exact solution algorithm for the PLOHP as well as techniques
to enlarge the size of the instances that can be optimally solved. In particular, we
present a Branch&Price algorithm for the PLOHP and we develop a number of
preprocessing techniques and decomposition strategies to dramatically reduce the
size of its instances. Computational experiments show that the proposed approach
is 10-30x faster than previous approaches described in the literature, and suggest
new directions for the development of future exact solution approaches that may
prove of fundamental assistance in practice.