Pangenome-guided sequence assembly via binary optimization

Journal article

De novo genome assembly is challenging in highly repetitive regions; however, reference-guided assemblers often suffer from bias. We propose a framework for pangenome-guided sequence assembly that can resolve short-read data in complex regions without bias towards a single reference genome. Our primary contribution is to frame the assembly as a graph traversal optimization problem, which can be implemented classically or on a quantum computer. The workflow involves first annotating pangenome graphs with estimated copy numbers for each node, then finding a path on the graph that best explains those copy numbers. On simulated data, our approach significantly reduces the number of contigs compared with de novo assemblers. While they introduce a small increase in inaccuracies, such as false joins, our optimization-based methods are competitive with current exhaustive search techniques. They are also designed to scale more efficiently as the problem size grows and will run effectively on future quantum computers; a small experiment on a real quantum device showcases this behaviour. Moreover, they are more resilient to noise in copy number estimation inherent in short-read-based assembly. We also develop novel tools for creating realistic synthetic pangenomes, aligning reads to pangenomes and for evaluating assembly quality.

Authors: Cudby, J; Bonfield, J; Zhou, C; Durbin, R; Strelchuk, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Oxford University Press
• Journal: Briefings in Bioinformatics
• Volume: 27
• Issue: 1
• Article number: bbag084
• Publication date: 2026-02-26
• Acceptance date: 2026-01-24
• DOI: 10.1093/bib/bbag084
• EISSN: 1477-4054
• ISSN: 1467-5463
• Language: English
• Keywords: quantum algorithms; optimization; pangenomics; assembly