Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

VRP Assembler: Haplotype-Resolved de novo Assembly of Diploid and Polyploid Genomes Using Quantum Computing

Yibo Chen, Jun-Han Huang, Yuhui Sun, Yong Zhang, Yuxiang Li, Xun Xu

Published Jan 1, 2023• 2 citations
Publisher
DOI
10.2139/ssrn.4601824

Related papers

Quantum algorithm for de novo DNA sequence assembly based on quantum walks on graphs

Georgios D. Varsamis, Ioannis G. Karafyllidis, K.M. Gilkes +8 more

arXiv:2308.03532•Biosystems•Sep 19, 2023•6 citations

VRP Assembler: haplotype-resolved de novo assembly of diploid and polyploid genomes using quantum computing

Yibo Chen, Jun-Han Huang, Yuhui Sun +3 more

Abstract Precision medicine’s emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the VRP assembler: a novel approach that transforms this task into a vehicle routing problem, a combinatorial optimization problem solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google’s OR-Tools, achieving a haplotype-resolved assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to hifiasm with the phasing accuracy first approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.

•Oct 21, 2023•0 citations

Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing

Yibo Chen, Jun-Han Huang, Yuhui Sun +3 more

Precision medicine's emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the vehicle routing problem (VRP) assembler: an approach that transforms this task into a vehicle routing problem, an optimization formulation solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google's OR-Tools, achieving a haplotype-resolved local assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to Hifiasm with phasing accuracy approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.

Cell Reports Methods•Apr 12, 2024•10 citations

Quantum algorithms for genomic analysis in systems biology

Don Roosan, Hasiba Mahshed Khan, Rubayat Islam Khan

Elsevier eBooks•Jan 1, 2026•0 citations

Literature Review on Quantum Genomics: Applying Quantum Computing in Gene Editing

Amarachi Austin-Okoh, Rukayya Sambo Dangaji, Hauwa Bashir Largema +2 more

•Jan 1, 2025•0 citations

QHap: Quantum-Inspired Haplotype Phasing

Rui Zhang, Xian-Zhe Tao, Yibo Chen +12 more

Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.

q-bio.GNCross-listedarXiv:2603.25762•Mar 27, 2026
Abstract Precision medicine’s emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the VRP assembler: a novel approach that transforms this task into a vehicle routing problem, a combinatorial optimization problem solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google’s OR-Tools, achieving a haplotype-resolved assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to hifiasm with the phasing accuracy first approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.
Precision medicine's emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the vehicle routing problem (VRP) assembler: an approach that transforms this task into a vehicle routing problem, an optimization formulation solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google's OR-Tools, achieving a haplotype-resolved local assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to Hifiasm with phasing accuracy approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.
Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.