Haplotype Inference with Pure Parsimony: A Quantum Computing Approach

Haplotype inference with pure parsimony (HIPP) problem seeks to reconstruct a minimum set of haplotypes that explain a given set of genotypes observed from a population. This important problem is known to be NP-hard. In this paper, we explore the potential of quantum computing in retrieving optimal...

Full description

Saved in:
Bibliographic Details
Main Authors: Nghiem, Nguyen-Viet-Dung, Le, Sy-Vinh, Nguyen, Tu N., Dinh, Thang N.
Format: Conference Proceeding
Language:English
Subjects:
Annealing
Haplotype inference
Quantum advantage
Quantum annealing
Qubit
Simulated annealing
Sociology
Software
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Haplotype inference with pure parsimony (HIPP) problem seeks to reconstruct a minimum set of haplotypes that explain a given set of genotypes observed from a population. This important problem is known to be NP-hard. In this paper, we explore the potential of quantum computing in retrieving optimal solutions for HIPP. We investigate several approaches to encode HIPP into quadratic unconstrained binary optimization (QUBO), which can be solved on quantum annealers. Further, we propose a new QUBO for HIPP, termed QHI, exploiting the structure of HIPP to reduce the QUBO size. Our comprehensive experiments on the state-of-the-art D-Wave annealer indicate comparable solution quality for quantum annealing approaches compared to classical simulated annealing. They also validate the effectiveness of our proposed QHI formulation in both solution quality and size.
ISSN:1938-1883
DOI:10.1109/ICC51166.2024.10622443