Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing.
Cell Rep Methods
; 4(5): 100754, 2024 May 20.
Article
in En
| MEDLINE
| ID: mdl-38614089
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 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.
Key words
Full text:
1
Collection:
01-internacional
Database:
MEDLINE
Main subject:
Polyploidy
/
Haplotypes
/
Diploidy
Limits:
Humans
Language:
En
Journal:
Cell Rep Methods
Year:
2024
Document type:
Article
Affiliation country:
Country of publication: