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

Luciano Porretta; Daniele Catanzaro; Bjarni V. Halldórsson; Bernard Fortz

doi:10.1007/s10288-018-0377-3

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

Luciano Porretta^*, Daniele Catanzaro, Bjarni V. Halldórsson, Bernard Fortz

^*Corresponding author for this work

Reykjavik University

Reykjavik University, Iceland

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

A point-interval(I _v , p _v ) is a pair constituted by an interval I _v of R and a point p _v ∈ I _v . 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 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 NP-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× 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.

Original language	English
Pages (from-to)	75-96
Number of pages	22
Journal	4OR
Volume	17
Issue number	1
DOIs	https://doi.org/10.1007/s10288-018-0377-3
Publication status	Published - 14 Mar 2019

Bibliographical note

Funding Information:
Part of this work has been developed when L. Porretta and D. Catanzaro were visiting both Reykjavik University and DeCODE Genetics. L. Porretta acknowledges support from the Belgian National Fund for Scientific Research (FRS-FNRS) who funded his short-term research visit. D. Catanzaro acknowledges support from the FRS-FNRS via the grant ?Cr?dit de Recherche? Ref. S/25-MCF/OL J.0026.17, the Universit? Catholique de Louvain via the ?Fonds Sp?ciaux de Recherche? (FSR) 2017?2019, the Fondation Louvain via the grant ?Le num?rique au service de l?humain?, and the computational resources provided by the ?Consortium des equipements de Calcul Intensif? (CCI), funded by the FRS-FNRS via the Grant Ref. 2.5020.11. The authors thank the anonymous referees for their valuable suggestions.

Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature.

Other keywords

Branch-and-price
Clique partitioning
Column generation
Computational biology
Loss of heterozygosity
Max point tolerance graphs

Access to Document

10.1007/s10288-018-0377-3

Cite this

@article{e100d2e80fb04ca283cf91b88ba845d9,

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

abstract = " A point-interval(I v , p v ) is a pair constituted by an interval I v of R and a point p v ∈ I v . 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 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 NP-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× 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 = "Branch-and-price, Clique partitioning, Column generation, Computational biology, Loss of heterozygosity, Max point tolerance graphs",

author = "Luciano Porretta and Daniele Catanzaro and Halld{\'o}rsson, {Bjarni V.} and Bernard Fortz",

note = "Funding Information: Part of this work has been developed when L. Porretta and D. Catanzaro were visiting both Reykjavik University and DeCODE Genetics. L. Porretta acknowledges support from the Belgian National Fund for Scientific Research (FRS-FNRS) who funded his short-term research visit. D. Catanzaro acknowledges support from the FRS-FNRS via the grant ?Cr?dit de Recherche? Ref. S/25-MCF/OL J.0026.17, the Universit? Catholique de Louvain via the ?Fonds Sp?ciaux de Recherche? (FSR) 2017?2019, the Fondation Louvain via the grant ?Le num?rique au service de l?humain?, and the computational resources provided by the ?Consortium des equipements de Calcul Intensif? (CCI), funded by the FRS-FNRS via the Grant Ref. 2.5020.11. The authors thank the anonymous referees for their valuable suggestions. Publisher Copyright: {\textcopyright} 2018, Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2019",

month = mar,

day = "14",

doi = "10.1007/s10288-018-0377-3",

language = "English",

volume = "17",

pages = "75--96",

journal = "4OR",

issn = "1619-4500",

publisher = "Springer",

number = "1",

}

TY - JOUR

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

AU - Porretta, Luciano

AU - Catanzaro, Daniele

AU - Halldórsson, Bjarni V.

AU - Fortz, Bernard

N1 - Funding Information: Part of this work has been developed when L. Porretta and D. Catanzaro were visiting both Reykjavik University and DeCODE Genetics. L. Porretta acknowledges support from the Belgian National Fund for Scientific Research (FRS-FNRS) who funded his short-term research visit. D. Catanzaro acknowledges support from the FRS-FNRS via the grant ?Cr?dit de Recherche? Ref. S/25-MCF/OL J.0026.17, the Universit? Catholique de Louvain via the ?Fonds Sp?ciaux de Recherche? (FSR) 2017?2019, the Fondation Louvain via the grant ?Le num?rique au service de l?humain?, and the computational resources provided by the ?Consortium des equipements de Calcul Intensif? (CCI), funded by the FRS-FNRS via the Grant Ref. 2.5020.11. The authors thank the anonymous referees for their valuable suggestions. Publisher Copyright: © 2018, Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2019/3/14

Y1 - 2019/3/14

N2 - A point-interval(I v , p v ) is a pair constituted by an interval I v of R and a point p v ∈ I v . 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 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 NP-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× 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.

AB - A point-interval(I v , p v ) is a pair constituted by an interval I v of R and a point p v ∈ I v . 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 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 NP-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× 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.

KW - Branch-and-price

KW - Clique partitioning

KW - Column generation

KW - Computational biology

KW - Loss of heterozygosity

KW - Max point tolerance graphs

UR - http://www.scopus.com/inward/record.url?scp=85048125899&partnerID=8YFLogxK

U2 - 10.1007/s10288-018-0377-3

DO - 10.1007/s10288-018-0377-3

M3 - Article

AN - SCOPUS:85048125899

SN - 1619-4500

VL - 17

SP - 75

EP - 96

JO - 4OR

JF - 4OR

IS - 1

ER -

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

Abstract

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this