An integer programming formulation of the parsimonious loss of heterozygosity problem

Area of Science:

• Genetics and Bioinformatics
• Computational Biology
• Human Disease Research

Background:

• Loss of heterozygosity (LOH) events, where an individual should be heterozygote but is not due to deletion polymorphisms, are crucial in human disease.
• Detecting deletion polymorphisms offers insights for developing novel diagnostics and treatments.
• The parsimonious loss of heterozygosity problem (PLOHP) aims to partition suspected polymorphisms into a minimum number of deletion areas.

Purpose of the Study:

• To generalize the PLOHP formulation, incorporating variable recombination rates and prior deletion location knowledge.
• To establish the computational complexity of the PLOHP.
• To develop an effective computational method for solving large-scale PLOHP instances.

Main Methods:

• Generalized the PLOHP formulation based on Halldórsson et al.'s work.
• Formulated PLOHP as a clique partition problem on undirected catch-point interval graphs.
• Developed a state-of-the-art integer programming (IP) formulation with valid inequalities.

Main Results:

• Proved the general NP-hardness of the PLOHP.
• Successfully solved real-world PLOHP instances with up to 9,000 individuals and 3,000 SNPs using the IP formulation.
• Demonstrated the effectiveness of the generalized formulation and IP approach for handling complex genetic data.

Conclusions:

• The study provides mathematical insights into the PLOHP.
• The developed IP formulation offers an efficient exact solution for large datasets.
• Results pave the way for improved diagnostics and treatments by better understanding deletion polymorphisms.