In genomic research, scientists are like puzzle solvers trying to piece together a full genetic "blueprint" from countless small DNA fragments. This process, known as genome assembly, is particularly intimidating for polyploid organisms that have multiple sets of chromosomes. The task requires accurately reconstructing the genome from these scattered pieces, a process termed haplotype assembly.

Haplotype assembly is vital for understanding genetic traits, disease susceptibility, drug response predictions, and tracing species' evolutionary history. Given the computational complexity and enormous data involved, achieving accurate assembly remains a significant challenge in bioinformatics.

Researchers from BGI-Research have developed a ground-breaking solution by translating the haplotype assembly challenge into an optimization problem solvable by quantum computing. They introduced the VRP assembler, a tool that leverages quantum computing technology to tackle this issue.

Schematic diagram of the VRP assembler.

The team proposed a mathematical model suitable for haploid, diploid, and polyploid genome assemblies, achieving high-precision results on the human major histocompatibility complex (MHC) region. These findings, published in April 2024 in Cell Reports Methods, showcase quantum computing's potential in revolutionizing life science research by facilitating complex genome analysis, enriching precision medicine, biodiversity, and evolutionary studies.

The research “Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing” was published in Cell Reports Methods.

The VRP assembler concept is inspired by the Vehicle Routing Problem (VRP) in logistics, where the optimal routes for a set of "vehicles" to visit "customers" and return are determined. Here, each "vehicle" represents a DNA sequence within a haplotype, and "customers" are the sequencing reads. The assembler finds the optimal way to arrange these sequencing reads in the correct sequence and the correct order. Quantum computing's ability to process exponential information simultaneously allows it to consider multiple potential combinations at once, significantly speeding up the solution to such complex optimization tasks.

Utilizing the D-Wave quantum annealing device, the research team conducted small-scale haplotype assemblies on synthetic diploid and triploid genomes, achieving a reduction in processing time by three orders of magnitude compared to traditional algorithms. This represents a major leap in the intersection of quantum computing and bioinformatics.

D-Wave quantum annealing device completes small-scale  proof of concept on synthetic diploid and triploid.

Further testing combined OR-Tools with the VRP assembler for haplotype assembly of about 5 million base pairs in the human MHC region. The results indicated a switch error rate drops to the theoretical limit, crucial for identifying genetic variations and understanding their impact on health. Quantum computing's acceleration capabilities enable the VRP assembler to handle vast genomic data efficiently and accurately.

VRP assembler combined with OR-Tools completes high-precision haplotype assembly on the human MHC region[1].

As quantum technology continues to develop, we are poised at a historic juncture where quantum computing deeply integrates with life sciences. Quantum computing, a novel computing paradigm, promises to overcome computational limits of the post-Moore era, offering innovative solutions to the high-dimensional data challenges in biology.

Looking forward, quantum technology will empower bioinformatics processing, disease mechanism exploration, and new drug development through following fields:

·       Quantum Bioinformatics: Quantum algorithms can handle complex, high-dimensional biological data (e.g., genomics, transcriptomics, proteomics), helping researchers rapidly identify disease-related genes and unravel complex disease molecular mechanisms, supporting precision medicine.

·       Quantum Simulation in Biological Research: Quantum computing can simulate biological molecules and cellular quantum behaviours with unprecedented precision and scale, advancing our understanding of quantum effects in biological processes such as neuroscience and photosynthesis.

·       Quantum Precision Measurement in Biomedical Detection: Quantum precision measurement technologies provide unmatched accuracy in biological marker detection and disease diagnosis, enhancing disease diagnostic accuracy through more sensitive medical testing.

This research underscores quantum computing's vital role in life science applications, promising profound impacts on genomics and broader life science fields as quantum hardware and algorithms continue to advance.

For more details, see the published article in Cell Reports Methods.

[1] Chen, Y., Huang, J.H., Sun, Y., Zhang, Y., Li, Y., Xu, X. Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing. Cell Reports Methods 4, 100754 (2024).