Pangenome-guided sequence assembly via binary optimisation

Josh Cudby, James Bonfield, Chenxi Zhou, Richard Durbin, Sergii Strelchuk · 2025

Read Pangenome-guided sequence assembly via binary optimisation by Josh Cudby, James Bonfield, Chenxi Zhou, Richard Durbin, Sergii Strelchuk (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08200.txt.

Introduction

Josh Cudby, James Bonfield, Chenxi Zhou, Richard Durbin, and Sergii Strelchuk present a new way to build genome sequences. Their 2025 paper uses a pangenome, a graph that holds variation across many genomes. Building a genome from scratch is hard in repeat-rich regions. Using one reference can bias the result.

Their method first marks each node of the graph with an estimated copy count from short reads. It then finds the path through the graph that best fits those counts. The task is framed as a binary choice problem that can run on classical or quantum machines. On test data, it cut the number of pieces sharply versus from-scratch tools. It also handled noisy counts well.

Catalog record

CREATORJosh Cudby, James Bonfield, Chenxi Zhou, Richard Durbin, Sergii Strelchuk
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08200

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pangenome-guided sequence assembly via binary optimisation Josh Cudby, James Bonfield, Chenxi Zhou, Richard Durbin, Sergii Strelchuk Abstract 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, which can resolve short-read data in complex regions without bias towards a single reference genome. Our method frames assembly as a graph traversal optimisation problem, which can be implemented on quantum computers. The pipeline first annotates pangenome graphs with estimated copy numbers for each node, then finds a path on the graph that best explains those copy numbers. On simulated data, our approach significantly reduces the number of contigs compared to de novo assemblers. While it introduces a small increase in inaccuracies, such as false joins, our optimisation-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. 1 Introduction A single linear reference genome cannot capture the genome variation that occurs within species, whether the variation is local, such as Single Nucleotide Variants (SNVs), or larger structural changes, for example Copy Number Variations (CNVs) [ 1 ] . Bioinformatic pipelines often include a step where a new sample is compared to a reference; for example, in variant detection. When a single reference is used, reference bias is inevitable: a tendency to report fragments of sequence that appear in the reference, and to miss novel or highly divergent regions [ 1 , 2 , 3 ] . The solution is to use references that capture genomic diversity; the study of such objects is pangenomics. Pangenomics is a relatively young field, and there is no unified description of the various forms and construction methods of pangenomes. Indeed, the term “pangenome” is also applied to representations that separate the core and accessory genes present in bacterial species [ 4 ] , a completely different setting than we are interested in. According to the conventions set out by Matthews et al. [ 5 ] , we focus on sequence-oriented pangenome graphs , which we henceforth refer to simply as pangenomes or pangenome graphs. These objects describe the location and nature of genomic variation within a collection of individuals, most commonly from the same species. As the name suggests, they are described by mathematical graphs consisting of a set of nodes , representing fragments of sequence, connected by edges , representing fragments that are adjacent within a genome. These graphs can be created by popular tools such as vg [ 6 ] , pggb [ 7 ] and minigraph [ 8 ] . The Human Pangenome Reference Consortium (HPRC) recently published an initial human pangenome [ 7 ] containing data from 47 individuals, with a follow-up data release of more than 200 genomes available online. Due to dramatic reductions in the cost of next-generation sequencing, we now have whole-genome shotgun short-read data for millions of human genomes. Using a pangenome to reconstruct the full sequences of these samples would be preferable to using standard references such as GRCh38 [ 9 ] or performing incomplete de novo assembly. A toolkit dedicated to providing this functionality is not currently available, though some software kits use pangenomes in other ways. DRAGEN [ 10 ] performs variant detection by mapping reads against a pangenome before mapping back to a comparison against a single reference genome. Pasa [ 11 ] uses pangenomes as a source of global information to resolve assemblies with a large number of contigs into a single sequence. Here we propose a methodology for solving pangenome-guided sequence assembly by directly mapping reads onto a pangenome, then recasting assembly as a graph traversal problem. In most of the genome, traversal is trivial. We focus on highly complex regions of the pangenome graph. A sketch of our pipeline is shown in fig. 1 , and consists of 4 steps: 1. Short reads are aligned onto nodes of a pangenome. 2. Copy numbers for each node are estimated from the coverage data. 3. A path through the pangenome graph that best explains the copy numbers is found. 4. The corresponding sequence is extracted and optionally post-processed to improve assembly quality. Figure 1 : A sketch of the pangenome-guided sequence assembly procedure. (Upper-left) A pangenome graph and a set of short reads sequenced from a new individual. (Upper-right) Reads are aligned onto nodes of the graph. (Lower-left) Copy numbers are estimated from the coverage of each node. (Lower-right) A path that best explains the data is found, and the corresponding sequence is extracted. The key computational task in the pipeline is the path-finding in step 3. This problem is similar to those tackled by certain de novo genome assemblers like Flye [ 12 ] and Oatk [ 13 ] , which aim to resolve repeat-induced non-linear structures in assembly graphs. Their approach typically involves estimating the copy numbers of repeat sequences from sequence coverage and then identifying a graph traversal that satisfies these copy number constraints. In the context of pangenome graphs, however, additional complexities arise. First, due to genomic divergence, a pangenome graph does not fully represent the target genome, necessitating imputation of missing or divergent regions. Second, read mapping to a pangenome graph is inherently noisier, largely due to its repetitive and multi-genome nature, resulting in greater uncertainty in sequence coverage and, consequently, in copy number estimates. To accurately resolve the graph paths through repetitive regions, pangenome-based methods must be more robust to such noise. To that end, we formalise the path-finding problem as an optimisation problem. The optimisation may be viewed as a generalisation of the Hamiltonian path problem and is {\mathsf{NP}} -hard in general. We cast it as a Quadratic Unconstrained Binary Optimisation (QUBO), a framework commonly used in the optimisation literature due to its ability to strike a balance between expressivity and tractability. Moreover, QUBO is in some sense “native” for quantum optimisation, particularly the Quantum Adiabatic Optimisation Algorithm (QAOA). Quantum computers are currently limited in size and error-prone, characteristic of the so-called Noisy Intermediate-Scale Quantum (NISQ) era. In the NISQ era, applications of quantum computers must be carefully chosen to mitigate these limitations; combinatorial optimisation is a promising direction that has already seen some success [ 14 , 15 , 16 , 17 ] . A primer on quantum computing and quantum optimisation is given in section S1 . Below, we compare both classical and quantum approaches to the optimisation and discuss the potential utility of quantum approaches. We also make several contributions that may be of interest to the broader (pan)genomics community. We develop a tool for creating synthetic pangenomes that have a realistic biological structure. The size and complexity of these pangenomes can be controlled by adjusting the rate of simulated evolutionary mutations, such as CNVs, large repeats and translocations. We also create a novel tool kmer2node for aligning reads onto pangenome graphs. Finally, we develop a post-processing pipeline to evaluate assembly quality and improve it with an optional step. 2 Results Our main comparison point for existing state-of-the-art is pathfinder [ 13 ] . Pathfinder is a submodule from the oat-k package, a tool for resolving plant organelles using high-accuracy

Read the complete text