VRP Assembler: haplotype-resolved de novo assembly of diploid and polyploid genomes using quantum computing
Chen, Y.; Huang, J.-H.; Sun, Y.; Zhang, Y.; Li, Y.; Xu, X.
Show abstract
Precision medicines 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 Googles 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.
Matching journals
The top 4 journals account for 50% of the predicted probability mass.
Similar papers in this journal
- Rapid Reconstruction of Time-varying Gene Regulatory Networks with Limited Main Memory 95%
- Improved DNA-versus-Protein Homology Search for Protein Fossils 95%
- TMELand: An end-to-end pipeline for quantification and visualization of Waddington's epigenetic landscape based on gene regulatory network 95%
"Similar papers" are the closest papers from that journal in the model's embedding space. They show what the match is built on, but the ranking comes mostly from a classifier over the whole training set, not from these examples alone.