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

Luciano Porretta (), Daniele Catanzaro (), Bjarni V. Halldórsson () and Bernard Fortz ()
Additional contact information
Luciano Porretta: Université Libre de Bruxelles (ULB)
Daniele Catanzaro: Université Catholique de Louvain (UCL)
Bjarni V. Halldórsson: Reykjavk University
Bernard Fortz: Université Libre de Bruxelles (ULB)

4OR, 2019, vol. 17, issue 1, No 3, 75-96

Abstract: Abstract A point-interval $$(I_v, p_v)$$ ( I v , p v ) is a pair constituted by an interval $$I_v$$ I v of $${\mathbb {R}}$$ R and a point $$p_v \in I_v$$ p v ∈ I v . A graph $$G=(V,E)$$ G = ( V , E ) is a Max-Point-Tolerance (MPT) graph if each vertex $$v\in V$$ v ∈ V can be mapped to a point-interval in such a way that (u, v) is an edge of G iff $$I_u \cap I_v \supseteq \{p_u, p_v\}$$ I u ∩ I v ⊇ { p u , p v } . MPT graphs constitute a superclass of interval graphs and naturally arise in genetic analysis as a way to represent specific relationships among DNA fragments extracted from a population of individuals. One of the most important applications of MPT graphs concerns the search for an association 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 $${{\mathcal {N}}}{{\mathcal {P}}}$$ N P -hard combinatorial 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–30 $$\times $$ × 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.

Keywords: Clique partitioning; Max point tolerance graphs; Column generation; Branch-and-price; Computational biology; Loss of heterozygosity; 90C1; 90C27 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0377-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:17:y:2019:i:1:d:10.1007_s10288-018-0377-3

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0377-3

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().